leetcode96. 不同的二叉搜索树

1.题目描述：

给你一个整数n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

2.动态规划：

dp数组dp[i]代表i个节点能构成的二叉搜索树个数。那么dp[i] = f(1) + f(2) + ...... + f(i)，分解为头节点为1到i的二叉搜索树数量之和（j从1到i），f(j)  = dp[j - 1] * dp[i - j]，左子树能构成的二叉搜索树（根据二叉搜索树特性得出的节点数）与右子树的乘积。就有递推公式：dp[n] = dp[0] * dp[n - 1] + dp[1] * dp[n - 2] + dp[2] * dp[n - 3] + ...... + dp[n - 1] * dp[0]。初始化dp数组时，dp[0] = 1（无左子树，仅有右子树的变化）。

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 = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}