コイン交換

目標額を作る最少のコイン枚数を求めます。毎回最大の使える額面を選ぶ貪欲法は、一部の体系では正しくても任意の額面で最適とは限りません。DP は小さい金額を先に解いて再利用し、O(amount × coins) 時間です。ここでは正整数の額面を無制限に使えます。

独自の額面なら DP を使うか、貪欲選択を先に証明します。画面は同じ数直線に両戦略を置き、各ジャンプを一枚の額面に対応させます。

コイン交換の仕組み

貪欲法は remaining = amount から、残額以下の最大コインを選び、引いて数えます。0 なら金額は作れますが、最少とは限りません。残額があるのに使えるコインがなければ、その貪欲経路の失敗であり、単独では解なしの証明になりません。

dp[a] は a を作る最少枚数です。dp[0] = 0、ほかは未到達を表す無限大にします。

金額を小さい方から埋め、各額面 c を試します。c ≤ a で dp[a - c] が有限なら候補は次です。

dp[a - c] + 1

a-c の最適解に c を一枚加えます。全額面を比べて最小を採用し、有限候補がなければ無限大のままです。正額面なので依存先は小さく、完成済みです。

最後の dp[amount] が有限なら返し、無限大なら -1。実際のコインは各セルの勝者を記録し、目標からその額面を引いて 0 まで戻します。

計算をステップで追う

既定は額面 1, 3, 4、金額 6。

貪欲法：4 を取り残り 2、3 と 4 は使えず 1、1 を取って 0。4 + 1 + 1 の三枚で作れますが最少ではありません。

DP：dp[0] = 0、ほかは無限大。

• dp[1]：1 だけが使え、dp[0] + 1 = 1。
• dp[2]：1 だけで dp[1] + 1 = 2。
• dp[3]：3 は dp[0] + 1 = 1、1 は dp[2] + 1 = 3。一枚を選ぶ。
• dp[4]：4 は一枚、3 と 1 は二枚。4 を選ぶ。
• dp[5]：4 は dp[1] + 1 = 2、3 は 3、1 は dp[4] + 1 = 2。最小 2 で、この順序では額面 4 を保持。
• dp[6]：4 は dp[2] + 1 = 3、3 は dp[3] + 1 = 2、1 は dp[5] + 1 = 3。3 を選び二枚。

表は dp = [0, 1, 2, 1, 1, 2, 2]。

逆追跡：6 の勝者 3 を記録して金額 3 へ。そこも 3 を選んだので 0 へ。3 + 3 の二枚で、貪欲法より一枚少なくなります。

dp[6] より前に dp[3] は最適と確定し、過去の判断を取り消し続ける必要はありません。最後の逆追跡は組み合わせの復元です。Canonical の 1, 2, 5 で両者の一致、Impossible の 3, 5 と金額 7 で -1 を確認できます。

時間・空間計算量

coins は額面の種類数で、貪欲法にはソートと逐枚の出力を含みます。DP は金額の数値に依存する擬多項式アルゴリズムです。大きい金額では、規則が単純でも安いとは限りません。

境界ケース

• 金額 0：dp[0] = 0、コイン不要。全到達経路の基底。
• 大きすぎる額面：そのセルの候補にしない。
• 解なし：3 と 5 で 7 は dp[7] が無限大、-1。貪欲法は 5 を取って残り 2 で止まる。
• 貪欲法が正しい体系：1、2、5 で 11 は両方三枚。貪欲法は常に誤りではなく、条件が必要。
• -1 の意味：DP が全合法な最後のコインを調べた結果で、未完了ではない。

よくある間違い

• 最大額面を無条件に信頼する。 greedy-fails の 1、3、4 が反例です。
• 未到達を 0 にする。 無解の金額を無料で作れると扱い、最小値を壊します。
• 無限大から有効候補を作る。 dp[a - c] は有限でなければなりません。
• 最少枚数と組み合わせ数を混ぜる。 ここは min であり、通り数には別の漸化式が必要です。
• 前向きにコインを復元する。 最終金額から勝者の額面を引いて戻ります。

簡略化の範囲

少数の額面を数直線で比べます。日常の通貨で貪欲法がうまく動くことは、任意額面の証明にはなりません。この DP はすでに金額別の一次元表です。実装では結果のコインが必要かに応じて前駆記録を選び、数直線は不要です。漸化式の説明であり、すべての入力条件や運用方針を含む交換システムではありません。