LeetCode 343 Integer Break 整数拆分全解:从暴力递归到数学最优解的七种思路
LeetCode 343 Integer Break 整数拆分全解:从暴力递归到数学最优解的七种思路
本文基于本仓库 articles/integer-break.md 讲解文档展开,围绕 LeetCode 343(Integer Break)给出从递归、动态规划到纯数学推导的完整解法演进路径。读者读完可掌握:如何用"必须至少拆分一次"的约束建模递归与 DP 状态、自顶向下与自底向上两种 DP 写法的差异,以及为什么最优解总是由大量因子 3 构成。文末的 Common Pitfalls 部分汇总了本题最容易踩的三个坑,可用于面试前的快速自查。
前置知识
在动手实现前,建议先对以下三个基础能力足够熟练:
- 递归(Recursion)——把大问题拆成更小的子问题,再把子问题的结果组合起来。本题所有解法都以"把
n拆成i与n - i"这一递归分解为起点。 - 动态规划(Dynamic Programming)——包括记忆化搜索(top-down)与表格递推(bottom-up)两种实现方式。本题非常适合用来体会"同一 DP 思想、两种写法"的差异。
- 数学推理(Mathematical Reasoning)——理解为什么因子 3 能让乘积最大化,这是把复杂度从 O(n²) 降到 O(log n) 的关键。
题目回顾
给定一个正整数 n,将它拆分成 至少两个 正整数的和,并使这些正整数的乘积最大化,返回这个最大乘积。例如 n = 10 时,最优拆分是 10 = 3 + 3 + 4,乘积为 3 × 3 × 4 = 36(该示例同样出现在仓库 cpp/0343-integer-break.cpp 的注释中)。
本题唯一的"硬约束"是:原始数字必须被拆分(k ≥ 2),而拆分出来的子部分可以继续拆,也可以保持原样。
1. 递归(暴力枚举)
直觉
要想让乘积最大,可以尝试所有可能的拆分方式。对每个数字,考虑把它拆成两部分,再递归计算每一部分的最优乘积。关键洞察是:子部分可以继续拆分,也可以保持原样;唯独原始输入 n 必须至少拆一次。
算法
- 定义递归函数
dfs(num),返回从num能得到的最大乘积; - 基准情况:
num == 1时返回1; - 若
num等于原始输入n,结果初始化为0(必须拆分);否则num本身就是一个合法选项; - 枚举所有拆分点
i(从1到num - 1),计算dfs(i) * dfs(num - i)并保留最大值; - 返回最大乘积。
class Solution:
def integerBreak(self, n: int) -> int:
def dfs(num):
if num == 1:
return 1
res = 0 if num == n else num
for i in range(1, num):
val = dfs(i) * dfs(num - i)
res = max(res, val)
return res
return dfs(n)
C++ 版本中,通过额外参数 original 来区分"当前数字是否是原始输入",逻辑完全等价:
class Solution {
public:
int integerBreak(int n) {
return dfs(n, n);
}
private:
int dfs(int num, int original) {
if (num == 1) return 1;
int res = (num == original) ? 0 : num;
for (int i = 1; i < num; i++) {
int val = dfs(i, original) * dfs(num - i, original);
res = max(res, val);
}
return res;
}
};
复杂度分析
- 时间复杂度:O(n^n)——每个数字都要枚举全部拆分点,递归树呈指数爆炸;
- 空间复杂度:O(n)——递归调用栈深度。
2. 递归(有界背包视角)
直觉
暴力法枚举的是"无序的两部分拆分",存在大量重复。换个角度看,这个问题等价于一个有界背包(bounded knapsack):我们反复从 num 中减去某个因子 i,并把 i 乘进答案,i 的取值范围是 1 到 n - 1。通过允许同一个值被重复取用,所有组合被更高效地探索。
算法
- 定义
dfs(num, i),num是剩余值,i是当前允许使用的最大因子; - 基准情况:
num或i为0时返回1; - 若
i > num,把i缩小为num; - 在两种选择中取最大值:
- 使用因子
i:i * dfs(num - i, i); - 跳过因子
i:dfs(num, i - 1);
- 使用因子
- 入口调用
dfs(n, n - 1)。
class Solution:
def integerBreak(self, n: int) -> int:
def dfs(num, i):
if min(num, i) == 0:
return 1
if i > num:
return dfs(num, num)
return max(i * dfs(num - i, i), dfs(num, i - 1))
return dfs(n, n - 1)
复杂度分析
- 时间复杂度:O(n²)——状态数从指数级压缩到约 n²;
- 空间复杂度:O(n)——递归栈深度。
3. 动态规划(自顶向下)I
直觉
暴力递归会对相同子问题反复计算。把结果存入记忆化表后,每个 num 只计算一次、之后直接复用,冗余工作被消除。
算法
- 建立哈希表
dp,基准dp[1] = 1; - 定义
dfs(num):- 若
num已在dp中,直接返回缓存值; - 初始化
dp[num]:num == n时为0,否则为num; - 枚举拆分点
i(1到num - 1),用max(dp[num], dfs(i) * dfs(num - i))更新; - 返回
dp[num];
- 若
- 调用
dfs(n)并返回结果。
class Solution:
def integerBreak(self, n: int) -> int:
dp = {1: 1}
def dfs(num):
if num in dp:
return dp[num]
dp[num] = 0 if num == n else num
for i in range(1, num):
val = dfs(i) * dfs(num - i)
dp[num] = max(dp[num], val)
return dp[num]
return dfs(n)
这一写法与仓库 kotlin/0343-integer-break.kt 中注释为 DFS + memoization solution O(n^2) time and space 的实现思路一致:用 cache 数组替代哈希表,cache[num] = if (num == n) 0 else num 的初始化与本文完全对应。
复杂度分析
- 时间复杂度:O(n²);
- 空间复杂度:O(n)。
4. 动态规划(自顶向下)II
直觉
这一版对"有界背包"形式也做记忆化。缓存键由剩余值 num 与当前最大可用因子 i 两个维度组成,避免不同递归路径上相同状态被重复计算。
算法
- 建立二维记忆表
dp[num][i],初始化为-1; - 定义
dfs(num, i):- 若
min(num, i) == 0,返回1; - 若
dp[num][i]已缓存,直接返回; - 若
i > num,置dp[num][i] = dfs(num, num); - 否则置
dp[num][i] = max(i * dfs(num - i, i), dfs(num, i - 1)); - 返回
dp[num][i];
- 若
- 调用
dfs(n, n - 1)。
class Solution:
def integerBreak(self, n: int) -> int:
dp = {}
def dfs(num, i):
if min(num, i) == 0:
return 1
if (num, i) in dp:
return dp[(num, i)]
if i > num:
dp[(num, i)] = dfs(num, num)
return dp[(num, i)]
dp[(num, i)] = max(i * dfs(num - i, i), dfs(num, i - 1))
return dp[(num, i)]
return dfs(n, n - 1)
复杂度分析
- 时间复杂度:O(n²);
- 空间复杂度:O(n²)——二维记忆表。
5. 动态规划(自底向上)
直觉
不用递归,直接从小数字开始迭代:对从 2 到 n 的每个数字,枚举所有拆分方式,组合之前已算好的结果。
算法
- 建立长度
n + 1的数组dp,dp[1] = 1; - 对每个
num(2到n):- 初始化
dp[num]为num(若num == n则为0); - 对每个
i(1到num - 1),执行dp[num] = max(dp[num], dp[i] * dp[num - i]);
- 初始化
- 返回
dp[n]。
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for num in range(2, n + 1):
dp[num] = 0 if num == n else num
for i in range(1, num):
dp[num] = max(dp[num], dp[i] * dp[num - i])
return dp[n]
仓库中已有两个同思路的自底向上实现可对照阅读:
- cpp/0343-integer-break.cpp(注释标注
Time: O(n^2), Space: O(n)):dp[0] = 1, dp[1] = 1,内层用i * dp[ind - i]更新,且只有ind < n时才允许dp[ind] = max(dp[ind], ind)保留"不拆"选项,与本文"仅原始数字必须拆"的约束完全一致; - c/0343-integer-break.c:内层只枚举
j到i / 2,同时比较j * (i - j)(直接保留两部分)与j * maxProducts[i - j](继续拆分剩余部分),是一个更紧凑的等价写法。
复杂度分析
- 时间复杂度:O(n²);
- 空间复杂度:O(n)。
6. 数学法(贪心拆 3)
直觉
数学分析表明:最优策略是把数字尽量拆成多个 3。原因是 3 在"每单位数值贡献的乘积"上最优。同时要避免余数为 1 的情况——3 + 1 = 4,而 2 × 2 > 3 × 1,所以余 1 时应把一个 3 换成两个 2。对很小的 n(n <= 3)则需要特判。
算法
- 若
n <= 3,返回n - 1(因为必须至少拆一次,2 → 1×1 = 1,3 → 1×2 = 2); - 反复从
n中减去3并让结果乘3,直到n <= 4; - 把最终余数(只能是
2、3或4)乘进结果; - 返回结果。
class Solution:
def integerBreak(self, n: int) -> int:
if n <= 3:
return n - 1
res = 1
while n > 4:
res *= 3
n -= 3
return res * n
这一写法与仓库 java/0343-integer-break.java 的实现逐行对应(if (n < 4) return n - 1; 后 while (n > 4) 循环乘 3 减 3,最后 res *= n)。kotlin/0343-integer-break.kt 中注释为 Math solution O(n) time and O(1) space 的版本也完全相同。
复杂度分析
- 时间复杂度:O(n)——循环次数约为 n/3;
- 空间复杂度:O(1)。
7. 数学法(最优,直接公式)
直觉
上一步的循环本质上是在数"有多少个 3",因此可以直接用公式算出:若 n % 3 == 0,答案为 3^(n/3);若 n % 3 == 1,少用一个 3 改乘 4(因为 2 × 2 > 3 × 1);若 n % 3 == 2,则在 3 的幂上再乘 2。
算法
- 若
n <= 3,返回n - 1; - 计算
res = 3^(n / 3); - 若
n % 3 == 1,返回(res / 3) * 4; - 若
n % 3 == 0,返回res; - 否则返回
res * 2。
class Solution:
def integerBreak(self, n: int) -> int:
if n <= 3:
return n - 1
res = 3 ** (n // 3)
if n % 3 == 1:
return (res // 3) * 4
return res * max(1, (n % 3))
kotlin/0343-integer-break.kt 末段注释为 Mathimatically solved O(1) 的实现展示了同一公式的另一种等价推导:res = n / 3 与 rem = n % 3,余 1 时把 rem 改为 4 并让 3 的个数减一,最后计算 3^res * rem。
复杂度分析
- 时间复杂度:O(log n)——主要由幂运算
3^(n/3)决定; - 空间复杂度:O(1)。
解法复杂度总览
| 解法 | 思路 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 1. 递归(暴力) | 枚举两两拆分 | O(n^n) | O(n) |
| 2. 递归(有界背包) | 重复取因子 i | O(n²) | O(n) |
| 3. DP 自顶向下 I | 一维记忆化 | O(n²) | O(n) |
| 4. DP 自顶向下 II | 二维记忆化 | O(n²) | O(n²) |
| 5. DP 自底向上 | 表格递推 | O(n²) | O(n) |
| 6. 数学(贪心拆 3) | 循环乘 3 | O(n) | O(1) |
| 7. 数学(最优公式) | 直接计算 | O(log n) | O(1) |
常见陷阱(Common Pitfalls)
陷阱一:忘记原始数字必须被拆分
最常见的错误是允许原始输入 n 保持不拆。题目要求 k >= 2,即至少拆分一次,因此直接返回 n 本身是非法答案。正确做法是在基准初始化处强制原始数字至少拆一次,同时仍允许子问题直接使用自身值——这正是所有解法中 res = 0 if num == n else num 这一行存在的原因。
陷阱二:错误处理小数值 n
n = 2 和 n = 3 是特殊情况:对它们执行拆分得到的乘积反而比保持原样更小。例如 n = 2 拆成 1 × 1 = 1(但题目强制必须拆,所以答案就是 1);n = 3 拆分最佳也只有 1 × 2 = 2。很多解法失败是因为没有把这些边界情况与一般递归情形区分开——务必在递归或数学解法入口处对 n <= 3 做特判。
陷阱三:使用因子 1 或大于 4 的因子
拆出因子 1 永远不会带来收益,因为 1 × (n - 1) < n。同理,保留任何大于 4 的因子都是次优的——它总可以拆成更小的因子组合以获得更大乘积。例如 5 应拆成 2 + 3 得到乘积 6,而不是保留 5。这也解释了为什么最优解只由因子 2 和 3 构成。
在仓库中继续探索
本题的讲解文档位于 articles/integer-break.md,对应题号 0343 的多语言实现散落在仓库各目录中,可作为对照阅读与提交验证的参考:
仓库 README.md 中维护了完整的题解索引表,可以按语言(Python、Java、JavaScript、C++、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C、Scala、Dart)快速定位其他题目的实现。建议按"暴力递归 → 记忆化 → 自底向上 → 数学法"的顺序亲手实现一遍,体会同一种最优子结构在不同范式下的表达差异。