Python程式：查詢湊零錢所需的硬幣數量

假設我們有不同面額的硬幣和一個總金額。我們需要定義一個函式來計算湊成該金額所需的最少硬幣數量。當該金額無法由任何硬幣組合湊成時，返回 -1。所以如果輸入是 [1, 2, 5]，金額是 64，輸出是 14。這是由 12*5 + 2 + 2 = 64 組成。

為了解決這個問題，我們將遵循以下步驟：

  • 如果金額 = 0，則返回 0
  • 如果硬幣陣列的最小值 > 金額，則返回 -1
  • 定義一個名為 dp 的陣列，大小為 amount + 1，並將其全部填充為 -1
  • 對於 coins 陣列中的每個 i
    • 如果 i > dp 長度 - 1，則跳過下一部分，進行下一次迭代
    • dp[i] := 1
    • 對於 j 從 i + 1 到 amount
      • 如果 dp[j – 1] = -1，則跳過下一部分，進行下一次迭代
      • 否則，如果 dp[j] = -1，則 dp[j] := dp[j - i] + 1
      • 否則 dp[j] := dp[j] 和 dp[j – i] + 1 的最小值
  • 返回 dp[amount]

讓我們看看下面的實現，以更好地理解：

示例

即時演示

class Solution(object):
   def coinChange(self, coins, amount):
      if amount == 0 :
         return 0
      if min(coins) > amount:
         return -1
      dp = [-1 for i in range(0, amount + 1)]
      for i in coins:
         if i > len(dp) - 1:
            continue
         dp[i] = 1
         for j in range(i + 1, amount + 1):
            if dp[j - i] == -1:
               continue
            elif dp[j] == -1:
               dp[j] = dp[j - i] + 1
            else:
               dp[j] = min(dp[j], dp[j - i] + 1)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5],64))

輸入

[1,2,5], 64

輸出

14

更新於: 2020-10-19

198 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告