322. 零钱兑换 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/coin-change/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
提示：
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10
题目详细分析
- 数据范围：amount <= 10^4，硬币种类最多 12 种，适合 O(n * amount) 的 DP。
- 核心约束：每种硬币无限使用（完全背包），求最少个数（不是组合数）。
- 边界条件：amount = 0 时返回 0；如果硬币面额都大于 amount 则返回 -1。
- 隐藏条件：可能存在无法凑出的金额，需返回 -1。硬币面额是无序的，注意排序不是必须的。
小白版直白理解
你去商店买东西，需要凑够 amount 元。你口袋里有不同面额的硬币（每种无限多），你想用最少的硬币数付钱。比如要凑 11 元，你有 1 元、2 元、5 元硬币。你会先尽量用 5 元——两个 5 元是 10 元，再加一个 1 元，共 3 个硬币。这就像贪心解法，但注意有些面额组合贪心不一定最优（比如 coins=[1,3,4], amount=6，贪心用 4+1+1 共 3 个，但实际 3+3 只要 2 个），所以需要动态规划。
解题思路
思路一：完全背包 DP（推荐）
核心洞察：对于每个金额 j，如果选择面额 coin 的硬币，则问题变为凑 j-coin 的最少硬币数 + 1。在所有 coin 中取最小值。
DP 五步法：
- dp 定义：
dp[j]表示凑成金额 j 所需的最少硬币数 - 递推公式：
dp[j] = min(dp[j], dp[j - coin] + 1)for coin in coins - 初始化：
dp[0] = 0，dp[1..amount] = amount + 1（一个不可能的大数） - 遍历顺序：先遍历硬币（物品），再正序遍历金额（背包容量）——完全背包标准顺序
- 举例验证：coins=[1,2,5], amount=11 → dp[0]=0, dp[1]=1, dp[2]=1, …, dp[5]=1, dp[10]=2, dp[11]=min(dp[10]+1, dp[9]+1, dp[6]+1)=3 ✓
def coinChange(coins, amount):
# dp[j] 表示凑成金额 j 的最少硬币数
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for coin in coins: # 遍历物品（硬币）
for j in range(coin, amount + 1): # 正序遍历背包容量
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[amount] if dp[amount] != amount + 1 else -1思路二：暴力递归 + 备忘录（自顶向下）
每种面额选或不选，用 memo 记录已计算过的金额。
from functools import lru_cache
def coinChange(coins, amount):
@lru_cache(None)
def dfs(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
min_coins = float('inf')
for coin in coins:
res = dfs(rem - coin)
if res != float('inf'):
min_coins = min(min_coins, res + 1)
return min_coins
ans = dfs(amount)
return ans if ans != float('inf') else -1思路三：BFS 最短路径
将金额看成图中的节点，每次减去一个硬币面额视为一条边，求 amount 到 0 的最短路径。
from collections import deque
def coinChange(coins, amount):
if amount == 0:
return 0
queue = deque([(amount, 0)])
visited = [False] * (amount + 1)
visited[amount] = True
while queue:
cur, step = queue.popleft()
for coin in coins:
nxt = cur - coin
if nxt == 0:
return step + 1
if nxt > 0 and not visited[nxt]:
visited[nxt] = True
queue.append((nxt, step + 1))
return -1易错点
- 返回 -1 的判断：用
amount + 1作为不可能达到的初值，最后检查dp[amount]是否仍为初值。 - amount = 0：直接返回 0，因为 dp[0] 已初始化为 0。
- 硬币面额大小：coins[i] 可能大于 amount，遍历背包时
range(coin, amount+1)自动跳过。 - 完全背包 vs 0-1 背包：一维完全背包正序遍历，0-1 背包倒序遍历。顺序反了会导致结果错误。
框架提炼
完全背包（求最小值）模板：
def complete_knapsack_min(coins, target):
dp = [float('inf')] * (target + 1)
dp[0] = 0
for coin in coins: # 遍历物品
for j in range(coin, target + 1): # 正序遍历容量
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[target] if dp[target] != float('inf') else -1完全背包（求组合数）模板与最小值模板的区别：
- 最小值：
dp[j] = min(dp[j], dp[j - coin] + 1)，初值 inf - 组合数：
dp[j] += dp[j - coin]，初值 dp[0] = 1
关联题目
- 279-完全平方数 — 完全平方数就是特殊面额的”硬币”，思路完全一致
- 416-分割等和子集 — 0-1 背包，区分完全背包与 0-1 背包的遍历顺序差异
- 139-单词拆分 — 完全背包的字符串版本，dp 类型变为布尔值