Description
Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3
Output: 5
Constraints:
1 <= n <= 19
Solution
動態規劃
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int numTrees(int n) {
if (n == 1 || n == 0){
return 1;
}
int table[n + 1];
table[0] = 1;
table[1] = 1;
for (int i = 2; i <= n; ++i){
table[i]=0;
for (int j = 0; j < i; ++j){
table[i] += table[j] * table[i - j - 1]; //left subtree number * right subtree number
}
}
return table[n];
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Binary Search Trees.
Memory Usage: 5.9 MB, less than 92.43% of C++ online submissions for Unique Binary Search Trees.
