day41 动态规划（3）

day 41
代码随想录
2024.1.8

1. 343整数拆分
这道题主要中间递归公式不会写

1. dp数组很明确，代表结果，也就是i拆分后的最大乘积。
2. 递推公式主要一点是：我们遍历是从左往右的，这也是动态规划的思想所在，计算当前时需要用到之前已经算过的值，所以对于i，我们首先要明确，i之前的所有数已经是算过了的！！！，然后到i这里时，拆分又有很多可能，可以任意在之前每一处位置拆分，而我们要做的就是去这些拆分中的最理想值，也就是最大值！！！，这样是不是就明白了许多，也就是，递归时需要再一次for循环！，因此首先递归公式是max{当前dp值与里层遍历值}；接下来就是里层遍历值怎么求，如果，现在外层是i，里层是j，这个里层遍历值是什么呢，想一想，j从1开始变大，如果是1，然后中间是i-1，如果j是2，中间一段就是i-2.。。。是不是有种情况就是拆分两段就好，也就是j*(i-j)，这是一种，但是，这个i-j能不能细分呢，也就是拆分成多个数的情况，此时怎么表示呢，回忆dp数组的含义，不就是拆分结果吗！！！那i-j的拆分结果不就是dp[i-j]！！！也就是说，此时拆分多次结果就是j*dp[i-j];然后对于j，取这两种情况的最大值，就是此次里层遍历的最优结果！再将该结果与整体目前最优值dp【i】比较，不断更新dp【i】即可！
3. 遍历顺序前面也说了，从左往右
4. 至于dp数组初始化，其实就是最开始的几个值，2！
5. 略！

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i ; j++) { //里层值
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

2. 96不同的二叉搜索树

1. dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

3. 从左往右，大树需要小树的值
4. 初始化最开始两个的值
5. 略

class Solution {
public:
    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];
    }
};