343. Integer Break

Medium

Description

給定正整數 n（n >= 2），將它拆分為至少兩個正整數的和，使這些正整數的乘積最大化。回傳最大乘積。

Example:

Input: n = 10 Output: 36

Intuition#

數學上盡量拆成 3 是最優的；DP 上對每個數嘗試所有可能的第一刀位置。

dp[i] = 把 i 拆分後能得到的最大乘積
對每個 j (1 到 i-1)，可以選擇繼續拆 i-j 或不拆
狀態轉移：dp[i] = max(j * (i-j), j * dp[i-j]) for all j
數學解法：盡量拆成 3，因為 3 的分解效率最高

Approaches#

1: Bottom-Up DP#

概念: 對每個數嘗試所有切割位置，取最大乘積
時間複雜度: O(n^2)
空間複雜度: O(n)

class Solution {
    fun integerBreak(n: Int): Int {
        val dp = IntArray(n + 1)
        dp[1] = 1
        for (i in 2..n) {
            for (j in 1 until i) {
                dp[i] = maxOf(dp[i], j * (i - j), j * dp[i - j])
            }
        }
        return dp[n]
    }
}

⭐2: Math (Greedy with 3s)#

概念: 盡量拆成 3，餘 1 時改用 2+2，餘 2 時保留
時間複雜度: O(1)
空間複雜度: O(1)

class Solution {
    fun integerBreak(n: Int): Int {
        if (n == 2) return 1
        if (n == 3) return 2
        var result = 1
        var rem = n
        while (rem > 4) {
            result *= 3
            rem -= 3
        }
        return result * rem
    }
}

🔑 Takeaways#

Pattern: 最優分割 DP — 嘗試所有分割點，子問題可以選擇繼續分或不分
關鍵技巧: 數學上 e ≈ 2.718 是最優分割因子，離散化後 3 最佳；注意 dp[i] 的含義是「拆分後的最大乘積」，而 j * (i-j) 考慮的是不再拆分 i-j 的情況