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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个硬币列表和另一个值数量，我们必须找到总和等于数量的组合数量。如果答案很大，则将结果修改为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

    以上是 程序以找到要在Python中达到目标的硬币组合数量 的全部内容， 来源链接： utcz.com/z/330829.html

    回到顶部