```
public class Solution {
public int numTrees(int n) {
if (n <= 0) {
return 0;
}
int []state = new int[n];//memorized search
return helper(n, state);
}
public int helper(int n, int[] state) {
if (n == 0) {
return 1;
}
if (state[n - 1] != 0) {
return state[n - 1];
}
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += helper(i - 1, state) * helper(n - i, state);
}
state[n - 1] = sum;
return sum;
}
```

}