零钱兑换
Coin Change
给定若干种硬币面额（每种数量不限）和一个目标金额，求凑出该金额最少需要几枚硬币；凑不出返回 -1。
在力扣中练习题目描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount，表示总金额。
计算并返回可以凑成总金额所需的 最少 的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
示例 2：
输入：coins =[2], amount =3输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
解题思路
完全背包 · 一维 DP
dp[a] = 凑出金额 a 的最少硬币数
先想暴力：每种硬币可以用 0 次、1 次、2 次……把所有组合试一遍是指数级。
用自拟输入 coins = [2, 3, 5], amount = 9 推演。金额 1 不可达，后续需要比较不同硬币提供的候选。若一味先拿最大的硬币，会拿到 5 + 3 后剩 1；正确方案可以是 5 + 2 + 2，只需 3 枚。
但凑出金额 a 的最后一枚硬币只可能是 coins 里的某一个 c。如果最后一枚是 c，前面那部分金额就是 a - c，于是
dp[a] = min(dp[a - c] + 1) 对所有 c ≤ a
dp[a] 表示凑出金额 a 的最少硬币数
dp[0] = 01更优dp[2]=dp[0] + 10 + 1候选 1 · 当前 ∞
它把「凑 a」拆成「凑 a−c，再加一枚 c」，规模严格变小，所以可以从小到大递推。
尝试让最后一枚硬币为 2。
dp[a] 表示凑出金额 a 的最少硬币数
当前∞
dp[2]=∞初始化的两个细节：dp[0] = 0 是唯一的起点；其余填 INF = amount + 1——面额都是正整数，任何可行方案的枚数不会超过 amount，所以这个值能表示不可达，且加一不会溢出 int。最后若 dp[amount] 仍是 INF，返回 -1。
易错点
- 把不可达初始化成 INT_MAX：dp[a-c] + 1 会整型溢出成负数，答案直接错。
- 硬币在外、金额正序在内也能求最少枚数；若把金额倒序扫描，就会限制同一硬币只能用一次。
- 忘记最后判断 dp[amount] == INF，不可达时会返回 INF 本身。
记忆化搜索
自顶向下：dfs(rest) 要什么，就递归去算
正确的记忆化搜索，用递归按需计算同一状态；主解法迭代填表可避免深递归。
同一个转移方程，也可以从 amount 往下递归：
dfs(rest):
rest == 0 → 0
rest < 0 → -1（这枚硬币放不下）
否则 → min(dfs(rest - c) + 1)，取不到的忽略
不加记忆化就是指数级搜索；加上 memo 数组后，每个 rest 只会被真正计算一次，复杂度与递推版相同。
好处是思维更直接：问「凑出 rest 最少要几枚」，答案就是「少用一枚硬币后的子问题 + 1」。适合 DP 转移不太直观、不想先想清楚遍历顺序的场合。
注意 memo 的哨兵值要和真实答案区分开：这里用 -2 表示「没算过」、-1 表示「凑不出」，如果混用 0 或 -1 会造成重复计算或错误缓存。
- 1dfs(rest)：rest < 0 返回 -1，rest == 0 返回 0。
- 2查 memo，命中则直接返回。
- 3枚举每种硬币，递归求子问题，取最小的 + 1。
- 4写入 memo 并返回。
易错点
- memo 的哨兵值选错，导致「凑不出」的结果被反复重算。
- 递归深度可能随 amount 增长，较大输入有栈溢出风险，优先使用迭代。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
coins = [2, 3, 5], amount = 9dp[0] = 0，其余初始化为 INF = 10，画面用 ∞ 表示。
dp[a] 表示凑出金额 a 的最少硬币数
dp[0]=0查看 C++ 代码
延伸阅读
- 这是「完全背包求最小价值」的标准模型：物品可无限取、求最少个数。把 min 换成方案数累加，就变成零钱兑换 II（518）。
- 「用 amount + 1 当无穷」是背包题的常见技巧：既保证比任何合法答案大，又不会在 +1 时溢出。
- 如果要求输出具体的硬币组合，可以额外记录 choice[a] = 最后一枚硬币，再从 amount 倒推。