考点归类
完全背包 · 最值型动态规划。硬币无限取用是完全背包的标志，与 0-1 背包的区别只在遍历方向。
思路推导
暴力思路：枚举所有硬币组合（数量不定、可重复），求凑出 amount 的最少枚数 → 指数级爆炸。
优化核心：子问题划分。凑 amount 的最少硬币数 = min(凑 (amount - coin) 的最少硬币数 + 1)，对每个面值取最小。这就是状态转移：
dp[i] = min(dp[i], dp[i - coin] + 1)dp[i]：凑出金额i所需的最少硬币数dp[i-coin] + 1：最后一步用一枚coin从状态i-coin转移过来
为什么外层硬币、内层金额、i 正向？
for (let i = coin; i <= amount; i++) 从小到大遍历，dp[i-coin]（更小下标）先于 dp[i] 被更新，且可能已含有当前这枚 coin → 同一枚硬币可被反复使用 → 完全背包。
若改成倒序 for (let i = amount; i >= coin; i--)，dp[i-coin] 还是旧值 → 每枚硬币至多用一次 → 变成 0-1 背包。验证 coins=[1,3]、amount=6：正序（完全背包）3+3 = 2 枚，倒序（0-1 背包）每个面值最多用一次，最大只能凑 3+1 = 4 < 6，返回 -1。结果不一样（正序允许同枚硬币复用，倒序不允许）。
内外层交换（金额在外层）为什么答案仍正确？
本题只求”最少数量”，不关心硬币排列顺序，1+5 与 5+1 都是两枚。更严谨地说：金额在外层时，dp[i] 依赖的 dp[i-coin]（更小下标）在上一轮外层循环已全部定稿，不会再被本次更新，因此取 Math.min 仍保证不重不漏——“最小值聚合”对遍历顺序不敏感。但对”求组合/排列总数”的题，聚合方式是加法，内外层顺序会改变答案——组合去重用外层硬币，排列计数的外层金额。
完整代码
var coinChange = function (coins, amount) {
let dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0 // 凑 0 元不需要硬币
for (let coin of coins) { // 外层：逐个面值
for (let i = coin; i <= amount; i++) { // 正向：完全背包，硬币无限用
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
// ↑ 不选这枚硬币 ↑ 选这枚，从凑 i-coin 的状态多花 1 枚
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
};复杂度
- 时间 O(amount × n)，n 为硬币面值数
- 空间 O(amount)
易错点
Infinity哨兵：Infinity + 1仍是Infinity，因此dp[amount] === Infinity能判断凑不出来，返回 -1。不要用0或amount+1之外不明确的初始值- i 从 coin 起：
dp[i-coin]最小取dp[0]，不会越界 - 遍历方向：正序 = 完全背包（无限取用），倒序 = 0-1 背包（每件一次），本题目的是无限硬币，必须正序
变体与举一反三
- 518. 零钱兑换 II：求组合总数——外层硬币（去重）写
+；若外层金额则是排列总数，答案会大很多。建议先自己验证coins=[1,2]凑3的两种结果 - 279. 完全平方数：同构题，把硬币换成平方数，
dp[i] = min(dp[i], dp[i - j*j] + 1) - LeetCode Hot100 位运算与动态规划（零钱兑换在 Hot100 系列的位置）
← 速查卡片见 GRD 动态规划