96. 不同的二叉搜索树

原题链接：96. 不同的二叉搜索树

solution:

一样的题目

95. 不同的二叉搜索树 II_anieoo的博客-CSDN博客

给定长度固定时，不同二叉搜索树的种类一样。

比如：1~10的二叉搜索树的种类和10~20的种类数一样

总的二叉搜索树的种类等于左子树的种类*右子树的种类

动态规划：dp[i]表示连续长度为i的二叉搜索树的种类

状态计算：枚举长度为i中的每个根节点j，

dp[i] = dp[j - 1] * dp[i - j]

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