程序以找到要在Python中达到目标的硬币组合数量

假设我们有一个硬币列表和另一个值数量，我们必须找到总和等于数量的组合数量。如果答案很大，则将结果修改为10 ^ 9 + 7。

因此，如果输入就像硬币= [2，5]数量= 10，那么输出将是2，因为我们可以进行以下组合-[2，2，2，2，2，2]，[5，5]

为了解决这个问题，我们将遵循以下步骤-

• m：= 10 ^ 9 + 7

• dp：=大小等于数量+ 1的大小列表，并用0填充

• dp [0]：= 1

• 对于硬币中的每个d，

• 如果i-d> = 0，则

• dp [i]：= dp [i] + dp [i-d]

• 对于范围1到dp的i，执行

• 返回（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