算法吧临时网站

# 「力扣」第 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。

# 思路分析

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

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

# 方法一：贪心算法

分析题意

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

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

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

从小规模数据找规律

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

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

因为 ，明显，越分解乘积越小。

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

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

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

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

得 。

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

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

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

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

得 。

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

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

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

（1）；

（2）；

（3）；

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

在 比较大的时候， 是显然的，而 ，又由上面的第 1 点可知分解出 1 肯定使得乘积越来越小，而且很明显 。

结论：

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

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

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

（1）；

（2）；

（3）；

（4）；

在 比较大的时候， 是显然的，而 ，又由上面的第 1 点可知分解出 1 肯定使得乘积越来越小，而且很明显 。

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

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

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

$$ 6 \times (n-6)< 2 \times 2 \times 2 \times (n - 6) < 3 \times 3 \times (n - 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： 以上（包括 ）的正整数加法因子都不必考虑了，因为分解成它们的乘积，都小于分解出合适数量的 和 相乘以后的乘积。

根据以上分析，正整数加法因子只有 和 ，在根据我们的直觉，感觉分解出 这个正整数加法因子的乘积肯定比分解出 这个正整数加法因子的乘积，还以 为例，，按照惯例，找边界，即解不等式

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

解得 。

结论 7：分解出 比分解出 好。

综上所述：

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

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

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

综上所述：

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

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

参考代码 1：

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;
    }
}

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

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

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

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

参考代码 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：动态规划

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);
    }
}

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]

作者：liweiwei1419 链接：https://suanfa8.com/greedy/solutions/0343-integer-break 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Last Updated: 11/19/2024, 11:31:47 AM

← 「力扣」第 354 题：俄罗斯套娃信封问题（困难） →