96. 不同的二叉搜索树 (opens new window)

1.动态规划

要善于将问题拆解成子问题，对于从1到n的所有节点，每个节点都可以作为根节点；第i个节点作为根节点的方案数就等于节点[1,i-1]构成左子树的方案数*节点[i,n]构成的右子树方案数。由此可见原问题的解用到了子问题的解，可以采用动态规划的方式解决问题。不能仅仅思考dp[i+1]与dp[i]的关系。

利用了二叉搜索树的左右子树都是二叉搜索树的性质。这也是树的特点，进一步将原问题拆分成子问题。

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

    }
}