You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
給你一組不同面額的錢以及資金總額。找到使用硬幣組合成該資金總額的最少數(shù)量。如果沒法組合得到，返回-1
coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)
coins = [2], amount = 3 return -1.
動態(tài)規(guī)劃解。定義dp[i]：使用硬幣組合成資金總額i的最少數(shù)量，遞推關(guān)系式：dp[i] = min(dp[i - coin]) + 1 (coin in coins)。因為dp[i]都需要加上硬幣面額中的一個（當然硬幣面額一定要小于資金總額），所以我們只要找出到底加上哪個硬幣面額使用硬幣數(shù)量最少即可。對于沒法組合得到的資金總額，我們只需初始化的時候設(shè)置一個固定較大值，它并不會被更新到
class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ dp = [0] + [amount + 1] * amount for a in range(1, amount + 1): for c in coins: # 只對小于amount的硬幣進行判斷 if a >= c: dp[a] = min(dp[a], dp[a - c] + 1) # 如果amount不能被硬幣組合得到，那么它對應(yīng)的d[amount]不會更新 return dp[amount] if dp[amount] != amount + 1 else -1新聞熱點
疑難解答
