給定不同面額的硬幣陣列
coins和一個目標金額amount，求湊成該金額所需的最少硬幣數。如果無法湊成，回傳 -1。每種硬幣數量無限。
Example:
Input: coins = [1,2,5], amount = 11 Output: 3
Intuition
TIP
完全背包問題：對每個金額，嘗試每種硬幣，取使用最少硬幣數的方案。
dp[i]= 湊成金額i的最少硬幣數- 對每種硬幣
c：dp[i] = min(dp[i], dp[i - c] + 1) - 初始化
dp[0] = 0，其餘為正無窮
Approaches
1. Top-Down Memoization — O(amount * coins.size) / O(amount)
- Idea: 遞迴嘗試每種硬幣，記憶化避免重複計算
- Time:
O(amount * coins.size) - Space:
O(amount)
class Solution {
fun coinChange(coins: IntArray, amount: Int): Int {
val memo = IntArray(amount + 1) { -2 }
fun dp(rem: Int): Int {
if (rem == 0) return 0
if (rem < 0) return -1
if (memo[rem] != -2) return memo[rem]
var best = Int.MAX_VALUE
for (c in coins) {
val res = dp(rem - c)
if (res in 0 until best) best = res + 1
}
memo[rem] = if (best == Int.MAX_VALUE) -1 else best
return memo[rem]
}
return dp(amount)
}
}⭐ 2. Bottom-Up DP — O(amount * coins.size) / O(amount)
- Idea: 從金額 1 到
amount依序填表，每次嘗試所有硬幣面額 - Time:
O(amount * coins.size) - Space:
O(amount)
class Solution {
fun coinChange(coins: IntArray, amount: Int): Int {
val dp = IntArray(amount + 1) { amount + 1 }
dp[0] = 0
for (i in 1..amount) {
for (c in coins) {
if (c <= i) {
dp[i] = minOf(dp[i], dp[i - c] + 1)
}
}
}
return if (dp[amount] > amount) -1 else dp[amount]
}
}🔑 Takeaways
- Pattern: 完全背包 — 每個物品可以無限次使用，求最優解
- Key trick: 用
amount + 1作為「不可達」的初始值，比用Int.MAX_VALUE更安全（不會溢位）