「力扣」第 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:
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
方法二:“记忆化搜索”与“动态规划”
思路:先研究递归结构,发现有大量重叠子问题,再实现“记忆化搜索”,最后实现使用“动态规划”。即先“自顶向下”思考,再“自底向上”实现。
注意:对于每一个状态而言,还要再比较“不再继续分割”和“继续分割”,取当中的最大值,将 $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:动态规划
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]