不同的二叉搜索树

题目描述：
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例：

image.png
假设n个节点存在的二叉树个数为G(n)，令f(i)为以i为根的二叉树个数。
则G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)。当以i为根节点时，其左子树节点个数为i - 1，右子树结点个数为n - i,则有f(i) = G(i - 1) * G(n - i)。综上可得卡特兰数公式：
G(n) = G(0)G(n-1) + G(1)G(n-2) + ... + G(n-1)*g(0)

Java代码：

class Solution {
    public int numTrees(int n) {
        if(n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2;i < n + 1;i++)
            for(int j = 1;j < i + 1;j++)
                dp[i] += dp[j - 1] * dp[i - j];
        
        return dp[n];
    }
}