LeetCode 343. 整数拆分

2026-06-04 HGNULB 约 4 分钟

文章信息 14 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决需加强 20-50 字节跳动美团腾讯猿辅导百度滴滴商汤亚马逊

题目描述

✅ 343. 整数拆分

题意分析

给一个正整数 n，把它拆成至少两个正整数之和，求这些数乘积的最大值。「至少两个」是硬约束：即使不拆的乘积更大，也不允许把 n 原样交上去。

这条约束在小数据上直接决定答案。n = 2 只能拆成 1 + 1，乘积是 1，比 2 本身还小；n = 3 只能是 1 + 2 或 1 + 1 + 1，最大乘积是 2，同样小于 3。因此 2 和 3 是两个必须单独确认的边界，任何「先看能不能不拆」的写法都会在这里翻车。

另一个信号是数据范围很小（n 不超过 58），平方级的算法完全跑得动，说明本题的重点不在效率，而在状态定义和转移是否严谨。至于拆出来的数是否可以重复、顺序是否有区别——都不影响乘积，因此只需关心「拆成了哪些数」这个多重集合，不必考虑排列。

解法：动态规划枚举最后一次拆分

核心思路

定义 dp[i] 为把整数 i 至少拆成两段后能得到的最大乘积。枚举第一段 j，剩余的 i-j 有两种选择：不再拆，乘积为 j * (i-j)；继续拆，乘积为 j * dp[i-j]。因此

$dp[i] = \max_{1 \le j < i}\left{j(i-j),\;j \cdot dp[i-j]\right}$

两个候选缺一不可，因为 dp[i-j] 的定义强制继续拆，不包含“保持 i-j 原样”。按 i 从小到大计算时，转移依赖的状态都已得到最优值。任意合法拆分都能按第一段 j 归入上述两种情况之一，反过来每个候选也对应合法拆分，所以枚举取最大不会漏解。

解题步骤

创建长度为 n+1 的 dp 数组，保留默认的 dp[0]=dp[1]=0。

从 i=2 到 n 递增计算，保证 dp[i-j] 已知。

枚举 j 从 1 到 i-1，分别计算“剩余部分不拆”和“继续拆”的乘积。

用两个候选更新 dp[i]，最终返回 dp[n]。

例如 n=10 时，前面的状态依次得到 dp[2..7]=1,2,4,6,9,12；计算 dp[10] 时，j=3 给出 3 * dp[7] = 36，对应 3+3+4，这是最大值。

代码实现

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)$，使用一维 dp 数组保存所有较小规模的答案。

关键点总结

状态定义强调“必须拆”，因此转移必须同时考虑 i-j 保持原样和继续拆分。

dp[i] 只依赖更小下标，按规模递增即可满足依赖顺序。

枚举第一段能覆盖所有拆法；乘法满足交换律，因此重复枚举不影响最大值。

面试时先用 n=2、n=3 校验强制拆分边界，再写状态和转移，能避免把 dp[i] 误当成允许不拆。

易错点总结

只写 j * dp[i-j]：n=2 时得到 0，因为余下的 1 不能继续拆。

只写 j * (i-j)：最多只拆成两段，n=10 会得到 25，而正确答案是 36。

写成 dp[j] * dp[i-j]：强迫两边都继续拆，n=3 无法得到合法的 1*2。

允许 j=i：这表示完全没有拆分，违背“至少两个正整数”的题意。

把 dp[i] 初始化为 i：会把“不拆”混入答案，n=3 将错误返回 3。

相似题目

题目	难度	考察点
剑指 Offer 14- I. 剪绳子	中等	与本题同模型，数据范围小，可用来对照 dp 与贪心两种写法
剑指 Offer 14- II. 剪绳子 II	中等	结果需取模导致 dp 的比大小失效，只能走贪心加快速幂