322. Coin Change
Solution
背包問題
Implementation
class Solution {
fun coinChange(coins: IntArray, amount: Int): Int {
val dp = IntArray(amount + 1) { -1 }
dp[0] = 0
for (value in 1..amount) {
for (coin in coins) {
val prev = value - coin
if (prev < 0 || dp[prev] == -1) continue
dp[value] = if (dp[value] == -1) dp[prev] + 1 else min(dp[value], dp[prev] + 1)
}
}
return dp[amount]
}
}