动态规划 · 最少硬币数

初始化 · 建立起点

先给“0 元”一个确定答案

基础情况

从最简单的情况开始初始化

✓ 已固定 · 点击金额可跳转

格子按金额（元）定位；中间大数字是硬币枚数；“末枚”是 choice 记录的面额。

随动画同步

环节

通用规则 · 为什么这样做

本步代入 · 实际如何判断

接下来 →

每种面额都要检查

③ ↔ ④ 尝试其余面额
② → ⑤ 完成后，再算下一个金额

对应算法操作

候选枚数 = dp[x − c] + 1

只尝试 c ≤ x 的面额。候选比旧记录更少才更新；相等或更多都保留旧记录。

这些符号与循环分别指什么

x：本轮金额，单位是元。
c：假设最后一枚的面额，单位是元。
dp[x]：凑 x 元的最少枚数。轮内是暂存的最好结果，轮末才固定。
choice[x]：该方案最后一枚的面额。

外层有 6 轮：金额 1 → 6。每轮依次检查 c = 1、3、4。下面的 50 步是动画拆解，不是 50 轮。

若某个较小金额仍是 ∞，表示尚无可用方案，∞ + 1 仍为 ∞。本例有 1 元硬币，因此每个较小金额都可达。

01 / 50初始化