LeetCode LCR 103. 零钱兑换
目录
题目描述
题意分析
给若干种面额的硬币和一个总金额
amount，问凑出这个金额最少需要多少枚硬币；凑不出来返回-1。每种硬币的数量是无限的。三个词决定了整道题的形态。「最少」说明这是最优化问题，状态里存的是最小枚数；「无限」说明同一面额可以反复使用，这与「每样只能拿一次」的取舍完全不同；「凑不出返回 -1」说明必须有一个能与真实答案区分开的「不可达」标记。
约束里
amount ≤ 10^4、硬币种类≤ 12，而面额本身可以大到 $2^{31} - 1$。金额小、种类少，说明可以拿金额当下标做一张表；面额可能极大，说明要小心j - coin这类下标运算的越界与溢出。一个容易被忽略的信号：答案只与「还差多少钱」有关，与「已经用过哪些硬币、按什么顺序用」无关。凑出 6 元用了
1+5还是5+1，对后续没有任何区别。这条无后效性正是可以做递推的前提。边界有三处：
amount = 0时答案是 0 枚而不是 -1；某些金额天然凑不出（比如只有面额 2 却要凑 3）；金额可达时答案上界是amount枚（全用面额 1 的极端情形），这个上界后面会被借用来当「不可达」的哨兵值。
解法：动态规划递推
核心思路
暴力做法是搜索：每一步选一枚硬币扣掉，递归求剩余金额的最优解。这棵树的分支数是硬币种类、深度是
amount / minCoin，指数级爆炸，amount = 10^4时毫无希望。瓶颈在于同一个「剩余金额」被反复求解。凑 11 元时，先拿 1 再拿 2、和先拿 2 再拿 1，都会落到「还剩 8 元」这个子问题上，而这个子问题的答案是唯一确定的。把「剩余金额」当作状态把重复分支合并，指数树立刻塌成一维数组。
由此得到状态定义：
dp[j]= 凑出金额j所需的最少硬币数；若凑不出，dp[j]保持一个大于任何合法答案的哨兵值。初始状态
dp[0] = 0：金额 0 不需要任何硬币，这是全部递推的根。其余位置初始化为哨兵amount + 1——之所以选这个值而不是Integer.MAX_VALUE，是因为合法答案最多是amount枚（全用面额 1），所以amount + 1一定大于任何真实答案，可以安全地当作「不可达」；同时它不会在dp[j - coin] + 1里溢出，而MAX_VALUE + 1会翻成负数。转移方程：
dp[j] = min(dp[j], dp[j - coin] + 1)。含义是「凑j元」要么沿用不使用当前面额的旧答案，要么先凑出j - coin元再补上一枚coin。不变量在这里和 0-1 背包恰好相反：处理面额
coin时，读到的dp[j - coin]应当是已经允许使用coin的那一版，因为同一面额可以拿任意多枚。要让这条不变量成立，内层容量必须正序遍历——正序时dp[j - coin]在本轮已被更新过，天然包含了「再多拿一枚coin」的可能。这就是完全背包与 0-1 背包在代码上唯一的区别。最后检查
dp[amount]是否还停在哨兵值：是则返回 -1，否则返回它本身。
解题步骤
- 开长度
amount + 1的数组dp，整体填成amount + 1。为什么长度要+1：下标要覆盖金额 0 到amount。为什么哨兵取amount + 1：它严格大于任何合法答案（最多amount枚），又足够小以避免加法溢出，一个值同时解决了「不可达标记」和「取最小值时不被误选」两件事。- 置
dp[0] = 0。为什么：凑 0 元用 0 枚硬币，这是唯一的天然已知解；漏掉它整张表都无法启动，所有金额都会被判成不可达。- 外层遍历面额
coin。为什么按面额分层：每种面额独立地把「多拿一枚」的能力灌进整张表，层与层之间互不干扰，写起来也不必关心面额的顺序。- 内层从
j = coin正序遍历到amount。为什么下界是coin：金额小于面额时根本放不下这枚硬币，且j - coin会越界；把下界写成coin比在循环体里加if更干净，也顺手挡掉了面额大到超过amount的极端输入（此时内层一次都不执行）。为什么正序：维持「dp[j - coin]已允许使用coin」这条不变量，从而支持同一面额取无限枚。- 执行
dp[j] = min(dp[j], dp[j - coin] + 1)。为什么加 1：dp[j - coin]是凑出剩余部分的最少枚数，补上当前这一枚就是j的一个候选解；取min是因为要在「不用这枚」和「用这枚」之间保留更优的。- 返回
dp[amount] > amount ? -1 : dp[amount]。为什么用> amount判断而不是== amount + 1：两者在本实现下等价，但> amount的写法把「任何超出合法上界的值都视为不可达」这一语义写死，即使哨兵换成别的大数也不会失效。以
coins = [1, 2, 5]、amount = 11走一遍。哨兵是 12，初始dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]。处理
coin = 1：j从 1 正序到 11，每一步dp[j] = min(dp[j], dp[j-1] + 1)，于是dp变成[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]。这正是「只有 1 元硬币」的答案，也印证了合法答案的上界确实是amount。处理
coin = 2：j从 2 正序到 11。dp[2] = min(2, dp[0]+1) = 1；dp[3] = min(3, dp[1]+1) = 2；dp[4] = min(4, dp[2]+1) = 2——注意这里读到的dp[2]已经是本轮刚更新过的 1，也就是说 4 元用了两枚 2 元，同一面额被重复使用，正是正序想要的效果。继续下去得到[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]。处理
coin = 5：j从 5 正序到 11。dp[5] = min(3, dp[0]+1) = 1；dp[6] = min(3, dp[1]+1) = 2；dp[7] = min(4, dp[2]+1) = 2；dp[10] = min(5, dp[5]+1) = 2；dp[11] = min(6, dp[6]+1) = 3。最终dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]。
dp[11] = 3 ≤ 11，返回 3，对应5 + 5 + 1。再看不可达用例
coins = [2]、amount = 3：哨兵是 4，处理coin = 2时只更新dp[2] = 1，dp[3] = min(4, dp[1] + 1) = min(4, 5) = 4仍是哨兵。最后dp[3] = 4 > 3，返回 -1。注意这里dp[1] + 1 = 5比哨兵还大，说明「从一个不可达状态转移出来」产生的候选值只会更差，不会污染结果——这正是哨兵取amount + 1而非MAX_VALUE却依然安全的原因。
代码实现
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// amount + 1 严格大于任何合法答案，充当「不可达」哨兵且不会溢出。
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
// 正序遍历，dp[j - coin] 已包含本面额，允许同一面额取多枚。
for (int j = coin; j <= amount; ++j) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
// amount + 1 严格大于任何合法答案，充当「不可达」哨兵且不会溢出。
for i := 1; i <= amount; i++ {
dp[i] = amount + 1
}
for _, coin := range coins {
// 正序遍历，dp[j-coin] 已包含本面额，允许同一面额取多枚。
for j := coin; j <= amount; j++ {
dp[j] = min(dp[j], dp[j-coin]+1)
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
复杂度分析
- 时间复杂度：$O(n \cdot amount)$，其中 $n$ 是硬币种类数。凭什么：外层遍历 $n$ 种面额，内层最多遍历
amount个金额，循环体只有一次比较和赋值。本题上界约 $12 \times 10^4$，非常宽松。- 空间复杂度：$O(amount)$。凭什么：只维护一维长度为
amount + 1的数组，面额那一维被滚动掉了；相比二维写法的 $O(n \cdot amount)$，空间少了一个数量级。
关键点总结
- 完全背包正序、0-1 背包倒序，差别只有内层循环方向一个字符，但语义完全相反：正序让
dp[j-coin]已含当前面额（可重复取），倒序让它不含（只能取一次）。面试时要能一句话说清楚这个对应关系。- 「不可达」不要用
Integer.MAX_VALUE，而要用一个刚好大于答案上界的哨兵（这里是amount + 1）。这样dp[j - coin] + 1永不溢出，也不需要在转移里额外写「前驱是否可达」的判断。- 内层循环的下界写成
j = coin而非j = 0加if，一次同时解决了下标越界、面额超过总额、以及无谓的空转三件事。- 求最少枚数时状态存「最优值」、求方案数时状态存「计数」，两者共用同一张表结构；能主动指出这一点，就能顺势答出 518 题的变形。
- 面试视角：本题也可以用 BFS 求最短路（把金额看作节点、面额看作边权为 1 的边），能同时给出 DP 和 BFS 两种视角并说明二者复杂度相同，是加分项。
- 「答案与已用硬币的顺序无关」这条无后效性要主动说出来，它是把搜索改写成递推的合法性依据。
易错点总结
dp[0]忘记置 0：coins = [1]、amount = 1时整张表都是哨兵，返回 -1 而正确答案是 1。- 哨兵用
Integer.MAX_VALUE：coins = [2]、amount = 3时计算dp[1] + 1得到MAX_VALUE + 1，溢出成Integer.MIN_VALUE，min会选中它，最终返回一个负数而不是 -1。- 内层容量倒序：
coins = [1, 2, 5]、amount = 4时每种面额只能取一枚，返回2 + 1 + ...的错误组合数；对coins = [2]、amount = 4更直接——倒序时dp[4]读到的dp[2]还是哨兵，结果判成 -1，而正确答案是 2。- 内层下界写成
j = 0且不判j >= coin：coin = 5、j = 2时访问dp[-3]，Java 抛越界异常、Go panic。- 忘记处理
amount = 0：若在开头写if (amount == 0) return -1之类的「防御性」特判，coins = [1]、amount = 0会返回 -1，而正确答案是 0；主逻辑本来就能自然覆盖，不该加这个特判。- 返回值只判
== amount + 1：若哨兵初值被误写成amount + 2，coins = [2]、amount = 3会把哨兵当成合法答案返回 5。用> amount判断更稳。- 把
min(dp[j], dp[j - coin] + 1)写成dp[j - coin] + 1：coins = [1, 2]、amount = 2时dp[2]会被面额 2 之后的计算覆盖成更差的值，丢掉已经求得的最优解。- 面额可能大于
amount却未处理：coins = [2147483647]、amount = 2时若内层从 0 开始并计算j - coin，会得到极大的负下标；以j = coin起步的写法内层一次都不进入，天然安全。- 误以为贪心「先拿大面额」可行：
coins = [1, 3, 4]、amount = 6时贪心得到4 + 1 + 1共 3 枚，而最优是3 + 3共 2 枚。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 322. 零钱兑换 | 中等 | 与本题同题，可直接套用同一份代码 |
| 518. 零钱兑换 II | 中等 | 求组合数而非最少枚数，状态改存计数，且面额必须在外层去重 |
| 279. 完全平方数 | 中等 | 面额不是给定的，而是要现场生成所有不超过 n 的完全平方数 |
| 377. 组合总和 Ⅳ | 中等 | 求排列数，必须金额在外层、面额在内层，循环顺序与本题相反 |
| 1449. 数位成本和为目标值的最大数字 | 困难 | 成本必须恰好用完，且要在长度相同的候选中比较字典序拼出大数 |
| 面试题 08.11. 硬币 | 中等 | 面额固定为 1/5/10/25，求组合数并要求对 $10^9+7$ 取模 |
| LCR 104. 组合总和 Ⅳ | 中等 | 与 377 同题，用来对照「组合数」与「排列数」的循环顺序差异 |