dp专题6 整数拆分

本题链接：力扣（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 结果
    }
};

最后提交：