コインの組み合わせは何通り？ 〜動的計画法〜

問題：1枚あたりの価値が{2,3,5}の3種類のコインを組み合わせ、金額の合計をちょうど14にするやり方は何通りか。コインはそれぞれ何枚でも使ってよいとする。

coin = [2, 3, 5]
total = 14
def combinations(coin, total):
    dp = [int(i % coins[0] == 0) for i in range(total + 1)]
    for coin in coin[1:]:
        for i in range(coin, total+1):
            dp[i] += dp[i-coin]
    return dp[-1]

コード解説

この例だと、まず価値が2のcoinだけを使った場合の場合の数を、全ての金額で算出する（これは単に2で割ってmod0の場合は0、mod1の場合は1）

この時点でのdpテーブルは以下のようになる。

[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

次に、「3を少なくとも1枚を使ってちょうど10を作る組み合わせ総数」をDPテーブルの数値に足し合わせていく。

例として、DPテーブルのtotal=10の数値を更新する場合を考える。
その時点でtotal=10の場所に入っている数値は「2だけを使ってちょうど10を作る組み合わせ総数」である。
ここに「3を少なくとも1枚を使ってちょうど10を作る組み合わせ総数」を加えた値は、「2と3を使ってちょうど10を作る組み合わせ総数」である。

ここで、「3を少なくとも1枚を使ってちょうど10を作る組み合わせ総数」は「2と3を使って7を作る組み合わせ総数（3は使っても使わなくても良い）」と同じであることに（天啓によって）気づく。

左から順々にDPテーブル更新していくため、totalが1から9の場合の数は既に更新されている(既に2と3を使ってちょうど{1~9}を作る組み合わせ総数が記入されている)と考えると、DP更新時にtotal=10に既に記入されている数値（2だけを使ってちょうど10を作る組み合わせ総数）にtotal=7に記入されている数値（2と3を使って7を作る組み合わせ総数）を足せばいい。

この要領で、DPテーブルのそれぞれを更新していくことをcoinを1枚ずつ増やしながら繰り返すと、最後には全コインを使った組み合わせ総数が求まる。（この時、range(coin, total-1)とcoinの数値始まりにしておくとインデックスエラーにならない）

以下が、DPの全ての更新が終了した後のテーブルである。
これらが、{2,3,5}を足してちょうど{1~14}を作る組み合わせ総数である。

[1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6]