最简单明了的整数拆分解析

LeetCode链接

题目介绍

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

 【题目分析】

这题又是一道动态规划题，且听我详细道来。

• 首先，我们可以看出，n = 0, n = 1是能拆分
• 其次 n = 2可以拆分成 1 +1;  最大乘积为1；
• n = 3 可以拆分 为 1 + 2  和 2+ 1；此时发现有重复，最大乘积 为2
• n = 4 可以拆分为 1 + 3和 2 + 2 和 3 + 1，乘积为3,4,3 最大为4；
• 我们可以看出在n 的值较小时，一般只能拆分成两个。
• 当n = 9 时 可以 拆分的情况很多，但是最大值为 3 * 3 * 3 = 27；
• 同理 n = 10 最大值为 3 * 3 * 4 = 27；

分析完后，我们发现第一个难题，有的值可以拆分为两个取到最大，有的值却可以拆分为3个或者更多，那么我们应该如何用代码来表示这种情况呢？

第一步我们先定义一个动态规划数组dp[i]，表示拆分数组i可以取的最大值dp[i];

第二步外层循环变量为i 对3 -> n进行遍历，然后内层循环变量为j在进行遍历得到拆分i后的的最大乘积值。（外层循环遍历元素，内层循环找该元素的最大值）

 外层循环的结束条件是 i <= n,为什么内层循环条件是j < i -1呢？

我们之前说过，在查询时候有重复值出现

 n = 4，其实我们只需要遍历到2即可，并不需要遍历到j = i-1,因此这个问题解决了。

那么我们继续思考，

dp[i] 应该如何被更新呢？

我们之前提到，有的值可以拆分成两个元素取得最大值，有的元素却可以拆分多个（>=3）元素取得乘积的最大值，那么这两种情况如何表示嗯？

• 拆分成两个元素：i = （i - j） + j; 因此其乘积为(i - j) * j；
• 拆分成多个元素：其乘积表示为：dp[i-j] * j;

拆分成两个元素好理解，那么多个元素为什么是这样呢？先看一下我们dp[i]的定义。

dp[i] 表示：拆分i时，取得的最大乘积值为dp[i]

假如我们更新9，那么i =9 j = 1至 7；当j = 3时，拆分为两个元素 为 3*6= 18；拆分为3个元素为3 *dp[6] = 3 * 9= 27;因为dp[6] = 3* 3; 

到此，可以证明拆分成多个元素可以通过dp[i-j] * j表示。

最后还有一步：dp的最终更新策略是这样的

dp[i] = Math.max(dp[i],Math.max((i- j) * j,dp[i - j] * j));

 比之前多了一个与dp[i]相比取较大值，

思考，为什么是这样呢？

看一下我们循环遍历

以9 为例，内层循环是从j = 1---7;

我们知道取最大是在dp[6] * 3处取得，

dp[i] = Math.max((i- j) * j,dp[i - j] * j);

如果dp[i]以这样更新,则dp[i] 中保存的就不是拆分当前i的最大值了。

【总结】

• 此题的dp数组为dp[i] ，表示拆分i时，乘积的最大值为dp[i]
• 循环遍历为两层循环，外层循环遍历元素，内层循环找该元素的最大值
• dp[i]的更新为 dp[i] = Math.max(dp[i],Math.max((i- j) * j,dp[i - j] * j));

【代码】

package db;
 
public class IntegerBreak {
    public static void main(String[] args) {
        int i = new IntegerBreak().integerBreak(10);
        System.out.println("i = " + i);
    }
 
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        }
        // 拆分数字i，可以得到的最大乘积dp[i]
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i - 1; j++) {
                dp[i] = Math.max(dp[i],Math.max((i- j) * j,dp[i - j] * j));
            }
            System.out.printf(dp[i] + "\t");
            System.out.println();
        }
        return dp[n];
    }
}

---

如果觉得讲的还算详细的话，可以支持一下！