518. Coin Change II

Medium

Description

給定不同面額的硬幣陣列 coins 和一個總金額 amount，回傳湊成該金額的組合數。每種硬幣可以無限次使用。若無法湊成則回傳 0。

Example:

Input: amount = 5, coins = [1,2,5] Output: 4 (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)

Intuition#

完全背包問題：外層遍歷硬幣、內層遍歷金額，確保計算的是「組合數」而非「排列數」。

這是經典的完全背包（Unbounded Knapsack）問題
dp[j] 代表湊成金額 j 的組合數
外層遍歷硬幣（保證每種組合只計算一次），內層從 coin 到 amount
轉移方程：dp[j] += dp[j - coin]

Approaches#

1: 2D DP Table#

概念: dp[i][j] 代表用前 i 種硬幣湊成金額 j 的組合數。對每種硬幣，要麼不用（dp[i-1][j]），要麼用一枚（dp[i][j-coin]）。
時間複雜度: O(n * amount)，n 為硬幣種類數
空間複雜度: O(n * amount)

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val n = coins.size
        val dp = Array(n + 1) { IntArray(amount + 1) }
        for (i in 0..n) dp[i][0] = 1
        for (i in 1..n) {
            for (j in 0..amount) {
                dp[i][j] = dp[i - 1][j]
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]]
                }
            }
        }
        return dp[n][amount]
    }
}

⭐2: 1D DP（空間優化）#

概念: 壓縮為一維，外層遍歷硬幣，內層正向遍歷金額（因為同一種硬幣可重複使用）。
時間複雜度: O(n * amount)
空間複雜度: O(amount)

class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val dp = IntArray(amount + 1)
        dp[0] = 1
        for (coin in coins) {
            for (j in coin..amount) {
                dp[j] += dp[j - coin]
            }
        }
        return dp[amount]
    }
}

🔑 Takeaways#

Pattern: 完全背包 — 外層遍歷物品、內層正向遍歷容量
關鍵技巧: 「組合數」要外層遍歷物品；「排列數」要外層遍歷金額。這個順序差異是背包問題的經典考點