在 Python 中找到达目标所需的硬币组合数

假设我们有一组硬币，和一个目标金额，我们要找到有多少种组合能够达到这个金额。如果答案很大，那么对 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，执行以下操作
- 对于 dp 列表的长度范围从 1 到 size，执行以下操作：
  - 如果 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))