343. 整数拆分

力扣传送门(opens new window)

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

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

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

解题思路：

确定dp数组（dp table）以及下标的含义

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

dp[i]的定义将贯彻整个解题过程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

确定递推公式

可以想 dp[i]最大乘积是怎么得到的呢？

其实可以从1遍历j，然后有两种渠道得到dp[i].

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。

那有同学问了，j怎么就不拆分呢？

j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。那么从1遍历j，比较(i - j) * j和dp[i - j] * j 取最大的。递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

也可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

如果定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。

所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

那么在取最大值的时候，为什么还要比较dp[i]呢？

因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。

dp的初始化

不少同学应该疑惑，dp[0] dp[1]应该初始化多少呢？

有的题解里会给出dp[0] = 1，dp[1] = 1的初始化，但解释比较牵强，主要还是因为这么初始化可以把题目过了。

严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。

拆分0和拆分1的最大乘积是多少？

这是无解的。

这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！

确定遍历顺序

确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

所以遍历顺序为：

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

注意枚举j的时候，是从1开始的。从0开始的话，那么让拆分一个数拆个0，求最大乘积就没有意义了。

j的结束条件是 j < i - 1 ，其实 j < i 也是可以的，不过可以节省一步，例如让j = i - 1，的话，其实在 j = 1的时候，这一步就已经拆出来了，重复计算，所以 j < i - 1

至于 i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

更优化一步，可以这样：

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。

例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话也是拆成m个近似数组的子数相乘才是最大的。

只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是最差也应该是拆成两个相同的可能是最大值。

那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。

至于 “拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的” 这个我就不去做数学证明了，感兴趣的同学，可以自己证明。

代码实现：

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

我们进行推导一下：

初始化 dp 数组：
dp[0] = 0，dp[1] = 0，dp[2] = 1。
计算 dp[3]：
- j = 1，dp[3] = max(dp[3], max(1*(3-1), 1*dp[3-1])) = max(1, 2) = 2。
计算 dp[4]：
- j = 1，dp[4] = max(dp[4], max(1*(4-1), 1*dp[4-1])) = max(1, 3) = 3。
- j = 2，dp[4] = max(dp[4], max(2*(4-2), 2*dp[4-2])) = max(3, 4) = 4。
计算 dp[5]：
- j = 1，dp[5] = max(dp[5], max(1*(5-1), 1*dp[5-1])) = max(1, 4) = 4。
- j = 2，dp[5] = max(dp[5], max(2*(5-2), 2*dp[5-2])) = max(4, 6) = 6。
计算 dp[6]：
- j = 1，dp[6] = max(dp[6], max(1*(6-1), 1*dp[6-1])) = max(1, 5) = 5。
- j = 2，dp[6] = max(dp[6], max(2*(6-2), 2*dp[6-2])) = max(5, 8) = 8。
- j = 3，dp[6] = max(dp[6], max(3*(6-3), 3*dp[6-3])) = max(8, 9) = 9。
计算 dp[7]：
- j = 1，dp[7] = max(dp[7], max(1*(7-1), 1*dp[7-1])) = max(1, 6) = 6。
- j = 2，dp[7] = max(dp[7], max(2*(7-2), 2*dp[7-2])) = max(6, 10) = 10。
- j = 3，dp[7] = max(dp[7], max(3*(7-3), 3*dp[7-3])) = max(10, 12) = 12。
计算 dp[8]：
- j = 1，dp[8] = max(dp[8], max(1*(8-1), 1*dp[8-1])) = max(1, 7) = 7。
- j = 2，dp[8] = max(dp[8], max(2*(8-2), 2*dp[8-2])) = max(7, 12) = 12。
- j = 3，dp[8] = max(dp[8], max(3*(8-3), 3*dp[8-3])) = max(12, 18) = 18。
- j = 4，dp[8] = max(dp[8], max(4*(8-4), 4*dp[8-4])) = max(18, 16) = 18。
计算 dp[9]：
- j = 1，dp[9] = max(dp[9], max(1*(9-1), 1*dp[9-1])) = max(1, 8) = 8。
- j = 2，dp[9] = max(dp[9], max(2*(9-2), 2*dp[9-2])) = max(8, 14) = 14。
- j = 3，dp[9] = max(dp[9], max(3*(9-3), 3*dp[9-3])) = max(14, 27) = 27。
- j = 4，dp[9] = max(dp[9], max(4*(9-4), 4*dp[9-4])) = max(27, 24) = 27。
计算 dp[10]：
- j = 1，dp[10] = max(dp[10], max(1*(10-1), 1*dp[10-1])) = max(1, 9) = 9。
- j = 2，dp[10] = max(dp[10], max(2*(10-2), 2*dp[10-2])) = max(9, 16) = 16。
- j = 3，dp[10] = max(dp[10], max(3*(10-3), 3*dp[10-3])) = max(36, 21) = 36。
- j = 4，dp[10] = max(dp[10], max(4*(10-4), 4*dp[10-4])) = max(36, 36) = 36。
- j = 5，dp[10] = max(dp[10], max(5*(10-5), 5*dp[10-5])) = max(36, 30) = 36。

通过以上推导，得到了当 n = 10 时，dp 数组的数值。最终结果是 dp[10] = 36。

目录CONTENT

343. 整数拆分

343. 整数拆分

解题思路：

代码实现：

评论区