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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告