Python程序：查找硬币组合数量以达到目标值

假设我们有一列硬币和另一个值amount，我们需要找到总和为amount的组合数量。如果答案非常大，则将结果模 10^9 + 7。

因此，如果输入类似于 coins = [2, 5] amount = 10，则输出将为 2，因为我们可以进行以下组合：[2, 2, 2, 2, 2]，[5, 5]

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

  • m := 10^9 + 7
  • dp := 一个大小与amount + 1相同列表，并用0填充
  • dp[0] := 1
  • 对于coins中的每个d，执行以下操作：
    • 对于从1到dp大小的范围内的每个i，执行以下操作：
      • 如果 i - d >= 0，则：
        • dp[i] := dp[i] + dp[i - d]
  • 返回 (dp的最后一个元素) 模 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

更新于： 2020年11月20日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告