力扣-不同的二叉搜索树

96. 不同的二叉搜索树

class Solution {
public:
//动规五部曲
//1.确定dp数组和下标i的含义
//i个节点组成不同的二叉搜索树个数为dp[i]
//2.确认递推公式（j从1到i）
//dp[i] += dp[以j为头节点时，左子树节点数量] * dp[以j为头节点时，右子树节点数量]
//dp[i] += dp[j - 1]*dp[i - j]
//3.初始化dp
//dp[0] = 1;//空节点算一种
//4.遍历顺序：从前往后
//5.举例验证：
//1  2  3  4  n = 4时，dp[4] = dp[0]*dp[3] + dp[1]*dp[2] + dp[2]*dp[1] + dp[3]*dp[0];
//1  2  5  14 
    int numTrees(int n) {
        vector<int> 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];
    }
};

    今天这题目，感觉挺难想的，特别像找规律的题，我一开始找的规律是这样的：

\[dp[i] = dp[i - 1] + \sum_{j=0}^{j=i-1}dp[j]\]

    但在第五步推导时，n=4就不对了，所以规律找错了，我也有想到按头节点来分类找，但没想到这个正确的规律。

    今天早晨为了等热水，来自习室挺晚了，所以偷下懒，就写一道吧~

    我看代码随想录到这道题也有个小结，下面就是背包问题了，刷代码随想录就先到此为止吧，明天开始看胡凡的数据结构，开刷pat了。