1. # 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
  2. #  -1。 
  3. # 
  4. #  你可以认为每种硬币的数量是无限的。 
  5. # 
  6. #  
  7. # 
  8. #  示例 1： 
  9. # 
  10. #  
  11. # 输入：coins = [1, 2, 5], amount = 11
  12. # 输出：3 
  13. # 解释：11 = 5 + 5 + 1 
  14. # 
  15. #  示例 2： 
  16. # 
  17. #  
  18. # 输入：coins = [2], amount = 3
  19. # 输出：-1 
  20. # 
  21. #  示例 3： 
  22. # 
  23. #  
  24. # 输入：coins = [1], amount = 0
  25. # 输出：0
  26. #  
  27. # 
  28. #  示例 4： 
  29. # 
  30. #  
  31. # 输入：coins = [1], amount = 1
  32. # 输出：1
  33. #  
  34. # 
  35. #  示例 5： 
  36. # 
  37. #  
  38. # 输入：coins = [1], amount = 2
  39. # 输出：2
  40. #  
  41. # 
  42. #  
  43. # 
  44. #  提示： 
  45. # 
  46. #  
  47. #  1 <= coins.length <= 12 
  48. #  1 <= coins[i] <= 231 - 1 
  49. #  0 <= amount <= 104 
  50. #  
  51. #  Related Topics 动态规划 
  52. #  👍 967 👎 0
  55. # leetcode submit region begin(Prohibit modification and deletion)
  56. class Solution(object):
  57.     def __init__(self):
  58.         self.cache = dict()
  60.     def coinChange(self, coins, amount):
  61.         """
  62.         :type coins: List[int]
  63.         :type amount: int
  64.         :rtype: int
  65.         """
  66.         # base case
  67.         if amount == 0:
  68.             return 0
  69.         if amount < 0:
  70.             return -1
  72.                 # 缓存
  73.         if amount in self.cache:
  74.             return self.cache[amount]
  76.         res = float("inf")
  77.         for coin in coins:
  78.             pre = self.coinChange(coins, amount - coin)
  79.             self.cache[amount - coin] = pre
  80.             if pre == -1:
  81.                 continue
  82.             res = min(res, 1 + pre)
  84.         return -1 if res == float("inf") else res
  87. # leetcode submit region end(Prohibit modification and deletion)
  89. print(Solution().coinChange([11, 12], 25))

自底向上（推荐）

  2. # leetcode submit region begin(Prohibit modification and deletion)
  3. class Solution(object):
  4.     def __init__(self):
  5.         self.cache = dict()
  7.     def coinChange(self, coins, amount):
  8.         """
  9.         :type coins: List[int]
  10.         :type amount: int
  11.         :rtype: int
  12.         """
  14.         dp = [float("inf") for x in range(amount + 1)]
  15.         dp[0] = 0
  16.         for i in range(amount + 1):
  17.             for coin in coins:
  18.                 if i < coin:
  19.                     continue
  20.                 dp[i] = min(dp[i], 1 + dp[i - coin])
  21.         return dp[amount] if dp[amount] != float("inf") else -1
  24. # leetcode submit region end(Prohibit modification and deletion)
  26. print(Solution().coinChange([11, 12], 2000002))