LeetCode 343. 整数拆分

约 4 分钟
文章信息 14 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 20-50 腾讯 字节 亚马逊 美团 百度 滴滴 商汤 猿辅导
标签
动态规划 数学

题目描述

✅ 343. 整数拆分

image-20260928201345416

题意分析

把整数 n 写成至少两个正整数之和，使这些正整数的乘积最大，返回最大乘积。每一部分都必须大于零，拆成多少部分可以自行决定，不能把完全不拆的 n 直接当成答案。

题目给定 2 <= n <= 58，枚举较小整数的最优拆分足以满足范围。关键是区分“某部分保持完整”和“某部分继续拆分”，二者可能产生不同的乘积。

解法：动态规划枚举第一段

核心思路

[!blue]

定义 dp[i] 为把整数 i 至少拆成两部分后能得到的最大乘积。状态里不包含保持整个 i 不拆的情况，这个约定直接决定了转移需要比较哪些候选。

任意一个合法拆分，都可以先拿出其中一个完整部分，记为 j，其余部分的和就是 i - j。枚举 1 <= j < i，剩余部分有两种选择：保持完整，得到 j * (i - j)；继续拆成至少两部分，得到 j * dp[i - j]。两者取最大，再在所有 j 中取最大，就是 dp[i]。

不需要再单独拆开 j，因为它被定义为最终方案中拿出来的一整部分。任何方案总能选出这样一部分，其余部分要么只有一段，要么由更小规模的最优状态覆盖。因此这两类选择能覆盖所有合法拆法；同一方案被重复枚举也不会影响取最大值。

从 i = 2 向上计算时，依赖的 dp[i - j] 下标一定更小，已经计算完。dp[1] = 0 表示正整数 1 无法继续拆成两个正数，但保留余数不拆的候选仍然有效，因此不会遗漏含有 1 的合法方案。所有转移都已拿出 j 和一个正的剩余部分，保证最终答案至少拆了两段。

解题步骤

  1. 创建长度为 n + 1 的 dp，初始值为零。
  2. 从 i = 2 到 n 依次计算，每次枚举第一部分 j，范围为 [1, i - 1]。
  3. 分别计算 j * (i - j) 与 j * dp[i - j]，对应剩余部分不拆和继续拆。
  4. 用这两个候选更新 dp[i]，最终返回 dp[n]。

代码实现

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // 固定剪出一段后，剩余部分可以保持完整，也可以继续拆分。
                int noSplit = j * (i - j);
                int split = j * dp[i - j];

                dp[i] = Math.max(dp[i], Math.max(noSplit, split));
            }
        }

        return dp[n];
    }
}

func integerBreak(n int) int {
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        for j := 1; j < i; j++ {
            // 固定剪出一段后，剩余部分可以保持完整，也可以继续拆分。
            noSplit := j * (i - j)
            split := j * dp[i-j]
            if noSplit > dp[i] {
                dp[i] = noSplit
            }
            if split > dp[i] {
                dp[i] = split
            }
        }
    }
    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(n^2)$。每个 $i$ 枚举 $i-1$ 种第一部分，累加为平方级。
  • 空间复杂度：$O(n)$，保存从较小整数到目标整数的最优拆分值。

关键点总结

[!green]

  • dp[i] 强制表示已经拆分，不能与不拆的整数 i 混为一谈。
  • 枚举一个完整部分，剩余部分同时考虑保持完整和继续拆分。
  • 依赖只指向更小整数，递增计算即可满足顺序。

易错点总结

[!yellow]

  • 只考虑 j * dp[i - j]，会强迫余数继续拆，遗漏只有两部分的方案。
  • 只考虑 j * (i - j)，就只能拆成两部分，无法找到需要更多部分的最优解。
  • 使用 dp[j] * dp[i - j] 会强制两边都继续拆，无法覆盖所有合法拆分。
  • j 必须小于 i，否则剩余部分为零，违反正整数要求。
  • 不能把 dp[i] 初始化为 i，这会把不拆分的非法候选混进答案。

相似题目

题目 难度 关联与区别
剑指 Offer 14- II. 剪绳子 II 中等 最大乘积的拆分规律相同，原题范围更大且要取模，不能把取模后的值直接用于大小比较。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63992688
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！