day41 动态规划(3)

2024-01-08 13:36:07

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];
    }
};

文章来源:https://blog.csdn.net/qq_56913257/article/details/135453810
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。