用 Python 编写程序，查找达到目标所需的硬币组合数

pythonserver side programmingprogramming

假设我们有一个硬币列表和另一个值 amount，我们必须找到总和为 amount 的组合数。如果答案非常大，则将结果取 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]
返回 (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))