コイン交換問題とは？
コイン交換(Coin Change)は、決まったコインの種類で目標金額を作るのに必要な最小コイン枚数を求める問題です(各コインは何度でも使える)。お釣り計算の一般化で、動的計画法の入門問題としてよく出ます。
核心の一行: 「金額aの答えは、それより小さい金額の答えから作られる」。 小さい金額から順に積み上げます。
なぜグリーディでは解けないのか
「大きいコインから欲張る」グリーディはコイン体系によっては間違えます。
コイン {1, 3, 4} で金額6を作ると
- •グリーディ: 4 + 1 + 1 = 3枚
- •最適: 3 + 3 = 2枚
このようにグリーディが崩れる場合があるため、全ての可能性を考えるDPが必要です。
状態定義と漸化式
dp[a] = 金額aを作るのに必要な最小コイン枚数。
各コイン c を最後にもう1枚使うと見ると
dp[a] = min( dp[a - c] + 1 )(全てのコインc、a ≥ c)
基底: dp[0] = 0(0円はコイン0枚)。
動作原理
ステップ1. dp[0] = 0、残りは「到達不可」を表す大きな値(∞)にします。
ステップ2. 金額aを1から目標まで増やし、各コインcについて dp[a-c] + 1 が小さければ更新します。
ステップ3. dp[target] が答えです。まだ∞ならそのコインでは作れない(-1を返す)という意味です。
AlgoNoteの可視化は、金額が大きくなるにつれ各マスがどのコインを足して埋まるかをステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(金額 × コイン数) |
| 空間 | O(金額) |
例で追ってみる
コイン {1, 3, 4}、目標6。
- •dp[1]=1, dp[2]=2, dp[3]=1(コイン3)
- •dp[4]=1(コイン4), dp[5]=2(4+1), dp[6]=2(3+3)
dp[6] = 2 が答えです。
よくあるミス
- •到達不可の扱い: ∞に1を足して比較するとオーバーフロー/誤答になり得るので、更新前に
dp[a-c]が∞かを確認します。 - •最小枚数 vs 場合の数の混同: 「作る方法の数」は漸化式が異なります(コインのループを外側に置き重複組合せを防ぐ)。
- •基底の欠落:
dp[0] = 0を忘れると全て到達不可になります。
AlgoNoteで直接確認しましょう
小さい金額から表が埋まり、各金額でどのコインを足すと最小になるかをAlgoNoteでステップごとに確認できます。