LeetCode 343 Integer Break 整数拆分全解从暴力递归到数学最优解的七种思路【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 articles/integer-break.md 讲解文档展开围绕 LeetCode 343Integer 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在两种选择中取最大值使用因子ii * dfs(num - i, i)跳过因子idfs(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枚举拆分点i1到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的数组dpdp[1] 1对每个num2到n初始化dp[num]为num若num n则为0对每个i1到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。对很小的nn 3则需要特判。算法若n 3返回n - 1因为必须至少拆一次2 → 1×1 13 → 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. 递归有界背包重复取因子 iO(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循环乘 3O(n)O(1)7. 数学最优公式直接计算O(log n)O(1)常见陷阱Common Pitfalls陷阱一忘记原始数字必须被拆分最常见的错误是允许原始输入n保持不拆。题目要求k 2即至少拆分一次因此直接返回n本身是非法答案。正确做法是在基准初始化处强制原始数字至少拆一次同时仍允许子问题直接使用自身值——这正是所有解法中res 0 if num n else num这一行存在的原因。陷阱二错误处理小数值nn 2和n 3是特殊情况对它们执行拆分得到的乘积反而比保持原样更小。例如n 2拆成1 × 1 1但题目强制必须拆所以答案就是 1n 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 的多语言实现散落在仓库各目录中可作为对照阅读与提交验证的参考C 实现自底向上 DPJava 实现数学法C 实现自底向上 DP内层只枚举一半Kotlin 实现四种解法DP、DFS记忆化、数学法、O(1) 公式法仓库 README.md 中维护了完整的题解索引表可以按语言Python、Java、JavaScript、C、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C、Scala、Dart快速定位其他题目的实现。建议按暴力递归 → 记忆化 → 自底向上 → 数学法的顺序亲手实现一遍体会同一种最优子结构在不同范式下的表达差异。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 343 Integer Break 整数拆分全解：从暴力递归到数学最优解的七种思路
LeetCode 343 Integer Break 整数拆分全解从暴力递归到数学最优解的七种思路【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 articles/integer-break.md 讲解文档展开围绕 LeetCode 343Integer 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在两种选择中取最大值使用因子ii * dfs(num - i, i)跳过因子idfs(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枚举拆分点i1到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的数组dpdp[1] 1对每个num2到n初始化dp[num]为num若num n则为0对每个i1到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。对很小的nn 3则需要特判。算法若n 3返回n - 1因为必须至少拆一次2 → 1×1 13 → 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. 递归有界背包重复取因子 iO(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循环乘 3O(n)O(1)7. 数学最优公式直接计算O(log n)O(1)常见陷阱Common Pitfalls陷阱一忘记原始数字必须被拆分最常见的错误是允许原始输入n保持不拆。题目要求k 2即至少拆分一次因此直接返回n本身是非法答案。正确做法是在基准初始化处强制原始数字至少拆一次同时仍允许子问题直接使用自身值——这正是所有解法中res 0 if num n else num这一行存在的原因。陷阱二错误处理小数值nn 2和n 3是特殊情况对它们执行拆分得到的乘积反而比保持原样更小。例如n 2拆成1 × 1 1但题目强制必须拆所以答案就是 1n 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 的多语言实现散落在仓库各目录中可作为对照阅读与提交验证的参考C 实现自底向上 DPJava 实现数学法C 实现自底向上 DP内层只枚举一半Kotlin 实现四种解法DP、DFS记忆化、数学法、O(1) 公式法仓库 README.md 中维护了完整的题解索引表可以按语言Python、Java、JavaScript、C、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C、Scala、Dart快速定位其他题目的实现。建议按暴力递归 → 记忆化 → 自底向上 → 数学法的顺序亲手实现一遍体会同一种最优子结构在不同范式下的表达差异。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考