今天給大家分享一道動態規劃的常考題，零錢兌換，很有趣的動態規劃題目，希望可以對大家找工作過程中起到幫助，幫助大家拓展下思維

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

示例 1：
輸入：
coins = [1, 2, 5], amount = 11
輸出：3 解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3 輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

Problem: 322. 零錢兌換

解題過程

使用動態規劃的解法，定義dp[i]為：湊夠金額i所用到最小多少枚硬幣，,定義硬幣面額為c,遍歷所有的硬幣面額，我們可以發現這樣一個轉移關系,如果此時i>=c,則：
$$dp[i]=dp[i?c]+1$$
最初我們定義所有的dp為極大值，dp[0]為0(因為湊過0元需要0個硬幣)，我們的目標值為target，最終返回dp[target]即可

復雜度

• 時間復雜度,假設目標值為m，有n個硬幣: $O(m?n)$
• 空間復雜度: $O(m)$

Code

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [inf] * (amount+1)dp[0] = 0for i in range(1,amount+1):for c in coins:if i>=c:dp[i] = min(dp[i],dp[i-c] + 1)return dp[amount] if dp[amount]!=inf else -1