LeetCode 343 Integer Break 整数拆分全解:从暴力递归到数学最优解的七种思路

原创2026-09-17 14:38:311,994 阅读
文章标签:示例工程教程

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 必须至少拆一次。

算法

  1. 定义递归函数 dfs(num),返回从 num 能得到的最大乘积;
  2. 基准情况:num == 1 时返回 1;
  3. 若 num 等于原始输入 n,结果初始化为 0(必须拆分);否则 num 本身就是一个合法选项;
  4. 枚举所有拆分点 i(从 1 到 num - 1),计算 dfs(i) * dfs(num - i) 并保留最大值;
  5. 返回最大乘积。
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。通过允许同一个值被重复取用,所有组合被更高效地探索。

算法

  1. 定义 dfs(num, i),num 是剩余值,i 是当前允许使用的最大因子;
  2. 基准情况:num 或 i 为 0 时返回 1;
  3. 若 i > num,把 i 缩小为 num;
  4. 在两种选择中取最大值:
    • 使用因子 i:i * dfs(num - i, i);
    • 跳过因子 i:dfs(num, i - 1);
  5. 入口调用 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 只计算一次、之后直接复用,冗余工作被消除。

算法

  1. 建立哈希表 dp,基准 dp[1] = 1;
  2. 定义 dfs(num):
    • 若 num 已在 dp 中,直接返回缓存值;
    • 初始化 dp[num]:num == n 时为 0,否则为 num;
    • 枚举拆分点 i(1 到 num - 1),用 max(dp[num], dfs(i) * dfs(num - i)) 更新;
    • 返回 dp[num];
  3. 调用 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 两个维度组成,避免不同递归路径上相同状态被重复计算。

算法

  1. 建立二维记忆表 dp[num][i],初始化为 -1;
  2. 定义 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];
  3. 调用 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 的每个数字,枚举所有拆分方式,组合之前已算好的结果。

算法

  1. 建立长度 n + 1 的数组 dp,dp[1] = 1;
  2. 对每个 num(2 到 n):
    • 初始化 dp[num] 为 num(若 num == n 则为 0);
    • 对每个 i(1 到 num - 1),执行 dp[num] = max(dp[num], dp[i] * dp[num - i]);
  3. 返回 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)则需要特判。

算法

  1. 若 n <= 3,返回 n - 1(因为必须至少拆一次,2 → 1×1 = 1,3 → 1×2 = 2);
  2. 反复从 n 中减去 3 并让结果乘 3,直到 n <= 4;
  3. 把最终余数(只能是 2、3 或 4)乘进结果;
  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。

算法

  1. 若 n <= 3,返回 n - 1;
  2. 计算 res = 3^(n / 3);
  3. 若 n % 3 == 1,返回 (res / 3) * 4;
  4. 若 n % 3 == 0,返回 res;
  5. 否则返回 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)快速定位其他题目的实现。建议按"暴力递归 → 记忆化 → 自底向上 → 数学法"的顺序亲手实现一遍,体会同一种最优子结构在不同范式下的表达差异。

登录后查看全文
leetcode