[LeetCode] Unique Binary Search Trees
Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's.
問題解決の考え方:
動的計画1,2に対して,...,i,...nの場合、二分ルックアップブックの個数は、iがルートノードであるすべての二分ルックアップツリーの個数の和に等しい.一方,iをルートノードとし,異なる左サブツリーの数をd[i−1]、異なる右サブツリーの数をd[n−i+1]とするのはいずれもd[i]のサブ問題であるため,動的計画により解くことができる.
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
問題解決の考え方:
動的計画1,2に対して,...,i,...nの場合、二分ルックアップブックの個数は、iがルートノードであるすべての二分ルックアップツリーの個数の和に等しい.一方,iをルートノードとし,異なる左サブツリーの数をd[i−1]、異なる右サブツリーの数をd[n−i+1]とするのはいずれもd[i]のサブ問題であるため,動的計画により解くことができる.
class Solution {
public:
int numTrees(int n) {
if(n<1){
return 1;
}
int d[n + 1];
memset(d, 0, sizeof(int) * (n+1));
d[0] = 1;
for(int i=1; i<=n; i++){
for(int j=0; j<i; j++){
d[i] += d[j]*d[i-j-1];
}
}
return d[n];
}
};