コイン両替最小枚数｜コードで実践

コイン両替最小枚数

このレッスンで分かること

1 つ目は dp[0] = 0 を忘れる

動的計画法の応用編、コイン両替 問題に挑みます

この問題が面白いのは、フィボナッチや階段問題と違って 遷移先が複数ある ことです

コイン両替最小枚数とは

額面の決まったコインで指定金額を作る最小枚数を DP で求める。状態遷移を「複数選択肢の min」で書く感覚を身につける。

動的計画法の応用編、コイン両替 問題に挑みます。利用できるコインの額面リスト coins (例: [1, 2, 5]) と作りたい金額 amount が与えられたとき、amount ちょうどを作るのに必要なコインの 最小枚数 を求めます。両替できない場合は -1 を返します。

この問題が面白いのは、フィボナッチや階段問題と違って 遷移先が複数ある ことです。amount を作るとき、最後に使ったコインが coins のどれかは事前には分かりません。だからこそ すべての候補を試して最小を取る という DP の典型パターンを学べます。

どのコインを最後に使うかは分からない。全部試して min を取れば良い。これが DP の典型パターン。

漸化式を導く

dp[i] を「金額 i を作るのに必要な最小コイン枚数」と定義します。基底ケースは dp[0] = 0 (0 円を作るには 0 枚)。それ以外の i について、最後に使ったコイン c が coins の中のどれかなので、

dp[i] = min(dp[i - c] + 1) (c は coins の各要素、ただし i >= c)

で計算できます。+ 1 は最後のコイン 1 枚分です。dp[i - c] が 不可能 (-1 もしくは無限大) なら、その候補は無視します。すべての候補が無理なら dp[i] 自体が 不可能 です。

diagram (will load when visible)

図のポイント (テキスト併記)

コインが [1, 2, 5] のとき、dp[i] は dp[i-1]+1、dp[i-2]+1、dp[i-5]+1 の 最小値 になります

コインが [1, 2, 5] のとき、dp[i] は dp[i-1]+1、dp[i-2]+1、dp[i-5]+1 の 最小値 になります。これがコイン両替 DP の核です。

不可能を表す番兵には float('inf') (Python) や Number.MAX_SAFE_INTEGER (JS) を使うと、min が自然に効く。

Python での実装

Python

def coinChange(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return dp[amount] if dp[amount] != INF else -1

dp を INF で初期化し、dp[0] = 0 だけ確定値を入れます。あとは i = 1 から amount まで全部のマスを埋めていきます。各マスでは coins の全要素を試し、より小さい値があれば更新する、というシンプルな二重ループです。最後に dp[amount] が INF のままなら、両替不可能を意味する -1 を返します。

JavaScript での実装

JavaScript

function coinChange(coins, amount) {
  const INF = Number.MAX_SAFE_INTEGER;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (i >= c && dp[i - c] + 1 < dp[i]) {
        dp[i] = dp[i - c] + 1;
      }
    }
  }
  return dp[amount] === INF ? -1 : dp[amount];
}

JavaScript も全く同じロジック。Number.MAX_SAFE_INTEGER を INF 代わりに使います。Infinity は加算しても Infinity のままなので番兵として安全に機能します。MAX_SAFE_INTEGER を使う場合は +1 で安全整数範囲を超えることに注意が必要です。

よくある間違い

1 つ目は dp[0] = 0 を忘れる。基底ケースを設定しないと、すべての dp[i] が INF のままになって -1 を返してしまいます。2 つ目は amount を作れないケースの判定。dp[amount] が INF のときに -1 を返さないと、巨大な数値が結果として返ってしまいます。3 つ目は 計算量の見積もり。二重ループなので O(amount * len(coins))。amount = 10^4、coins = 10 種でも 10^5 回程度なので余裕で間に合います。amount = 10^9 だとさすがに無理。

やってみよう

coins = [1, 3, 4]、amount = 6 で試す。貪欲法だと 4 + 1 + 1 = 3 枚 になるが、DP なら 3 + 3 = 2 枚 を見つけられる。
同じ問題で「何通りの組み合わせがあるか」を求める版に拡張する。漸化式が dp[i] += dp[i - c] に変わる。
dp 配列の中身をログに出して、左から右に最小値が確定していく様子を観察する。

貪欲法では解けない ケース (例: [1, 3, 4] で 6) を DP が解けるのが醍醐味。最後の 1 枚で場合分けし、min を取る、というパターンは多くの DP に応用できる。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 0/1 ナップサック問題 で、重さと価値を持つ品物から容量制限内で価値を最大化する組み合わせを DP で求める方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

コイン両替の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. コイン両替とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

コイン両替最小枚数