dp专题6 整数拆分

原创已于 2024-01-09 17:22:30 修改 · 粉丝可见 · 1k 阅读 · 19 · 24 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135339747

本题链接：力扣（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 和 i - j 的两个数，然后得到两个数值相乘结果

即： 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 结果
    }
};