when ask f(n),the root of possible tree can be 1,2...n,if the root is i,the possible number f(n,i) is the possible number of the left tree multiply by the right;the elements of left child tree is 1...i-1, number is i-1; the right is i+1...n,number is n-i;so f(n,i)=f(i-1)*f(n-i),f(n)=sum( f(n,i) )

```
int numTrees(int n) {
int dp[10000];
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=0;
for(int j=1;j<=i;j++){
dp[i]+=dp[j-1]*dp[i-j];
}
}
return dp[n];
}
```