Pythonでターゲットに到達するためのコインの組み合わせの数を見つけるプログラム

コインのリストと別の値の金額があるとすると、その合計から金額までの組み合わせの数を見つける必要があります。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します。

したがって、入力がcoins =[2、5] amount =10の場合、これらの組み合わせを作成できるため、出力は2になります-[2、2、2、2、2]、[5、5]

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7
• dp：=金額+1と同じサイズのリストで、0で埋めます
• dp [0]：=1
• コインのdごとに、
  • 1からdpのサイズまでの範囲のiについては、
    • i --d> =0の場合、
      • dp [i]：=dp [i] + dp [i --d]
• return（dpの最後の要素）mod m

理解を深めるために、次の実装を見てみましょう-

例

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