```
public class Solution {
int[][] map;
public int numTrees(int n) {
map = new int[n][n];
return num(1, n);
}
public int num(int m, int n){
if(m == n)
return 1;
if(map[m - 1][n - 1] != 0)
return map[m - 1][n - 1];
int sum = 0;
for(int i = m; i <= n; i++){
if(i == m)
sum += num(i + 1, n);
else if(i == n)
sum += num(m, i - 1);
else
sum += num(m, i - 1) * num(i + 1, n);
}
map[m - 1][n - 1] = sum;
return sum;
}
}
```