整数拆分 图解题解

整数拆分这道题到底要最大化什么

给一个正整数 n，把它拆成至少两个正整数相加 n=a1+a2+…+ak（k≥2），让这些数的乘积 a1×a2×…×ak 最大，返回这个最大乘积。题面例子 n=10，最好的拆法是 3+3+4，乘积 3×3×4=36，就是答案。这里必须拆成两段以上，不能原样留一个 n 不动。

为什么枚举所有拆法会指数爆炸

最直接的想法是把所有拆法都列出来比乘积。可 n 能拆成两段、三段、更多段，每段还能取不同大小，方案随 n 指数级膨胀，稍大就列不完。而且很多拆法共用同一截尾巴——拆 10 时剩下的 8 怎么拆，和单独拆 8 是同一个子问题，被反复重算。把「拆 i 能得的最大乘积」算一次存下来复用，指数枚举就压成动态规划（把子问题算过的结果存下、后面直接取用）。

dp[i] 定成什么，dp[1] 为什么要设 1

定义 dp[i] 为「把整数 i 拆成至少两段能得到的最大乘积」，答案就是 dp[n]。下标 i 是被拆的数、格子里存它拆开后的最大积。开头 dp[1]=1 是个约定：1 没法再拆成两个正整数，本不该有值，但它会在别人「续拆」时被当乘数用，设成 1 表示「乘上这一段不改变积」。别把 dp[1] 设成 0，否则任何用到它的续拆方案都会被乘成 0，整条转移崩掉。

为什么每格要在拆到底和再拆一次之间取大

算 dp[i] 时枚举第一段取多大，记作 j，从 1 扫到 i-1。第一段定成 j 之后，剩下的 i-j 有两条路：一是就让它整段留着不再拆，这段贡献是 i-j 本身，得 j×(i-j)；二是把 i-j 也拆到最优，贡献是 dp[i-j]，得 j×dp[i-j]。两条取大、再对所有 j 取大，就是 dp[i]=max(j×(i-j), j×dp[i-j])。

为什么非得留「不拆」这一路？因为 dp[i-j] 是「至少拆两段」的积，有时反而更小。比如剩下 3，拆成 1+2 积才 2，还不如整个 3 留着。少了 j×(i-j) 这支，小段被强行拆开就会算亏。

拿 n=10 亲手把这张 dp 表填一遍

从小往大填。dp[1]=1 打底，dp[2] 只能 1+1 得 1。dp[3] 整段留着 1×2=2 胜过续拆。dp[4] 第一段取 2，2×2=4。dp[5] 第一段取 2，2×3=6。dp[6] 第一段取 3，3×3=9。到 dp[7] 续拆更划算，第一段 2 接续拆的 2×dp[5]=2×6=12。dp[8] 得 2×dp[6]=2×9=18，dp[9] 得 3×dp[6]=3×9=27，dp[10] 得 2×dp[8]=2×18=36。dp[10]=36，正是 3+3+4 那组，和题面对上。

复杂度是多少，n=2 和 n=3 两个边界怎么收

外层枚举被拆的数 i、内层枚举第一段 j，两层循环 O(n²)；一维 dp 数组 O(n) 空间。两个小边界要想清：n=2 只能拆 1+1，dp[2]=1，别被「乘积该更大」的直觉带偏；n=3 最优是 1+2 得 2，不是硬凑更多段。还有内层 j 只能取到 i-1，得保证至少拆成两段，写成取到 i 就等于允许「原样不拆」，会把 dp[i] 顶成 i 而算错。

Python

def integerBreak(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        for j in range(1, i):
            dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
    return dp[n]

C++

int integerBreak(int n){
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            dp[i] = max({dp[i], j * (i - j), j * dp[i - j]});
    return dp[n];
}

Java

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