コイン問題（最小枚数）
決まった額面の硬貨で目標金額をちょうど払うとき、必要な最小の硬貨枚数を表を埋めて求めます。
11
埋めるステップ
0
計算中の金額
x−c（残り金額）の答え
復元経路
—
使える硬貨の額面が決まっているとき、目標金額をちょうど作る最小の枚数は？
金額 x は、最後に置く硬貨 c を 1 枚決めれば 残り x−c の答えに 1 を足すだけ：
「大きい硬貨から貪欲に」では最小にならない場合があり、DP なら必ず最小が出ます。
dp[x] ＝「金額 x を作る最小枚数」。金額 0 は 0 枚（dp[0]=0）から出発。金額 x は、最後に置く硬貨 c を 1 枚決めれば 残り x−c の答えに 1 を足すだけ：
dp[x] = 1 + min(dp[x−c] | 各硬貨 c)「大きい硬貨から貪欲に」では最小にならない場合があり、DP なら必ず最小が出ます。
いま計算している金額
ここが DP の本質
- 「目標金額の最小枚数」を 「0 円, 1 円, 2 円, … 各金額の最小枚数」という小さな部分問題に分解。
- 金額 x は すでに解いた x−c の答えを再利用するだけ。小さい金額から順に表を埋める。
- 例：硬貨 1・3・4 で 6 円 ── 貪欲だと 4+1+1=3 枚、DP なら 3+3=2 枚と正しく最小になる。