343. 整数拆分（Integer Break）

频次 ★★★ · 难度 🟡 · 高频：字节/腾讯

题目

给定正整数 n，拆分为至少两个正整数的和，使乘积最大，返回最大乘积。

示例：

输入: n = 10
输出: 36  （10 = 3+3+4, 3×3×4 = 36）

思路

两种解法：

解法 1：DP — dp[i] 表示 i 拆分后的最大乘积。dp[i] = max(j*(i-j), j*dp[i-j]) 对所有 j = 1..i-1。

• j*(i-j)：拆成两段，不再拆
• j*dp[i-j]：j 乘以 (i-j) 继续拆的最大值

解法 2：数学 — 尽量拆成 3（最优），余 1 时拆成 2×2（因为 2×2 > 3×1）。

代码

// 解法 1：DP
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;                         // 1 不能拆，dp[1] 用于后续计算
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}
 
// 解法 2：数学贪心 O(1)
public int integerBreak(int n) {
    if (n <= 3) return n - 1;          // 2→1, 3→2
    int q = n / 3, r = n % 3;
    if (r == 0) return (int) Math.pow(3, q);
    if (r == 1) return (int) Math.pow(3, q - 1) * 4;  // 拿一个 3 和 1 凑成 2×2
    return (int) Math.pow(3, q) * 2;    // r == 2
}

复杂度

• DP：时间 O(n²)，空间 O(n)
• 数学：时间 O(1)，空间 O(1)

边界条件

• n = 2：返回 1（1+1）
• n = 3：返回 2（1+2）
• n ≥ 4 时贪心拆 3 生效

变式

• 剑指 Offer 14-I. 剪绳子：同题
• 剑指 Offer 14-II：大数取模，需用快速幂

易错点

• dp[1]=1 是基值（虽然 1 不能拆），但不影响 n≥2 的结果
• 数学方法中 n≤3 的情况特殊处理（必须拆成至少两段，乘积反而更小）
• 余 1 时，不能直接 3^q × 1，应该 3^(q-1) × 4（2×2 > 3×1）

面试追问

• 为什么拆 3 最优？ 用均值不等式 + 求导：对 e 取整，3 最近。拆 4 等价于 2×2（乘积相同），拆 5 不如 3×2
• DP 和数学方法哪个更好？ 数学方法 O(1) 但需要证明；面试中先写 DP 再提数学优化

关联题

• 同套路：279. 完全平方数 —— 完全背包求最值
• 进阶：322. 零钱兑换 —— 贪心不总是最优，DP 保底
• 知识点：DP vs 数学贪心见动态规划