思路

code

public int numTrees(int n) {
     int[] dp = new int[n+1];
     dp[0]=1;
     dp[1]=1;
    //从n=2自底向上计算
     for(int i=2;i<=n;i++){
         for(int j=1;j<i+1;j++)
             dp[i]+=dp[j-1]*dp[i-j];  //递推公式
     }
     return dp[n];
}