アルゴリズムとデータ構造

コイン・チェンジ - 組み合わせの数

n 種類のコインからなる通貨システムがあり、それぞれのコインには正の値 が割り当てられています。これらのコインを使って合計金額 x を作る方法がいくつあるかを求める問題です。
たとえば、コインの値が のときに 5 を作る方法は全部で 4 通りあります: 5, 1 + 2 + 2, 1 + 1 + 1 + 2, 1 + 1 + 1 + 1 + 1。Combination Sum と異なり、ここでは並び順は考慮せず、使われるコインのマルチセットが同じであれば同一の組み合わせとして数えます。

入力

入力の最初の行には、2 つの整数 n (1 ≤ n ≤ 100) と x (1 ≤ x ≤ ) が与えられます。
次の行には、n 個の整数 (1 ≤ ≤ ) がスペース区切りで与えられます。

出力

与えられたコインを使って合計 x を作る方法の数を出力してください。答えが非常に大きくなる場合があるので、 で割った余りを出力する必要があります。

例

入力
出力
3 5 1 2 5
4
3 9 2 3 5
3

解説

  1. 5, 1 + 2 + 2, 1 + 1 + 1 + 2, 1 + 1 + 1 + 1 + 1
  1. 3 + 3 + 3, 2 + 2 + 5, 2 + 2 + 2 + 3
 

チュートリアル

もし d[s] のように、合計金額 s を作る方法の数を 1 次元配列で表そうとすると、同じコインの組み合わせを並び替えただけで重複カウントしてしまう問題が生じます。たとえば、1 + 2 + 2 という組み合わせは本来 1 通りであるべきところを、並びの異なる 1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1 として複数回計算してしまいます。
この重複を防ぐために、「コイン配列 c のうち、index が ci のコインまで使って合計 s を作るときの方法数」を状態として管理します。すなわち、d[s][ci] は「c の 0 番目から ci 番目までのコインを使って合計 s を作る方法の数」を表すようにします。ci 番目のコインを使わないこともあれば、複数枚使うことも可能で、すべてこの状態に含まれます。
 
d[s][ci] を更新する際に考慮する遷移は、大きく以下の 2 つです（現在のコインの添字は ci, その値を val とします）:
  1. コイン ci を全く使わない → d[s][ci - 1]
  1. コイン ci を 1 枚以上使う → d[s - val][ci]
つまり、最終的に ci 番目までのコインで合計 s を作る方法の数は、上記 2 つの遷移先からの和になります。
 
c = [...]
x = ...
# d を (x+1) 行 × len(c) 列の 0 で初期化
d = [[0] * len(c) for _ in range(x + 1)]
まず最初のコインを処理し、合計 s が取りうるすべての場合について d[s][0] を更新します。次に 2 番目のコインを使って d[s][1] を更新し、3 番目を使って d[s][2] を更新していく、という手順で最後のコインまで進みます。
すべてのコインを処理し終わったら、合計 x を作る方法の数は d[x][len(c) - 1] に格納されているので、それを出力すれば正解です。
for ci, val in enumerate(c):      # コインを1つずつ処理
    d[0][ci] = 1                  # 合計0はコインを使わなくても作れる
    for s in range(1, x + 1):     # 1 から x までの合計値を順に計算
        if ci - 1 >= 0:           # (1) ci をまったく使わない
            d[s][ci] += d[s][ci - 1]
        if s - val >= 0:          # (2) ci を1枚以上使う
            d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])
 
😎 1 次元配列で d を管理する方法を考えられますか？
コインを 1 種類ずつ処理するとき、ci - 2 より前のコインに関する計算結果はもう使いません。したがって、前のコインに関する配列と現在のコインに関する配列だけあれば十分です。前のコインに対応する配列から現在のコインに対応する配列を更新していけばいいのです。
😎 補助配列を使わずに、1 次元 d だけで解く方法は？
実は、前のコインの結果からは prev[s] を d[s] に足す操作しか行っていません。すると、そもそも前の配列を保持せずに以下のように書き換えることができます。
# d を x+1 個の要素で初期化
d = [1] + [0] * x                 # 合計0はコインを使わなくても作れる

for ci, val in enumerate(c):      # コインを1つずつ処理
    for s in range(1, x + 1):     # 1 から x までの合計値を順に計算
        if s - val >= 0:          # (2) ci を1枚以上使う
            d[s] += d[s - val]
        d[s] %= MOD

print(d[x])
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue