LeetCode Solutions
96. Unique Binary Search Trees
Time: $O(n^2)$ Space: $O(n)$
class Solution {
public:
int numTrees(int n) {
// G[i] := # of unique BST's that store values 1..i
vector<int> G(n + 1);
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; ++j)
G[i] += G[j] * G[i - j - 1];
return G[n];
}
};
class Solution {
public int numTrees(int n) {
// G[i] := # of unique BST's that store values 1..i
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j < i; ++j)
G[i] += G[j] * G[i - j - 1];
return G[n];
}
}
class Solution:
def numTrees(self, n: int) -> int:
# G[i] := # Of unique BST's that store values 1..i
G = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
for j in range(i):
G[i] += G[j] * G[i - j - 1]
return G[n]