动态规划第六课——神奇的消失墨水（小学版）

—— 像黑客一样节省内存（空间优化）

• 课时时长：90 分钟

• 核心目标：

  1. 痛点感知：理解为什么二维数组会“爆内存”（MLE）。
  2. 概念突破：理解滚动数组（一维 DP）的核心思想——覆盖。
  3. 难点攻克：彻底掌握 0/1 背包必须“倒着算”的原理。
  4. 代码进化：将二维背包代码重构为一维。

• 所需教具：

  • 黑板（必须有）。
  • 不同颜色的粉笔（白色代表旧数据，红色代表新数据）。
  • 黑板擦（本节课的神器）。
  • 一张巨大的纸（画满格子）和一张小纸条（画一行格子）。

课程时间表

详细教学流程

1. 引入：挤爆的仓库 (10分钟)

• 回顾：展示第 3 课的“小偷背包”二维表格。

• 危机降临：

  • “同学们，以前我们的背包只有 10kg，物品只有 5 个，表格很小。”
  • “但是，今天国王发布了一个超级任务：背包容量是 10万，物品有 1万 个！”
  • 算一算： \(100,000 \times 10,000 = 10亿\) 个格子！

• 演示：老师拿出一张画满格子的巨大纸张，假装拿不动，掉在地上。

  • “电脑的内存就像这个仓库，装不下这么多格子。如果我们强行申请 int dp[10000][100000]，电脑会直接罢工（MLE - Memory Limit Exceeded）。”

• 目标：我们要把这个巨大的仓库，压缩成这一个小纸条（展示手里的一行格子纸条）。

2. 概念：神奇的复写纸 (15分钟)

• 观察发现：

  • 让学生看旧的二维表。
  • “当我们填第 5 行的时候，第 1、2、3 行的数据还有用吗？”
  • 学生回答：没用了，只看第 4 行。
  • “没错！以前的数据都是垃圾。既然是垃圾，为什么要占地方？”

• 新策略：

  • 我们只申请一行数组 dp[j]。
  • 这一行里，刚开始存的是“第 0 行”的数据。
  • 算“第 1 行”时，直接把结果写在原来的格子上（覆盖旧数据）。
  • 就像用了一种“消失墨水”，新数据写上去，旧数据就自动消失了。

3. 核心：黑板擦大冒险 (30分钟) <-- 绝对难点，必须互动

• 场景设置：

  • 在黑板上画一行格子（容量 0 ~ 10）。
  • 初始状态：填入上一轮的数据（假设物品 A，重量 3，价值 10）。
  • 现在的格子（旧数据）：[0, 0, 0, 10, 10, 10, 10, 10, 10, 10, 10] (意思：只要容量>=3，价值就是10)
  • 新任务：现在来了物品 B（重量 2，价值 20）。我们要更新这一行格子。

• 错误演示（从左往右擦）：

  • 老师：我们试试从左边开始算。
  • 算容量 2：能装下 B 吗？能！价值 = 20。
  • 动作：老师用红色粉笔把容量 2 的格子改成 20。
  • 黑板现状：容量 2 是红色(新)，容量 3 是白色(旧)...

  • 继续算容量 4：

    • 公式：dp[4] = max(不拿, dp[4-2] + 20)。
    • 关键点：老师指着 dp[4-2] 也就是 dp[2]。
    • “看！dp[2] 是什么颜色？红色的！是刚刚更新过的！这意味着什么？”
    • “意味着我们在这一轮里，已经拿了一个物品 B。现在我们在 dp[2] 的基础上再加 20，等于拿了两个物品 B！”

  • 结论：从左往右擦，变成了“自助餐模式”（完全背包），数据被污染了！

• 正确演示（从右往左擦）：

  • 老师把黑板复原。
  • 老师：这次我们从屁股后面（容量 10）开始算。

  • 算容量 4：

    • 需要查 dp[4-2] 也就是 dp[2]。
    • “看 dp[2] 是什么颜色？白色的！是上一轮的数据。说明还没拿过物品 B。”
    • 动作：算出结果 10+20=30，把容量 4 改成红色。

  • 继续算容量 2：

    • 直接覆盖成 20。

  • 结论：倒着擦，永远查的是“旧账本”，保证每个物品只拿一次！

• 口诀记忆：

  • 0/1 背包（只有一件） 倒车请注意（从右向左）。
  • 完全背包（无限件） 大步向前走（从左向右）。

4. 代码：整形手术 (20分钟)

• 手术台对比： 在 PPT 或黑板上左右分栏展示。

  二维代码 (旧版)	一维代码 (黑客版)
  int dp[105][1005];	int dp[1005]; // 只有一行！
  for(int i=1; i<=n; i++) {	for(int i=1; i<=n; i++) {
  for(int j=0; j<=V; j++) {	for(int j=V; j>=w[i]; j--) { <-- 倒序！
  if(j >= w[i])	// if 省略了，因为循环只到 w[i]
  dp[i][j] = max(	dp[j] = max(
  dp[i-1][j],	dp[j], // 不拿，就是原来的自己
  dp[i-1][j-w[i]]+v[i]	dp[j-w[i]] + v[i]
  );	);
  else dp[i][j]=dp[i-1][j];	// else 也不用了，不改就是继承
  }	}
  }	}

• 代码解读：

  1. 数组变小：直接砍掉 [105]。
  2. 内层循环：j 从 V 开始，走到 w[i] 结束（比 w[i] 小的肯定装不下，不用动，直接保留旧数据，连 if 都省了）。
  3. 状态转移：dp[j] (新) = max(dp[j](旧), dp[j-w] + v)。

5. 总结与实战 (15分钟)

• 实战演练：

  • 拿出一道简单的背包题（物品少一点）。
  • 让学生在纸上只画一行格子。
  • 每读入一个物品，就用橡皮擦擦掉旧数字，写上新数字。
  • 体验“滚动”的感觉。

• 高手认证： > “恭喜大家！你们现在的代码，不仅速度快，而且占用的内存只有别人的 1%。在真正的编程比赛（CSP/NOI）中，这种技巧叫做‘空间优化’，这是从菜鸟迈向高手的必经之路！”

课后作业：空间魔术师

1. 基础题：把之前写的“采药”或“小偷背包”代码，全部改为一维数组版本，并提交通过。
2. 思考题：如果是“完全背包”（自助餐，物品无限拿），一维数组应该怎么写？（提示：回忆黑板擦从左往右擦的过程）。
3. 挑战题：LeetCode 416. 分割等和子集（Partition Equal Subset Sum）。试着用一维 DP 解决它。

给教练的建议

• 必须手动模拟：不要指望小学生能凭空想象“数据覆盖”的过程。黑板擦或者 PPT 动画是必须的。
• 不要讲 i%2：有些教材教滚动数组用 dp[2][j] 然后 dp[i%2] 和 dp[(i-1)%2]。千万别教这个！ 对于小学生来说，取模运算不仅难理解，而且代码写起来容易错。直接教 dp[j] 一维数组最直观，也是最终形态。
• 强调 j 的范围：j >= w[i] 是个很棒的优化，要告诉学生这比 if 语句更酷，因为它连循环次数都减少了。