LeetCode：96 不同的二叉搜索树

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

n = 3时，有5种
   1         3       3       2      1
    \       /        /         / \        \
     3    2       1       1   3       2
    /     /           \                      \
   2    1             2                    3

思路：

public class NumTrees {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        if(n <= 1) {
            return 1;
        }
        //G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)
        for (int i = 2; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                //从2开始递推，递推的方式空间复杂度：O(n)
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        NumTrees numTrees = new NumTrees();
        int i = numTrees.numTrees(5);
        System.out.println(i);
    }
}