給定不同面額的硬幣陣列
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
TIP
完全背包問題：外層遍歷硬幣、內層遍歷金額，確保計算的是「組合數」而非「排列數」。
- 這是經典的完全背包（Unbounded Knapsack）問題
dp[j]代表湊成金額 j 的組合數- 外層遍歷硬幣（保證每種組合只計算一次），內層從 coin 到 amount
- 轉移方程：
dp[j] += dp[j - coin]
Approaches
1. 2D DP Table — O(n * amount) / O(n * amount)
- Idea:
dp[i][j]代表用前 i 種硬幣湊成金額 j 的組合數。對每種硬幣，要麼不用（dp[i-1][j]），要麼用一枚（dp[i][j-coin]）。 - Time:
O(n * amount)，n 為硬幣種類數 - Space:
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 (Space Optimized) — O(n * amount) / O(amount)
- Idea: 壓縮為一維，外層遍歷硬幣，內層正向遍歷金額（因為同一種硬幣可重複使用）。
- Time:
O(n * amount) - Space:
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: 完全背包 — 外層遍歷物品、內層正向遍歷容量
- Key trick: 「組合數」要外層遍歷物品；「排列數」要外層遍歷金額。這個順序差異是背包問題的經典考點