40. Coin Change

読了目安 約2分

DP / LeetCode 322 (Medium) — 金額を作る最小コイン枚数。作れない場合は -1 を返す。

問題

LeetCode 322. Coin Change（Medium / カテゴリ: DP）

コインの額面の配列 coins と金額 amount が与えられます。 各額面は何枚でも使えます。 amount ちょうどを作る最小のコイン枚数を返し、作れない場合は -1 を返してください。 amount が 0 のときの答えは 0 です。

考え方

Swift 実装のポイント

• 「未到達」に Int.max を使うと + 1 でオーバーフローして実行時エラーになります。amount + 1 を番兵にすれば十分です。
• 1...amount は amount が 0 のとき実行時エラーになります。stride(from: 1, through: amount, by: 1) なら空になり安全です。
• 内側は for c in coins where c <= a と書くと、配列の範囲外参照を条件で防げます。

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        let unreachable = amount + 1
        var dp = [Int](repeating: unreachable, count: amount + 1)
        dp[0] = 0
        for a in stride(from: 1, through: amount, by: 1) {
            for c in coins where c <= a {
                dp[a] = min(dp[a], dp[a - c] + 1)
            }
        }
        return dp[amount] == unreachable ? -1 : dp[amount]
    }
}