Coin Change
異なる額面の硬貨のリスト coins と目標金額 amount が与えられます。各額面の硬貨は好きな回数だけ使用できます。硬貨の合計がちょうど amount になる組み合わせのうち、硬貨の枚数が最小となる枚数を返してください。そのような組み合わせがない場合は -1 を返します。金額が 0 の場合、必要な硬貨は 0 枚です。
関数
- coinsinteger-array
- 異なる硬貨の額面。それぞれ何度でも使用できます
- amountinteger
- 支払う合計金額を正確に
- 戻り値integer
- 必要な最小枚数のコイン。金額を作れない場合は -1
制約
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- すべてのコインの値は異なります。
例
- 入力
- coins = [2, 5, 10]amount = 27
- 出力
- 4
- 説明
- 10 + 10 + 5 + 2 は4枚のコインで27になります。3枚ではできません。27は奇数なので、5がちょうど1枚必要で、残りの2枚の合計は最大でも20となり、22に届きません。
- 入力
- coins = [4, 6]amount = 7
- 出力
- -1
- 説明
- 両方のコインの値は偶数なので、作れる合計はすべて偶数です。7は奇数なので、答えは-1です。
- 入力
- coins = [3, 7]amount = 0
- 出力
- 0
- 説明
- 0を支払うのにコインはまったく必要ないので、コインの値にかかわらず答えは0です。
発展問題
最少枚数の硬貨を見つけるのではなく、amountになる硬貨の組み合わせが何通りあるか数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
入る中で最も大きい硬貨を常に選んでも、硬貨の枚数が最少になるとは限りません。硬貨
[1, 3, 4]と金額6で試してみましょう。tより小さいすべての金額について、必要な硬貨の最少枚数がすでにわかっているとします。硬貨をもう1枚追加すると、どの小さい金額からtに到達できますか？fewest[0..amount]の表を0から順に埋めます。fewest[0] = 0とし、各fewest[t]は、コインc <= tについての最良のfewest[t - c]に 1 を加えた値です。到達できない金額には、amount + 1のように実際のどの答えよりも大きな値を設定し、最後に-1にします。
解説
入る中で最も大きい硬貨を選ぶ方法は失敗します。硬貨が1、3、4の場合、6は4 + 1 + 1として支払われますが、3 + 3なら硬貨は2枚で済みます。ある金額に必要な最少枚数は、より小さい金額に必要な最少枚数だけで決まるため、0からamountまでの各金額を一度ずつ解きます。
再帰を使ってあらゆる組み合わせを試す
正しいが、最大のテストでは終わらない
考え方
最後に支払う硬貨の額面が c なら、その前に支払う硬貨で remaining - c をできるだけ少ない枚数で支払います。つまり、fewest(remaining) は、使える硬貨すべてについて fewest(remaining - c) の最小値に1を足したものです。超過しない硬貨の組み合わせをすべて試すため、最適な組み合わせを見逃すことはありません。
同じ金額を何度も計算します。額面が2、5、10の硬貨の場合、金額27では、10 + 2、2 + 10、5 + 5 + 2などの順序で支払うたびに15に到達し、その都度15を最初から計算します。呼び出し回数は金額に対して指数関数的に増加します。
アルゴリズム
fewest(remaining)を作成します。このヘルパー関数は、remainingを支払うのに必要な最小のコイン数を返し、どのコインも使えない場合は -1 を返します。remainingが 0 の場合は、0 を返します。remaining以下の各コインについて、そのコインを支払った後の残額を使ってヘルパー関数を呼び出します。- -1 ではない結果のうち最小のものを選び、支払ったコイン分の 1 を加えます。
- その枚数を返します。どのコインを使っても解決できない場合は -1 を返します。答えは
fewest(amount)です。
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)メモ化を用いた再帰
正しいが、最大のテストでは終わらない
考え方
再帰では、金額 amount までの 0 からの範囲だけを調べます。答えを最初に求めたときに配列に保存し、その金額が再び出てきたら保存した値を返します。各金額は、コインを順に調べるループで一度だけ解決されます。計算量は O(amount × coins) です。
それでも、支払うコインごとに呼び出しが1段階ずつネストします。価値が1のコインがある場合、ネストは最大で 10^4 段階になり、多くの言語でデフォルトのコールスタックが許容する深さを超えます。
アルゴリズム
- 0から
amountまでのすべての金額に対応できる大きさの配列memoを作り、まだ計算されていないことを示すマーカーを格納します。 fewest(remaining)では、0の場合は0を返し、すでに答えが格納されている場合はmemo[remaining]を返します。- それ以外の場合は、単純な再帰と同じように使えるすべてのコインを試し、最小の結果に1を加えた値を保持します。
- 返す前に、結果（-1も含む）を
memo[remaining]に保存します。 fewest(amount)を返します。
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)金額に対するボトムアップ型の動的計画法
考え方
テーブル fewest を0から順に埋めていきます。合計が t になったとき、それより小さいすべての合計は確定しているので、fewest[t] は、使えるコイン c についての fewest[t-c] の最小値に1を足した値です。
どのコインの組み合わせでも到達できない合計には、目印 amount + 1 を入れておきます。どのコインも少なくとも1の価値があるため、実際の答えで使うコインの枚数が amount を超えることはなく、この目印はどの比較でも負けます。再帰の代わりにループを使うので、呼び出しスタックの深さは問題になりません。
アルゴリズム
amount + 1個の要素を持つfewestを作成し、すべてにマーカーamount + 1を設定して、fewest[0]を 0 に設定します。- 合計
tを 1 からamountまで順に取り、それぞれについてc ≤ tを満たすすべてのコインcを調べます。 fewest[t-c] + 1がfewest[t]より小さい場合、その値をfewest[t]に格納します。- ループの後、
fewest[amount]がまだマーカーの値なら -1 を返し、そうでなければfewest[amount]を返します。
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
落とし穴と境界ケース
- 最も額面の大きい硬貨を最初に使う。硬貨が3と5で、金額が9の場合、5と3を使って残り1で行き詰まり、-1を返しますが、3 + 3 + 3ならうまくいきます。
- 最大の整数を目印として使う。それに1を足すとオーバーフローして負の数になり、あらゆる比較で勝ってしまいます。
amount + 1を使いましょう。 - 行き止まりで1を足す。-1を返す分岐に支払った硬貨を足すと0になり、あらゆる比較で勝ってしまいます。-1の結果はスキップしましょう。
amountのレベルまで再帰する。額面が1の硬貨を使い、金額が10^4の場合、Pythonはデフォルトの1000レベルで停止し、JavaScript、Dart、Ruby、Rもスタック不足になります。- 硬貨の額面が
tより大きい場合に、テーブルの先頭より前にあるfewest[t-c]を読み取る。
よくある質問3
Coin Change で貪欲法が失敗するのはなぜですか？
入る中で最も大きな硬貨を選ぶ方法が安全なのは、ほとんどの実際の通貨のような、一部の硬貨体系に限られます。硬貨が1、3、4の場合、6を支払うのに2枚ではなく3枚必要になり、硬貨が3と5の場合は、9をまったく支払えません。動的計画法はあらゆる選択肢を比較するため、どのような硬貨体系でもだまされません。
Coin Change の時間計算量はどれくらいですか？
動的計画法による解法は、時間計算量が O(amount × coins)、空間計算量が O(amount) です。金額ごとにテーブルのエントリーが1つあり、各エントリーについてすべてのコインを確認します。メモ化を使わない単純な再帰では、金額に対して指数時間がかかります。
Coin Change では、トップダウンとボトムアップのどちらが優れていますか？
どちらも同じ O(amount × coins) の処理を行います。トップダウンの再帰は金額と同じ深さまでネストすることがあり、複数の言語では 10^4 でコールスタックがオーバーフローします。ボトムアップはループでテーブルを埋めるため、深さの制限がなく、面接ではより安全な選択肢です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def coinChange(coins, amount):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
coins = [2, 5, 10] amount = 27
期待される出力
4