LeetCode 322. Coin Change

原題

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.

Note:
You may assume that you have an infinite number of each kind of coin.

?

示例

Example 1:
coins =?[1, 2, 5], amount =?11
return?3?(11 = 5 + 5 + 1)

Example 2:
coins =?[2], amount =?3
return?-1.

?

思路

比較典型的動態規劃題目。要確定每個amount最少需要多少硬幣，可以用amount依次減去每個硬幣的面值，查看剩下總額最少需要多少硬幣，取其中最小的加一即是當前amount需要的最少硬幣數，這樣就得到了遞推公式，題目就迎刃而解了。

?

代碼實現

# 動態規劃
class Solution(object):def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""# 邊界條件if amount == 0:return 0# 存儲之前計算過的結果dp = [sys.maxint] * (amount + 1)dp[0] = 0# 自底向下編寫遞推式for i in xrange(1,amount+1):for j in xrange(len(coins)):if (i >= coins[j] and dp[i - coins[j]] != sys.maxint):# 當前數額的最小步數dp[i] = min(dp[i], dp[i - coins[j]] + 1)# 如果最小步數等于最大值，則代表無解return -1 if dp[amount] == sys.maxint else dp[amount]