题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明:**

  • 可以认为每种硬币的数量是无限的。

    方案一（递归+memorize）

  1. from functools import lru_cache
  3. class Solution:
  4.     def coinChange(self, coins: List[int], amount: int) -> int:
  5.         if amount == 0:
  6.             return 0
  7.         min_coins = min(coins)
  8.         # 使用一个函数而不是直接使用递归是为了只执行一次 min(coins)
  10.         @lru_cache(maxsize=None)
  11.         def getMin(amount: int) -> int:
  12.             # 获取组成 amount 的最小硬币数
  13.             if amount < min_coins:
  14.                 return -1
  15.             if amount in coins:
  16.                 return 1
  18.             _min = []
  19.             for coin in coins:
  20.                 if amount > coin:
  21.                     tmp = getMin(amount - coin)
  22.                     if tmp != -1: # 可以凑成满足条件金额
  23.                         _min.append(tmp + 1)
  25.             if not _min:
  26.                 return -1
  27.             else:
  28.                 return min(_min)
  30.         return getMin(amount)

方案二（动态规划，完全背包问题）

  1. class Solution:
  2.     def coinChange(self, coins: List[int], amount: int) -> int:
  3.         # 转换成背包问题：
  4.         #   将总金额看做是背包大小，则只需要求出填满背包的最少的硬币数量即可
  5.         dp = [float('inf')] * (amount + 1)  # dp[i] 表示填满背包大小为 i 所需的硬币的最小数量
  6.         dp[0] = 0
  8.         for coin in coins:
  9.             for i in range(coin, amount + 1):
  10.                 dp[i] = min(dp[i], 1 + dp[i - coin])
  12.         return dp[-1] if dp[-1] != float('inf') else -1