凑硬币

给定一组硬币面额和目标金额，问最少需要几枚硬币能凑出目标。每种面额可以无限次使用。

这是 DP 入门经典之一。状态定义：

dp[i] = 凑出金额 i 的最少硬币数

转移：枚举每种硬币 c，如果 c ≤ i 而且 dp[i - c] 可达，那么 dp[i] 可以由 dp[i - c] + 1 得到。取所有候选里的最小值。

dp[i] = min(dp[i - c] + 1)，遍历所有可用硬币 c

dp[0] = 0，其余初始视为”无法到达”（图中用 ∞ 表示）。

复杂度

• 时间：O(amount · n)，n 是面额种类数
• 空间：O(amount)

在动画里看什么

• 顶部 是可用的硬币集合；正在被试的硬币会高亮
• DP 表 每一格表示 dp[i]：浅蓝代表”已算出”，深蓝是当前位置，灰色是”还不可达”
• 暖红 是最终目标格 dp[amount]
• 算法结束后下方给出反推的方案（用 prev[i] 记录每个金额是用哪枚硬币凑出来的）