0️⃣343.整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 :

• 输入: 10
• 输出: 36
• 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
• 说明: 你可以假设 n 不小于 2 且不大于 58。

思路

基本思想

对于整数n拆分之后，形成的最大乘积可以由拆分得到的几个部分的最大乘积相乘得到，所以可以使用动态规划来做

对于一个数n，可以先拆分成两部分，x和n-x，其中x的范围从1一直到n-1，不能取n，否则拆分成n和0没有意义

所以可以从前向后一直拆分，一直拆分到n的时候，前面的数最大拆分结果都已经统计出来，n的拆分结果就是统计所有拆分情况，取最大的拆分结果即可

执行流程

从前向后拆分每一个数，统计他的最大拆分结果

对于每一个数都有n-1种拆分方式，对于每一种拆分方式又可以分成两种情况：

1. 将n拆分成x和n-x，并且n-x不再拆分，此时乘积为x*(n-x)
2. 将n拆分成x和n-x，并且n-x继续拆分，此时乘积为x*dp[n-x]

为什么n-x不再拆分呢，如果n-x是2，此时不拆分的结果更大,所以每个数都判断是否拆分

为什么x不再拆分，看如下证明

因为j * dp[i - j]包含了dp[j] * dp[i - j]，这是可以证明的：

对j最优拆分：j = a1 + a2 +…+an

对i - j 最优拆分：i - j = b1 + b2 +…+bn

所以有 dp[j] = a1 * a2 … an

dp[i - j] = b1 * b2 *… bn

dp[j] * dp[i - j] = (a1 *a2 *…an) * (b1 * b2 … bn) = a1 * (a2 * … * an * b1 * b2 … bn)

令 k = a1，必有i - k = a2 + … + an + b1 + b2 +…+ bn(这就是对 i - k 的一种拆分)

如果以上这种对i - k的一种拆分是最优的，那么必有dp[j] * dp[i - j] = k * dp[i - k]

所以此时j * dp[i - j]包含dp[j] * dp[i - j]，因为j从1增长到i-1；

如果以上这种对i - k的拆分不是最优的，那这种拆分方案虽不会被j * dp[i - j]包含但也不会是答案，此时可以直接丢弃；

也就是说不用对j单独进行拆分,如果当前分割方案是最优的，一定会被某一种拆分方式包含

每一种拆分方式都取两种情况中的最大值，最后所有的拆分方式中取最大值，所以需要取两次最大值

初始化整数1的拆分结果为0，因为他不能拆分

代码

根据以上分析，得出一下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        //依次对每个数进行拆分
        for(int i=2;i<=n;++i){
            //统计每个数的所有拆分结果
            int res=0;//当前最大的拆分结果为0
            for(int j=1;j<i;++j){
                //两种拆分情况谁大
                int curMax=max(j*(i-j),j*(dp[i-j]));
                //所有的拆分方式谁大
                res=max(curMax,res);
            }
            //当前整数的最终拆分结果
            dp[i]=res;
        }
        //返回整数n的拆分结果
        return dp[n];
    }
};

总结

由于一个整数的拆分结果由其拆分之后的数决定，所以从前向后统计所有数的拆分结果

对于每个数n都有n-1种拆分方式，统计所有拆分方式的最大值就是当前整数的拆分结果

后面的数拆分时需要用到前面数的拆分结果，所以从前向后遍历

理解为什么x不被拆分，只拆分n-x！！！

dp[j] * dp[i - j] = k * dp[i - k] 的证明过程