整数拆分如何用动态规划求最大乘积？为什么要比较拆与不拆？

简化版

整数拆分用 dp[i] 表示把整数 i 拆分后能得到的最大乘积。枚举第一段长度 j，另一段 i-j 可以继续拆，也可以不拆，所以转移是 dp[i] = max(dp[i], j * (i-j), j * dp[i-j])。

详细版

这题的陷阱在于题目要求至少拆成两个正整数，但递归子问题里的剩余部分不一定继续拆更好。例如拆 4 时，2*2 比 2*dp[2] 更好，因为 dp[2]=1。所以枚举 j 后，要同时比较“剩余部分不拆”和“剩余部分继续拆”。

从小到大计算 dp[2] 到 dp[n]。时间复杂度 O(n²)，空间复杂度 O(n)。面试中也可以提到数学贪心：尽量拆成 3，但 DP 更通用，也更容易解释边界。

完整版教学

一、为什么这题不能只写普通乘法

给定 n=10，最优拆法是 3+3+4，乘积是 36。如果只拆成两段，可能错过更多段组合；如果一直拆到最小，也可能把乘积拆小。

10 = 5 + 5 => 25
10 = 3 + 3 + 4 => 36

动态规划要解决的是：每个整数拆到什么程度最划算。

二、状态定义和“至少拆一次”的边界

定义：

dp[i] = 整数 i 至少拆分成两个正整数后，可以得到的最大乘积

边界里 dp[2]=1，因为 2=1+1。但注意，子问题中的某一段可以选择不继续拆。这个语义差异是本题最容易混淆的地方。

例如处理 4：

2 + 2
不继续拆：2 * 2 = 4
继续拆右边：2 * dp[2] = 2

所以不能只用 j * dp[i-j]。

三、转移为什么要比较拆与不拆

枚举第一段 j，剩余部分是 i-j。剩余部分有两种选择：

不拆：j * (i - j)
继续拆：j * dp[i - j]

取最大值：

dp[i] = max(dp[i], j * (i - j), j * dp[i - j])

候选	含义	什么时候有用
`j * (i-j)`	只拆成两段	剩余段直接参与乘积更大
`j * dp[i-j]`	剩余段继续拆	多段乘积更大

这张表就是面试解释的核心。

四、用 n=10 推演几个关键值

先算小值：

dp[2] = 1
dp[3] = max(1*2, 1*dp[2]) = 2
dp[4] = max(1*3, 1*dp[3], 2*2, 2*dp[2]) = 4

继续往上：

dp[8] = 18  // 3+3+2
dp[10] = 36 // 3+3+4

你会发现 3 经常出现，这是因为从数学角度看，拆成尽量多的 3 通常乘积最大。但 DP 不依赖这个定理。

五、代码模板

int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[2] = 1;
    for (int i = 3; 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];
}

循环 j < i 是为了保证两段都是正整数。实际可以枚举到 i/2，因为乘法对称，但完整枚举更直观。

六、DP 和数学贪心怎么对比

数学解法通常说尽量拆成 3，余数为 1 时把 3+1 改成 2+2。例如：

10 = 3 + 3 + 4 => 36
8 = 3 + 3 + 2 => 18

解法	优点	风险
动态规划	通用、容易推导	`O(n²)`
数学贪心	`O(1)` 或 `O(n/3)`	需要证明，面试解释要求更高

记忆钩子：整数拆分 DP 的关键不是“拆”，而是每一段都要问“继续拆是否更赚”。

七、常见误区与追问

误区：只写 j * dp[i-j]。 这样会漏掉剩余部分不拆更优的情况。
误区：把 dp[1] 当成 1 后随意转移。 题目要求至少拆一次，状态语义要保持清楚。
误区：认为拆得越碎越好。 4 拆成 2+2 得 4，比 1+1+1+1 得 1 好得多。
追问：为什么 3 很特殊？ 从数学上看，当拆分因子接近自然常数 e 时乘积更大，整数里 3 最合适。
追问：能不能空间优化？ 这题每个 i 可能依赖很多更小状态，数组保留更自然。
追问：为什么 n=2 返回 1？ 因为必须拆成 1+1，不能直接返回 2。

八、加强记忆

整数拆分的记忆链是：dp[i] 表示至少拆一次的最大乘积，枚举第一刀 j，剩余部分既可以不拆成 i-j，也可以继续拆成 dp[i-j]。所以公式里必须同时出现 j*(i-j) 和 j*dp[i-j]。这道题面试最看重状态语义，语义讲清楚，代码就很短。

简化版

详细版