問題
硬貨のcoins と、amount をamount に
- 組み合わせは、
どの 硬貨を 何枚使うかだけで 区別します。 出す順番の 違いは 同じ 1 通りです。 たとえば 2 円、 3 円の 順と 3 円、 2 円の 順は同じです amountが 0 のときは、 硬貨を 1 枚も 使わない 1 通りが あるので 1 を 返します。 作れない ときは 0 を返します coinsの長さは 1 以上 300 以下で、 額面は どれも 違います。 額面は 1 以上 5000 以下です amountは 0 以上 5000 以下です。答えは 2147483647 以下に 収まる ものとします
入力と出力の例
例 1
10 円 1 枚と 1 円 2 枚、
入力
coins = [1, 5, 10]
amount = 12出力
4例 2
2 円 2 枚と 3 円 1 枚の 1 通りだけです。
入力
coins = [2, 3]
amount = 7出力
1例 3
金額が 0 なら、
入力
coins = [4]
amount = 0出力
1面接での聞かれ方
面接では、
- 「では、
ちょうど その 金額に する 組み合わせは 何通り ありますか？」 - 書いた
答えが 大きすぎると、 「2 と 3 で 5 を 作るのは 何通りですか？」と 小さな 例で 確かめさせられます。 順番違いを 別に 数えていないかを 見ています - 「2 重の
繰り返しの 内と 外を 入れ替えると、 何を 数える ことになりますか？」と、 繰り返しの 順の 意味を 聞かれます
最少の
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
最少のways[a-c] の
段 2
組み合わせを 1
段 3
表 ways を 1 次元にし、ways[0] = 1 からamount までways[a] に ways[a-c] をways[a-c] には
解答
Python
Python
def coin_ways(coins, amount):
n = amount + 1
ways = [0] * n
ways[0] = 1
for c in coins:
for a in range(c, n):
ways[a] += ways[a-c]
return ways[amount]JavaScript
JavaScript
function coinWays(
coins, amount
) {
const n = amount + 1;
const ways = Array(n).fill(0);
ways[0] = 1;
for (const c of coins) {
let a = c;
while (a < n) {
ways[a] += ways[a - c];
a++;
}
}
return ways[amount];
}Go
Go
func coinWays(
coins []int, amount int,
) int {
n := amount + 1
ways := make([]int, n)
ways[0] = 1
for _, c := range coins {
for a := c; a < n; a++ {
ways[a] += ways[a-c]
}
}
return ways[amount]
}外側の 1 回がways[a] はamount より
計算量
- 時間は O(k × amount) です (k は
硬貨の 種類の 数)。 硬貨ごとに 表を 1 回なめます。 300 種類で 金額 5000 なら 150 万回ほどです - 使う
記憶は O(amount) です。 表 waysの長さが amount + 1です - 「何種類目までで
金額いく つか」の 2 次元の 表でも 同じ 時間で 解けますが、 記憶が O(k × amount) になります
よく
- 金額を
外側、 硬貨を 内側に回す。 出す順番の 違いを 別々に 数えてしまいます。 例 2 で 3 を 返したら、 この 間違いです。 最少の 枚数の 問題では どちらの 順でも 答えは 同じでしたが、 数える 問題では 繰り返しの 順が 答えを変えます - 内側を
大きい ほうから回す。 0-1 ナップサックの 癖で 後ろから 回すと、 各硬貨を 1 枚までしか 使わない 数え方に なります。 例 1 の 1 円 12 枚のような 組み合わせが 数えられません ways[0]を 0 にする。 何も出さない 1 通りが 土台なので、 ways[0] = 1から始めます。 0 のままだと、 どの 金額も 0 通りに なります。 例 3 の 金額 0 の 答えも 1 です - 最少の
枚数の 問題の 表を そのまま使う。 そちらは 「作れない」の 印に 大きな 値を 入れ、 最小を 取る 表です。 数える 問題では、 作れない 金額は 0 通りで、 足し算で 積み上げます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「順番違いを
同じと 数えるので、 硬貨を 外側の 繰り返しに して、 1 種類ずつ 使える 硬貨を 増やしながら 表を 更新します。 金額を 内側で 小さい 順に 回すと、 同じ 硬貨を 何枚でも 使えます。 金額と 硬貨の 繰り返しを 入れ替えると、 出す順番の 並べ方を 数えてしまうので、 この 順が 大事です。 時間は O(種類 × 金額)、 記憶は O(金額) です。」
書き終えたら、
「例 2 の 2 円と 3 円で 7 円を
たどります。 2 円だけでは、 偶数の 0、 2、 4、 6 が 1 通りずつです。 次に 3 円を 足すと、 3 円は 0 円から 1 通り、 5 円は 2 円から 1 通り、 6 円は 3 円から 足して 2 通り、 7 円は 4 円から 足して 1 通りに なります。 答えは 1 です。」