コイン両替最小枚数
額面の決まったコインを組み合わせて、指定された金額ちょうどを作ります。使う枚数を最も少なくするのが目標で、どう組み合わせても作れない金額なら -1 を返します。
大きい額から使うと、2 枚で済むところが 3 枚になる
コインが 1、3、4 円の 3 種類、作りたい金額が 6 円だとします。大きいほうから使うと、まず 4 を取り、残り 2 円を 1 円 2 枚で埋めて合計 3 枚です。ところが 3 円を 2 枚使えば 2 枚で済みます。
大きいほうから取る手は、日本の硬貨のように額面が都合よく並んでいるときだけ当たります。額面が自由に決まる以上、最初の 1 枚を決め打ちで選ぶことはできません。
最後の 1 枚を決め打ちして、残りは任せる
選べないなら、全部試します。6 円を作る最後の 1 枚が何だったかで場合分けします。
5 円、3 円、2 円それぞれの最小枚数さえ分かっていれば、そこへ最後の 1 枚を足した 3 つの値のうち、一番小さいものが 6 円の答えです。5 円の答えも同じやり方で 4、2、1 円から決まります。金額を 1 円から順に決めていけば、見に行く先は必ず先に決まっています。
出発点は 0 円で、使う枚数は 0 枚です。
作れないことを 0 で表すと、それが選ばれてしまう
2 円玉しかないのに 3 円を作れ、という金額が途中に現れます。ここを 0 にしておくと、最小値を選ぶ場面で 0 が一番小さい値として選ばれ、作れないはずの金額から答えが組み立てられてしまいます。
作れないことは、絶対に選ばれない大きな値で表します。
Python
print(min(float('inf'), 3)) # 3 が選ばれる
print(float('inf') + 1) # inf のままJavaScript
console.log(Math.min(Infinity, 3)); // 3
console.log(Infinity + 1); // Infinity無限大は何を足しても無限大なので、+ 1 を通しても「作れない」の印が消えません。最後まで無限大のままだったら、その金額は本当に作れなかった、と判定できます。
やってみよう
coinChange(coins, amount) を書いてください。金額ごとの最小枚数を入れる箱を 0 円から amount 円まで用意し、0 円のところに 0 を置きます。あとは金額の小さいほうから順に、coins の各額面を最後の 1 枚だと仮定して試し、一番小さい値を残します。額面より小さい金額では、その額面は試せません。最後に amount の箱を見て、作れないままなら -1 を返します。
要件
- dp[i] を「金額 i を作る最小コイン枚数」と定義し、dp[0] = 0 を基底ケースにする
- dp[i] = min(dp[i - c] + 1) を coins の全要素で試す (i >= c のときのみ)
- amount を作れない場合は -1 を返す
入出力例
coinChange([1,2,5], 11) → 3
coinChange([2], 3) → -1
coinChange([1], 0) → 0
coinChange([1,3,4], 6) → 2
coinChange([2,5,10,1], 27) → 4
coinChange([186,419,83,408], 6249) → 20ヒント
