Recursive and DP Solution in java

• ``````public class Solution {
// recursive
public int numTrees2(int n) {
if (n == 0 || n == 1) {
return 1;
}
else {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += numTrees(i - 1) * numTrees(n - i);
}
return sum;
}
}

// DP
public int numTrees(int n) {
int[] array = new int[n + 1];
array[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
array[i] += array[j - 1] * array[i - j];
}
}
return array[n];
}
}
``````

Obviously, DP has a much better performance.
The idea is simple.
Make j as the root among i nodes
Left sub-tree has j - 1 nodes
Right sub-tree has i - j nodes;
f(i, j) = f(j - 1) * f(i - j);
f(i) = f(i, 1)+ f(i, 2) + .... + f(i, i);

• here is my solution:

``````int numTrees(int n) {
if (n == 0 || n == 1) return n;
vector<int> N(n+1, 0);
N[0] = 1;
N[1] = 1;

int i;
for (i = 2; i <= n; i++) {
int subNodes = i - 1, j;
for (j = 0; j <= subNodes/2; j++) {
N[i] += 2 * (N[j] * N[subNodes - j]);
if (2*j == subNodes) {
N[i] -= N[j]*N[j];
}
}
}

return N[n];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.