动态规划第五课——最懒惰的收银员（凑钱问题）（小学版）

课时安排： 90 分钟
核心目标：
1. 思维反转：从“求最大价值（Max）”转变为“求最小数量（Min）”。
2. 打破直觉：通过反例证明为什么“贪心算法（先拿大的）”是错的。
3. 工程细节：理解为什么求 Min 时，数组初始化必须是“无穷大”。

第一部分：情景引入——重力星球的烦恼（15分钟）

角色反转：
- “同学们，前几节课我们是‘大胃王’，想把背包塞得越满越好。今天我们要变身了，我们是‘重力星球的收银员’。”
- “在这个星球，硬币是用铅做的，超级重！比如你要找给顾客 15 块钱，如果你给他 15 个 1 块的硬币，顾客会因为太重拿不动而投诉你。”
- 核心任务： 用最少数量的硬币，凑出目标的金额。（我们要偷懒，少搬砖！）
直觉陷阱（贪心必死）：
- 出题： 硬币面值有 1元, 3元, 4元。我们要凑 6元。
- 学生直觉（贪心）： “这还不简单？先拿最大的！”
  - 先拿 4元，还差 2元。
  - 4元 拿不了了，3元 也拿不了。
  - 只能拿两个 1元。
  - 结果： 4 + 1 + 1 = 3 枚硬币。
- 上帝视角（DP）：
  - “但是，如果有个聪明的收银员，他没拿最大的 4，而是拿了 3元...”
  - 还差 3元，再拿一个 3元。
  - 结果： 3 + 3 = 2 枚硬币！
- 结论： “看到了吗？眼前的贪婪（拿最大的）会让你多干活！ 贪心算法在这里失效了，我们必须请回那个‘聪明的记账本’。”

第二部分：填表逻辑——寻找“谁是最近的邻居”（30分钟）

定义状态（一维数组）：
- 画一条长长的格子（数轴），代表要凑的金额 0, 1, 2, ... 6。
- 这一次，格子里填的不是“价值”，而是“最少硬币数”。
初始化（埋雷环节）：
- “dp[0] 是多少？凑 0 元需要 0 个硬币。填 0。”
- “dp[1] 到 dp[6] 先填什么？”
- 错误引导： “如果像以前一样填 0 会怎样？”
  - “电脑会想：凑 6 元？我要取 min(0, ...)，哇！0 最小！所以凑 6 元只需要 0 个硬币！——这不就变成魔术了吗？”
- 正确做法： “我们要找‘最少’，0 就是那个最大的捣乱鬼。所以，还没算过的格子，统统填上 99999（代表‘不可能’/‘无穷大’）。就像给没去过的地方筑起高墙。”
手动推导（利用完全背包的“正序”逻辑）：
- 硬币： 1, 3, 4
- 从左往右走（正序）：
  - 走到 1： 只能用 1 元。dp[1] = dp[0] + 1 = 1。
  - 走到 2： 只能用 1 元。dp[2] = dp[1] + 1 = 2。
  - 走到 3（关键）：
    - 方案A（用1元）：从 dp[2] 走一步 \(\rightarrow\) 2 + 1 = 3。
    - 方案B（用3元）：从 dp[0] 走一步 \(\rightarrow\) 0 + 1 = 1。
    - PK： min(3, 1)，选方案B！dp[3] 更新为 1。
  - 走到 4：
    - 方案A（用1元）：从 dp[3] 走一步 \(\rightarrow\) 1 + 1 = 2。
    - 方案B（用3元）：从 dp[1] 走一步 \(\rightarrow\) 1 + 1 = 2。
    - 方案C（用4元）：从 dp[0] 走一步 \(\rightarrow\) 0 + 1 = 1。
    - PK： 选最小的！dp[4] 更新为 1。
  - 走到 6（揭秘刚才的陷阱）：
    - ...
    - 方案B（用3元）：回头看 dp[6-3] 也就是 dp[3]。查表发现 dp[3] 是 1。所以 1 + 1 = 2。
    - 方案C（用4元）：回头看 dp[6-4] 也就是 dp[2]。查表发现 dp[2] 是 2。所以 2 + 1 = 3。
    - 最终胜利： 选方案 B，答案是 2。

第三部分：公式与代码（25分钟）

公式微调：
- 以前求最大值： dp[j] = max(dp[j], dp[j-w] + v)
- 现在求最小值： dp[j] = min(dp[j], dp[j-coin] + 1)
- 提问： “为什么要 +1？”
- 回答： “因为你刚拿了一枚硬币呀！动作次数加 1。”

代码模板（C++）：

// 1. 初始化是关键！
// 假设我们要凑 amount 块钱
vector<int> dp(amount + 1, 99999); 
dp[0] = 0; // 起点

// 2. 遍历顺序
// 问：硬币能重复拿吗？能！
// 答：既然是“无限拿”，那就是完全背包，要“正着跑”！
for (int i = 0; i < n; i++) { // 遍历每种硬币
        for (int j = coins[i]; j <= amount; j++) { // 正序遍历金额
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        }
}

特殊情况处理：
- “如果在重力星球，只有 2 块钱的硬币，你要凑 3 块钱，能凑出来吗？”
- “不能。这时候 dp[3] 里面还是那个 99999。”
- “题目通常要求，如果凑不出，返回 -1。所以最后要加个判断：if (dp[amount] == 99999) return -1;”

第四部分：总结口诀（20分钟）

回顾核心差异：
- Max 问题： 初始全为 0，用 max 选大的。
- Min 问题： 初始无穷大，用 min 选小的。
朗朗上口：

“凑钱要想硬币少，

不能只捡大的找。

初始设成无穷大，

回头看看哪步小。”

课后作业：
- LeetCode 322. 零钱兑换

教练备课 Tips（避坑指南）

关于初始化的数值：
- 不要直接教 INT_MAX，因为 INT_MAX + 1 会爆掉变成负数。
- 对小学生来说，amount + 1 或者 99999 这种具体的“大数”更安全，也更好理解。
完全背包的复习：
- 这一课是巩固“正序循环”的绝佳机会。反复强调：“因为我要基于‘刚拿了这个硬币’的状态继续拿，所以我需要这一行的新数据，所以要从左往右。”
调试技巧：
- 如果学生算出的结果不对，让他们把 dp 数组打印出来。
- 如果看到全是 0，就是没初始化。
- 如果看到负数，就是用了 INT_MAX 导致溢出。