代码随想录Day41 | 343. 整数拆分 96.不同的二叉搜索树

343.整数拆分

文档讲解：代码随想录
视频讲解： 动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分
状态

1. dp数组
   dp[i] 就表示第i个数的最大乘积
2. 递推公式
   对于dp[i]，可以拆分成两数相加 – j和i-j，最大乘积就是 j*dp[i-j] 与 j*(i-j)的最大值。
   而对于每个j最后有一个最大值。

temp = max(j*dp[i-j],j*(i-j));
dp[i] = max(dp[i],temp);

3. 初始化
   dp[2] = 1
4. 遍历顺序
   从前向后遍历
5. 打印dp

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;
        for(int i = 3;i<=n;i++)
        {
            //对于0 和 1 是无效的
            for(int j = 1;j<i-1;j++)
            {
                dp[i] = max(dp[i],max(j*dp[i-j],j*(i-j)));
            }
        }
        return dp[n];
    }
};

96.不同的二叉搜索树

文档讲解：代码随想录
视频讲解： 动态规划找到子状态之间的关系很重要！| LeetCode：96.不同的二叉搜索树
状态

1. dp数组
   dp[i]就是1-i能够形成二叉搜索树的个数
2. 递推公式
   dp[i] = (以1为头节点的二叉搜索树) + (以2为头节点的二叉搜索树) + … +(以i为头节点的二叉搜索树)
   对于一个以j为头节点的二叉搜索树，那么其左子树就应当是1-j-1构成的二叉搜索树，右子树就是由j+1到i这i-j个元素构成的二叉搜索树。
   所以对于以j为头节点的二叉搜索树的总个数就是

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

3. 初始化
   dp[0] = 1;
   因为从1来看其可以变为dp[0]*dp[0]
4. 遍历顺序
   仍然是从前向后
5. 打印

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