不同的二叉搜索树

该题虽然是一个二叉树的题目 但是使用动态规划做

1. dp[i]数组的含义：i个节点有多少种组合方式
2. 递推公式：dp[i] = dp[j] + dp[i-1-j] j(0–>i-1)
3. 初始化：dp[0]=1 dp[1] = 1
4. 确定递推顺序 i(2–>n) j(0–>i-1)
5. 推导一遍

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<= n ;i++){
            for(int j = 0;j <= i-1 ; j++){
                dp[i] += dp[j] * dp[i-1-j];
            }
            System.out.print(dp[i]);
        }
        return dp[n];
    }
}