LeetCode 343. 整數拆分：數學規律與貪心策略 O(1) 解法

LeetCode 343. 整數拆分：數學規律與貪心策略 O(1) 解法

題目： 給定正整數 n (n ≥ 2)，將其拆分為 至少兩個 正整數之和，使乘積最大化。返回最大乘積。

示例： n=2 → 1 (1+1)；n=10 → 36 (3+3+4)

一、 核心數學洞察：盡可能多地拆分為 3

證明直覺 (實數域 → 整數域)

1. 對於實數 x > 0，拆分為 e (≈2.718) 乘積最大 (微積分極值)。
2. 整數域中，最接近 e 的是 3 (其次是 2)。
3. 4 = 2+2，乘積 2×2=4 不變，可拆可不拆。
4. 5 = 3+2，乘積 6 > 5，必拆。
5. 6 = 3+3 (9) > 2+2+2 (8)，3 優於 2。
6. n ≥ 5 時，拆出 3 總是優於拆出 2 或保留 (因 3×(n-3) ≥ 2×(n-2) 當 n≥5)。

最優拆分策略

• 盡可能多拆 3。
• 餘數處理：
  • 餘 0：全 3 (如 9 = 3+3+3)。
  • 餘 1：換一個 3 成兩個 2 (即 3+1 → 2+2)，因 3×1 < 2×2 (如 10 = 3+3+4)。
  • 餘 2：保留一個 2 (如 8 = 3+3+2)。
• 特例：n=2 → 1×1=1；n=3 → 2×1=2 (題目要求至少拆兩個，故 3 不能不拆)。

二、 O(1) 數學公式解法 (推薦)

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        int quotient = n / 3;
        int remainder = n % 3;
        
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            // 3+1 → 2+2，少一個 3，多兩個 2
            return (int) Math.pow(3, quotient - 1) * 4;
        } else { // remainder == 2
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

複雜度

• 時間： O(log n) — Math.pow 對數時間 (或視為 O(1) 硬件指令)。
• 空間： O(1)。

三、 遞歸/動態規劃解法 (理解最優子結構)

狀態定義

dp[i] 表示整數 i 拆分後的最大乘積 (i ≥ 2)。

轉移方程

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

• j * (i-j)：直接拆成兩塊不再拆。
• j * dp[i-j]：拆成兩塊，第二塊繼續最優拆分。

代碼

class Solution {
    public 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];
    }
}

複雜度

• 時間 O(n²)，空間 O(n) — 適合理解問題結構，非最優解。

四、 貪心迭代解法 (無數學公式直覺時的工程寫法)

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        int product = 1;
        while (n > 4) { // n=4 時 2+2=4 不再拆分獲利
            product *= 3;
            n -= 3;
        }
        product *= n; // 剩餘 n (2, 3, 或 4) 直接相乘
        return product;
    }
}

邏輯等價於數學公式，循環拆 3，剩餘 2/3/4 直接乘入。代碼簡潔，無 Math.pow 精度擔憂。

五、 關鍵測試用例驗證

六、 總結與舉一反三

1. 數學建模能力： 將離散優化問題映射到連續函數極值 (e)，再回映整數域 (3)。
2. 貪心選擇性質： 局部最優 (拆 3) 能推導出全局最優，無需 DP 狀態轉移。
3. 邊界處理藝術： n=2,3 特例、餘 1 時「借 3 換 2+2」、循環終止條件 n > 4。
4. 同類題： LeetCode 343 (本題)、LeetCode 96 (不同二叉搜索樹 - 卡特蘭數)、剪繩子 (劍指 Offer 14/14-II)。

掌握「盡可能拆 3，餘 1 換 2+2」的核心規律與 O(1) 實現，不僅能秒殺此題，更能培養從數學本質穿透算法表象的核心競爭力。