# LeetCode 第 343 题：“整数拆分”题解

题解地址：“贪心选择”性质的简单证明、记忆化搜索、动态规划 （Python 代码、Java 代码）。

说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。

传送门：343. 整数拆分。

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

示例 1:

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

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

# “贪心选择”性质的简单证明、记忆化搜索、动态规划 （Python 代码、Java 代码）

能够使用“贪心算法”完成的问题，严格上来说，是要证明这个问题具有“贪心选择”性质，但是如果一个问题，不能使用贪心算法，只需要举一个反例就可以了。

而证明一个问题具有“贪心选择”性质，通常是比较困难的。本篇就我对「力扣」第 343 题：“整数拆分”的贪心选择性质给予证明。

# 方法一：贪心算法

（温馨提示：下面的幻灯片中，有几页上有较多的文字，可能需要您停留一下，可以点击右下角的后退 “|◀” 或者前进 “▶|” 按钮控制幻灯片的播放。）

,,

分析题意

题目中说，把正整数 $n$ 分解成若干个正整数加法因子，让我们求所有可能的加法因子相乘以后乘积的最大值。看示例 2 ，就很清楚题目的意思，这里就不多展开了。

本文对求解这个问题的贪心选择性质做了简单的归纳、证明。即我们要证明的是：

“贪心地”、“尽可能多”地分解出 $3$ 正整这个加法因子，就能够使得最终的乘积得到最大。

从小规模数据找规律

我们不妨从最小的正整数加法因子 $1$ 开始，到 $2$、$3$、$4$、...，依次分析，分解以后，乘积的大小，写几个出来，看看规律。

• 情况 1：如果分解式中含有 $1$

因为 $1 \times (n-1) = n-1 < n$，明显，越分解乘积越小。

结论1：$1$ 不能作为分解的正整数加法因子。

• 情况 2：如果分解式中含有 $2$

直觉上，分解以后相乘肯定比原来这个数要大。例如：$n = 19$ 时，$2 \times 17 = 34 > 19$，越大的数越是如此，因此我们要关心的是边界。于是解不等式

$2 \times (n - 2) > n$

得 $n > 4$。

结论2：当 $n > 4$ 的时候，分解出 $2$ 这个因子，与剩下的数 $(n - 2)$ 得到的乘积，就肯定超过 $n$ 了。

• 情况 3：如果分解式中含有 $3$

直觉上，也是分解以后相乘肯定比原来这个数要大。例如：$n = 19$ 时，$3 \times 16 = 48 > 19$，越大的数越是如此，因此我们要关心的是边界。于是解不等式

$3 \times (n - 3) > n$

得 $n > 4.5$。

结论3：当 $n > 4.5$ 的时候，分解出 $3$ 这个因子，与剩下的数 $(n - 3)$ 得到的乘积，就肯定超过 $n$ 了。

• 情况 4：如果分解式中含有 $4$

情况就有点意思了，我们就可以比较以下四者的乘积大小：

（1）$n$；

（2）$4 \times (n - 4)$；

（3）$2 \times 2 \times (n - 4)$；

（4）$1 \times 3 \times (n - 4)$，其实这都不用考虑，因为情况 1 的结论：$1$ 不能作为分解的正整数加法因子，因为它会使得乘积原来越小，下面我们马上还会分析到。

在 $n$ 比较大的时候，$4 \times (n - 4) > n$ 是显然的，而 $4 \times (n - 4) = 2 \times 2 \times (n - 4)$，又由上面的第 1 点可知分解出 1 肯定使得乘积越来越小，而且很明显 $4 \times (n - 4) > 1 \times 3 \times (n - 4)$。

结论：

结论4：分解出 $4$，等价于分解出两个 $2$，因此，情况 2 就包含了情况 4 ，故没有必要考虑分解出正整数加法因子 $4$。

• 情况 5：如果分解式中含有 $5$

情况也有点意思了，我们就可以比较以下四者的乘积大小：

（1）$n$；

（2）$5 \times (n - 5)$；

（3）$2 \times 3 \times (n - 5)$；

（4）$1 \times 4 \times (n - 5)$；

在 $n$ 比较大的时候，$5 \times (n - 5) > n$ 是显然的，而 $2 \times 3 \times (n - 5) > 5 \times (n - 4)$，又由上面的第 1 点可知分解出 1 肯定使得乘积越来越小，而且很明显 $2 \times 3 \times (n - 5) > 5 \times (n - 4) > 1 \times 4 \times (n - 5)$。

结论5：分解出 $5$ 与 $(n - 5)$ 的乘积还不如分解出 $2$ 、 $3$ 与 $(n-5)$ 的乘积，因此没有必要考虑分解出正整数加法因子 $5$。

为了避免行文啰嗦，我就直接写最关键的部分了：

• 情况 6：如果分解式中含有 $6$

$6 \times (n-6)< 2 \times 2 \times 2 \times (n - 6) < 3 \times 3 \times (n - 6)$

结论：

分解出 $6$ 与 $(n - 6)$ 的乘积还不如分解出 $3$ 、 $3$ 与 $(n-6)$ 的乘积，因此没有必要考虑分解出正整数加法因子 $6$。

写到这里，估计你也看出来了，继续分析下去的结论就是，

$7 \times (n - 7) < 2 \times 2 \times 3 \times (n - 7)$

$8 \times (n - 8) < 2 \times 3 \times 3 \times (n - 8)$

$9 \times (n - 8) < 3 \times 3 \times 3 \times (n - 9)$

结论：

结论6：$4$ 以上（包括 $4$）的正整数加法因子都不必考虑了，因为分解成它们的乘积，都小于分解出合适数量的 $2$ 和 $3$ 相乘以后的乘积。

根据以上分析，正整数加法因子只有 $2$ 和 $3$，在根据我们的直觉，感觉分解出 $3$ 这个正整数加法因子的乘积肯定比分解出 $2$ 这个正整数加法因子的乘积，还以 $n = 19$ 为例，$3 \times 16 = 48 > 34 = 2 \times 17$，按照惯例，找边界，即解不等式

$3 \times (n - 3) \ge 2 \times (n -2)$

解得 $n \ge 5$。

结论7：分解出 $3$ 比分解出 $2$ 好。

综上所述：

我们应该尽可能分解出 $3$ ，直到最后剩下 $4$ 或者 $2$。

下面我们分析最后剩下几就不能再分出 $3$ 了：

如果最后剩下 $7$ 的话，可以分解成两个 $3$、$3$、$2$；
如果最后剩下 $6$ 的话，可以分解成两个 $3$；
如果最后剩下 $5$ 的话，可以分解成 $3$ 和 $2$；
如果最后剩下 $4$ 的话，不能分解出 $3$ 了，因为最后剩下的正整数加法因子是 $1$，由结论 1 ，这是不允许的；
如果最后剩下 $3$ 的话，不能分解出 $2$ 了，因为剩下是 $1$，由结论 1 ，这是不允许的。

综上所述：

在大于 $4$ 的前提下，尽可能分解出 $3$ 。当 $n \le 4$ 的时候，专门计算一下给出结论就可以了。

以上分析其实并不难，关键要动手写一下，相信聪明的你一定会比我做得更好。

参考代码 1：

Python 代码：

class Solution:
    def integerBreak(self, n):
        if n == 2:
            return 1
        if n == 3:
            return 2
        if n == 4:
            return 4
        res = 1
        while n > 4:
            res *= 3
            n -= 3

        res *= n
        return res

Java 代码：

public class Solution {
    public int integerBreak(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        // 接下来就是 n >= 5 的时候的逻辑了
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        res *= n;
        return res;
    }
}

# 方法二：“记忆化搜索”与“动态规划”

思路：先研究递归结构，发现有大量重叠子问题，再实现“记忆化搜索”，最后实现使用“动态规划”。即先“自顶向下”思考，再“自底向上”实现。

注意：对于每一个状态而言，还要再比较“不再继续分割”和“继续分割”，取当中的最大值，将 $n$ 进行分解的时候，以 $8$ 为例：$1$ 与 $7$ 是一个解，$1$ 与 $7$ 的分解的结果也是一个解。

参考代码 2：记忆化搜索

Python 代码：

class Solution:
    def __init__(self):
        self.memo = []

    def integerBreak(self, n):
        self.memo = [-1 for _ in range(n + 1)]
        self.memo[0] = 1
        self.memo[1] = 1
        return self.__dfs(n)

    def __dfs(self, n):
        if n == 1:
            return 1
        if self.memo[n] == -1:
            res = 0
            for i in range(1, n):
                res = max(res, i * (n - i), i * self.__dfs(n - i))
            self.memo[n] = res
        return self.memo[n]

Java 代码：

public class Solution {

    private int[] memory;

    public int integerBreak(int n) {
        assert n >= 2;
        memory = new int[n + 1];
        memory[0] = 0;
        memory[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            memory[i] = -1;
        }
        int res = breakInteger(n);
        return res;
    }


    // 将 n 进行分割得到的乘积最大值
    private int breakInteger(int num) {
        if (num == 1) {
            return 1;
        }
        if (memory[num] == -1) {
            int res = 0; // 这个初始值可以设置为 0 吗，1 行不行？
            for (int i = 1; i < num; i++) {
                // 关键之处：状态转移方程，其中 i * (num - i) 这一步很关键，千万不能漏掉
                res = max3(res, i * (num - i), i * breakInteger(num - i));
            }
            memory[num] = res;
        }
        return memory[num];
    }

    private int max3(int num1, int num2, int num3) {
        int temp = Integer.max(num1, num2);
        return Integer.max(temp, num3);
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int max = solution.integerBreak(9);
        System.out.println(max);
    }
}

参考代码 3：动态规划

Python 代码：

class Solution:
    def integerBreak(self, n):
        dp = [1 for _ in range(n + 1)]
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * dp[i - j], j * (i - j))
        return dp[n]

Java 代码：

/**
 * 动态规划的解法
 * Created by liwei on 17/10/3.
 */
public class Solution3 {

    private int[] memory;

    public int integerBreak(int n) {
        memory = new int[n + 1];
        memory[0] = 0;
        memory[1] = 1;
        for (int i = 2; i <= n; i++) {
            int maxValue = -1;
            for (int j = 1; j <= i - 1; j++) {
                maxValue = max3(maxValue, j * (i - j), j * memory[i - j]);
            }
            memory[i] = maxValue;
        }
        return memory[n];
    }

    private int max3(int num1, int num2, int num3) {
        int temp = Integer.max(num1, num2);
        return Integer.max(temp, num3);
    }

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        int max = solution.integerBreak(9);
        System.out.println(max);
    }
}