322. Coin Change

Posted on Mar 24, 2025

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]
    }
}