問題
自動販売機のcoins と、amount をamount に-1 を
amountが 0 のときは、 硬貨を 1 枚も 使わないので 0 を返します coinsの長さは 1 以上 12 以下で、 額面は どれも 違います。 額面は 1 以上 2147483647 以下です amountは 0 以上 10000 以下です
入力と出力の例
例 1
10 円 2 枚、
入力
coins = [1, 5, 10]
amount = 27出力
5例 2
大きい 4 から
入力
coins = [1, 3, 4]
amount = 6出力
2例 3
4 と 6 は
入力
coins = [4, 6]
amount = 9出力
-1面接での聞かれ方
面接では、
- 「硬貨の
種類と 金額が あります。 最小の 枚数を 返してください。 作れなければ -1 です」 - 最初に
欲張り (大きい 硬貨から 取る ) を 書くと、 「4、 3、 1 で 6 を 作ると？」と 反例を 出されます。 欲張りが 外れる ことに 自分で 気づけるかを 見ています - 書き終えた
あとに 「再帰と メモで 書けますか」 「表を 作る 向きは どちらでも いいですか」 「使う 硬貨の 内訳も 返せますか」と 続けて 聞かれます
金額 0 の
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
まず
段 2
このamount までのbest にbest[a] を
段 3
作れないamount 枚です。amount + 1 を[4, 6] のようなbest[0] = 0 からbest[amount] が-1 をa より
段 4
段 2 のamount からamount が 10000 なら Python の
解答
Python
Python
def min_coins(coins, amount):
none = amount + 1
best = [none] * (amount + 1)
best[0] = 0
for a in range(1, none):
for c in coins:
if c > a:
continue
cand = best[a-c] + 1
if cand < best[a]:
best[a] = cand
if best[amount] == none:
return -1
return best[amount]JavaScript
JavaScript
function minCoins(
coins, amount
) {
const none = amount + 1;
const best = Array(none)
.fill(none);
best[0] = 0;
best.forEach((_, a) => {
for (const c of coins) {
if (c > a) continue;
const prev = best[a - c];
if (prev + 1 < best[a]) {
best[a] = prev + 1;
}
}
});
const ans = best[amount];
if (ans === none) return -1;
return ans;
}Go
Go
func minCoins(
coins []int, amount int,
) int {
none := amount + 1
best := make([]int, none)
for a := 1; a <= amount; a++ {
best[a] = none
for _, c := range coins {
if c > a {
continue
}
cand := best[a-c] + 1
if cand < best[a] {
best[a] = cand
}
}
}
if best[amount] == none {
return -1
}
return best[amount]
}best[a-c] がbest[a] をamount + 1 にforEach で 0 円からbest[0] = 0 のまま
計算量
- 時間は O(amount × k) です (k は
硬貨の 種類の 数)。 金額ごとに 全部の 硬貨を 1 回ずつ試します。 金額 10000、 硬貨 12 種類なら 12 万回ほどです - 使う
記憶は O(amount) です。 表 bestの長さが amount + 1です - メモ付きの
再帰でも 計算量は 同じですが、 金額 10000 だと 深さが 10000 段近くになり、 Python の 再帰の 上限に かかります。 表を 下から 埋める 書き方の 方が安全です
よく
- 欲張りで書く。
大きい 硬貨から 取れるだけ取る 書き方は、 例 2 で 3 枚を 返します。 面接では これを 最初に 書いてしまい、 反例を 出されて詰まる 人が 多いので、 書く 前に 「欲張りで最小になるか」を 小さい 例で 確かめます - 作れない
印に 大きすぎる 値を使う。 Go で math.MaxIntを印に して best[a-c] + 1を計算すると、 あふれて 最小の 負の 数に なり、 それが 最小として 選ばれます。 印は amount + 1にします - 金額 0 の
扱いを忘れる。 amount == 0で -1 を返すと 誤りです。 使う 枚数は 0 枚です。 表を best[0] = 0から始めれば、 特別に 書かなくても 0 が返ります - 作れなかった
金額を 最後に 直さない。 best[amount]が印のまま 返すと、 -1ではなくamount + 1を返してしまいます - 額面が
金額より 大きい硬貨を 飛ばさない。 Python では best[a-c]の番号が 負に なっても エラーに ならず、 表の 後ろを 読んで 間違った 答えに なります。 c > aを先に 確かめます - 数え上げの
問題と 取り違える。 「作り方が何通りあるか」の 問題は、 硬貨の 繰り返しを 外側に する 別の 表に なります。 最小の 枚数を 求める この 問題とは、 表の 意味が違います
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「大きい
硬貨から 取る 欲張りは、 1、 3、 4 で 6 を 作る ときに 3 枚を 返して 外れます。 そこで 最後に 使った 1 枚に 注目すると、 金額 a の 最小の 枚数は、 どれかの 硬貨 c に ついて a - c の 最小の 枚数に 1 を 足した ものです。 0 円から 順に 表を 埋めれば、 各金額で 硬貨を 全部試すだけなので、 時間は O(金額 × 硬貨の 種類)、 記憶は O(金額) です。 作れない 印は 金額 + 1 に して、 最後に それが 残っていれば -1 を 返します。」
書き終えたら、
「例 2 で
たどります。 1 円から 3 円までは 1、 2、 1 枚です。 4 円は 4 の 硬貨 1 枚で 1 枚、 5 円は 4 円の 1 枚に 1 を 足して 2 枚です。 6 円は、 最後が 1 なら 5 円の 2 枚に 足して 3 枚、 最後が 3 なら 3 円の 1 枚に 足して 2 枚、 最後が 4 なら 2 円の 2 枚に 足して 3 枚なので、 最小の 2 枚が 答えです。」