这道题求的是二叉搜索树的个数，题目见 96. 不同的二叉搜索树

我们先从1，2，开始找规律。有1个节点，二叉搜索树的个数是1；有2个节点，二叉搜索树的个数是2。当有3个节点时，二叉搜索树的总数目是由根节点左边的节点组成的二叉搜索树的数目乘以根节点右边的节点组成的二叉搜索树的数目，可以看出结点的数目可以由更少的节点数目推出来。

设dp[i]为节点数目为i的二叉搜索树的个数，递推公式为dp[i]=dp[i]+dp[j]*dp[i-1-j]，因为每一次的二叉搜索树个数都是当前的左右子树数目乘积加上前一次的二叉搜索树的数目。

考虑特殊情况，有0个节点，二叉搜索树的个数是1，因为当根节点的某一个子树为空，则该子树的二叉搜索树的数目为1，1乘以另一个不为空的子树的二叉搜索树的个数不影响结果，这是符合实际情况的。代码如下

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