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

問題：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テーブルは以下のようになる。 次に、「3を少なくとも1枚を使