dp专题6 整数拆分

2024-01-02 16:08:47

本题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目:

思路:

? ? ? ? 对于整数拆分,就是多个子问题,我们通过解决一个子问题,来推出大问题,我们拆分的时候,按照逻辑一个数拆成两个数,比如: 6 = 2 + 4?或者 6 = 1 + 5 或者 6 = 3 + 3 ...等,其中 拆分了一个数之后,如果拆分得到的数不为 1 说明还是可以拆分,所以这时候我们可以得到了子问题的特征了,即 dp[N] 中 dp 的下标含义应该是什么, 我们dp下标的含义应该指向我们拆分的数,其中 dp[下标]? 元素 含义那就是我们可以拆成后所求的结果。

根据题目意思,需要的是 拆分后相乘的最大结果,所以我们的dp 公式一定要有 max函数

现在我们一步一步来推:

第一步:dp 的初始化

我们可以知道,dp[0] = dp[1] = 0 因为 0 和 1 无法拆分了或者可以理解为 拆分得到 0, 1相乘最大结果就是 0 , 然后? dp[2] = 1 因为 拆分后 1 + 1 拆分数相乘最大结果就是 1。

第二步:明确题目要求,dp公式应该是什么

根据题目意思,我们拆分一个数后,得到的应该是两个数了

所以? 我们设? 拆分 i? 得到 j 和 j - i 的两个数,然后得到两个数值相乘结果

即:? ? j * (i?- j)? 这是一种结果? ①

其中? 我们 dp[] 元素存储的是 我们对 下标 i 拆分的数最大结果相乘,我们又得到第二种结果。

即:? ? j * dp[i - j] 这是第二种结果 ②

这时候有人就会疑问了,为什么不是 dp[j]*dp[i - j] ,这是因为我们 dp[i - j] 的时候就已经包含了? dp[ j ] 的拆分了, 例如? : 8 = 4 + 2 + 2? ?其中? 8 = 2 + 2 + 4?也是一样的

最后也要注意,我们 dp[] 存储的是我们拆分过程的结果,我们也要注意更新最优结果。

即还有第三种结果就是 我们 拆分 i 的时候 前面拆分过的结果有可能是最优的 dp[ i ] 所以也有第三种结果就是? dp[ i ] = dp[ i ]

最后 dp 公式为 :? dp[ i ] = max(dp[ i ],max(j * (i - j) ,j * dp[ i - j ]))

这里我们还可以优化以下,由于? ? i - j? 减到 一定程度 会变成 i - j = i 的情况,它的临界值就是在 i / 2 那里又因为 C++ 是向下取整 我们减的临界值应该 向上取整更优

代码详解如下:

class Solution {
public:
    int integerBreak(int n) {
        vector<int>dp(n+ 1,0);    // 声明 dp 数组
        dp[2] = 1;  // dp 初始化

        for(int i = 3;i <= n;++i)   // 第一层循环为拆分数
        {
            for(int j = 1;j <= i / 2 + 1;++j)   // 第二层循环为 拆分得到的两个数 j , i - j
            {
                dp[i] = max(dp[i],max(j*(i - j),j*dp[i - j]));  // dp 更新
            }
        }
        return dp[n];   // 返回 dp 结果
    }
};

最后提交:

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