```
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);