題目描述:給定一個整數陣列 coins(硬幣面值)以及一個整數 amount(目標金額),請計算湊出 amount 的組合數(每種硬幣可無限使用)。若無法湊出,回傳 0。
解題思路:
本題是**無界背包(Unbounded Knapsack)**的經典應用,求的是「組合數」而非「最少硬幣數」。
定義 dp[j] 為湊出金額 j 的組合數,初始值 dp[0] = 1(空集合可以湊出金額 0)。
關鍵觀察:為了避免重複計算排列(例如 [1,2] 和 [2,1] 只算一次),我們需要把硬幣放在外層迴圈,金額放在內層迴圈。這樣每枚硬幣被考慮時,之前的 dp 狀態都只包含更早處理過的硬幣,確保不會重複計算同一組合的不同排列。
轉移方程:對每枚硬幣 coin,遍歷 j 從 coin 到 amount:
dp[j] += dp[j - coin]
這表示「若使用當前這枚硬幣,剩餘金額 j - coin 的組合數直接累加進來」。由於是從左往右更新,同一枚硬幣可以被使用多次(無界)。
範例:coins = [1, 2, 5],amount = 5
dp = [1, 0, 0, 0, 0, 0]dp = [1, 1, 1, 1, 1, 1]dp = [1, 1, 2, 2, 3, 3]dp = [1, 1, 2, 2, 3, 4]dp[5] = 4時間複雜度:O(n × amount) — 其中 n 為硬幣種數,對每枚硬幣都遍歷所有金額一次。
空間複雜度:O(amount) — 只需一維 DP 陣列,長度為 amount + 1。
1. Initialize dp array of size (amount + 1) with all zeros.
2. Set dp[0] = 1 (base case: empty combination sums to 0).
3. For each coin in coins:
a. For j from coin to amount (inclusive):
- dp[j] += dp[j - coin]
4. Return dp[amount].二維 DP O(n × amount):使用 dp[i][j] 表示前 i 種硬幣湊出金額 j 的組合數。轉移:dp[i][j] = dp[i-1][j] + dp[i][j-coin_i](不選或選當前硬幣)。空間複雜度 O(n × amount),邏輯更直觀但記憶體使用較多。
遞迴 + 記憶化 O(n × amount):對每個 (index, remaining) 做 DFS,嘗試不選當前硬幣(index+1)或選當前硬幣(remaining-coin),用 hash map 或二維陣列快取結果。效果與迭代 DP 相同,但函數呼叫開銷較大。
amount 非常大但硬幣種數很少時,有沒有比 O(n × amount) 更快的方法(例如數學或矩陣快速冪)?