資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚設計
法律Python 中的找零問題
假設我們有不同面值和總數額為 amount 的硬幣。我們需要定義一個函式來計算組成該金額所需的硬幣最少數量。如果任何硬幣組合都無法滿足該金額，則返回 -1。因此，如果輸入為 [1,2,5]，且金額為 11，則輸出為 3。這是使用 5 + 5 + 1 = 11 形成的。
為解決這個問題，我們將遵循以下步驟 −
- 如果 amount = 0，則返回 0
- 如果 coins 陣列的最小值 > amount，則返回 -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) #print(dp) return dp[amount] ob1 = Solution() print(ob1.coinChange([1,2,5], 11))
輸入
[1,2,5] 11
輸出
3
更新於： 2020-4-28
5K+ 次瀏覽
廣告