代码与动画 COIN CHANGE · DP
零钱兑换.
从小金额推导大金额，计算凑出目标金额的最少硬币数。
时间 O(amount × 硬币种类数)空间 O(amount)每种硬币可重复使用
原理与执行逻辑
把目标金额拆成“少一枚硬币的金额”与最后一枚硬币。逐个求出较小金额的最少硬币数，再从所有可用面额中选择最小方案。
执行步骤
- 令 dp[0] = 0，其他金额为 ∞。
- 按金额 x 从小到大遍历。
- 对不大于 x 的每个面额 coin，比较 dp[x] 与 dp[x - coin] + 1。
- 返回 dp[amount]，仍为 ∞ 时返回 -1。
关键理解
dp[x] 表示恰好凑出 x 的最少枚数。同一面额可重复使用，较小金额状态可以再次被引用；不可达状态加一后仍不可达。
简短示例
面额 [1, 3, 4]、金额 6 时，两个 3 只需 2 枚；先取最大面额 4 再补两个 1 则需要 3 枚。
代码与执行动画
STEP 0 / 20function coinChange(coins, amount) { const dp = Array(amount + 1).fill(Infinity); dp[0] = 0; for (let x = 1; x <= amount; x++) { for (const coin of coins) { if (coin <= x) dp[x] = Math.min(dp[x], dp[x - coin] + 1); } } return dp[amount] === Infinity ? -1 : dp[amount];}面额 1, 3, 4
当前数据正在操作已访问 / 命中标记 / 指针
0
初始化 DP
dp[0] = 0，其余金额暂时不可达。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
零钱兑换的操作规则
dp[x] 表示凑出金额 x 的最少硬币数；∞ 表示不可达。目标无法凑出时返回 -1。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目322. 零钱兑换打开题目
直接对应最少硬币数；每种面额可重复使用。