Pythonで指定した金額を作るコインの組み合わせ数を求めるプログラム

コインの種類を表すリストと、目標となる金額（amount）が与えられたとき、合計がちょうどその金額になる組み合わせが何通りあるかを求める問題を考えてみましょう。答えが非常に大きくなる場合は、結果を 10^9 + 7 で割った余りを返します。

たとえば、coins = [2, 5]、amount = 10 という入力の場合、出力は 2 になります。これは次の2通りの組み合わせで 10 を作れるためです。

• [2, 2, 2, 2, 2]
• [5, 5]

解法のアプローチ：動的計画法（DP）

この問題は動的計画法を使うことで効率的に解けます。dp[i] を「i 円を作る組み合わせの数」と定義し、コインの種類ごとにDPテーブルを更新していきます。

ポイントは、コインのループを外側に置くことです。こうすることで、[2, 5] と [5, 2] のように並び順だけが違うものを「同じ組み合わせ」として数え、重複を防ぐことができます。

アルゴリズムの手順

• m := 10^9 + 7（剰余を取るための定数）
• dp := サイズが amount + 1 のリストを作り、すべて 0 で初期化する
• dp[0] := 1（0円を作る方法は「何も選ばない」の1通り）
• coins 内の各コイン d について、以下を繰り返す：
  • i を 1 から dp のサイズまで動かしながら、i - d >= 0 であれば dp[i] := dp[i] + dp[i - d] と更新する
• 最後に dp の最後の要素を m で割った余りを返す

計算量はコインの種類数を n、金額を a とすると O(n × a) となり、全探索よりもはるかに効率的です。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
   def solve(self, coins, amount):
      dp = [0] * (amount + 1)
      dp[0] = 1
      for d in coins:
         for i in range(1, len(dp)):
            if i - d >= 0:
               dp[i] += dp[i - d]
      return dp[-1] % (10 ** 9 + 7)
ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))

入力

[2, 5], 10

出力

2

まとめ

このプログラムでは、dp[0] = 1 を基点として、各コインの種類ごとにDPテーブルを順番に更新していくことで、重複なく組み合わせの総数を数えています。コインの順列ではなく「組み合わせ」を数える場合は、ループの順序（コインを外側にする）が重要なポイントになるので、覚えておくと応用が利きます。