动态规划第 八 课——作业查重系统（小学版）

—— 谁抄了我的作业？（最长公共子序列 LCS）

• 课时时长：90 分钟

• 核心目标：

  1. 概念区分：彻底分清 子串 (连续) 与 子序列 (不连续) 的区别。
  2. 模型构建：掌握双序列 DP 的二维表格画法。
  3. 核心逻辑：理解“斜着走 (+1)”与“横竖走 (继承)”的状态转移方程。
  4. 实战应用：解决经典的字符串匹配问题。

• 所需教具：

  • 黑板与彩色粉笔。
  • 磁力贴字母卡片（A, B, C, D, E 等）。
  • 一张打印好的大网格纸（用于模拟填表）。

课程时间表

详细教学流程

1. 引入：狡猾的抄袭者 (10分钟)

• 故事开场： > “同学们，小明写了一篇满分作文，内容是 ABCDE。小红想抄作业，但她很聪明，怕被老师发现，所以她删掉了几个字，改成了 ACE。”

• 概念辨析：

  • 子串 (Substring)：必须是连在一起的，比如 BCD。
  • 子序列 (Subsequence)：可以跳着选，但顺序不能乱。比如 ACE 就是跳着抄的。
  • 提问：AEC 是小明的子序列吗？
  • 回答：不是！因为小明的作文里 E 在 C 后面，小红把顺序搞反了，露馅了！

• 任务发布：

  “老师要写一个‘查重系统’，专门找出两个人写的一样的字，而且顺序要对。找出来的字越多，说明抄袭嫌疑越大！”

2. 可视化：侦探的坐标系 (15 min)

• 绘图准备：

  • 在黑板上画一个网格。
  • 横轴 (X)：小明的作文 A B C D E (长度 5)。
  • 纵轴 (Y)：小红的作文 A C E (长度 3)。
  • 关键点：必须多画一行一列！ (第 0 行和第 0 列)。
  • 解释：第 0 行代表“小明一个字都没写”，第 0 列代表“小红一个字都没写”。这种情况下，共同点当然是 0。

• DP 数组含义：

  • dp[i][j] 代表：
    • 横轴看到第 i 个字。
    • 纵轴看到第 j 个字。
    • 这时候，他们最多有多少个相同的字？

3. 核心：填表规则——撞衫与继承 (25 min) <-- 核心难点

• 互动填表（手把手演示）：

  • 场景 1：撞衫了（字符相同）
    • 看格子 (1, 1)：横轴是 A，纵轴是 A。
    • “哇！第一个字就一样！抓住了！”
    • 动作：我们在这个格子里填 1。
    • 来源：这个 1 是怎么来的？是在“谁都没写 (0,0)”的基础上 +1 的。
    • 规则 1：字母相同 ↘️ 斜着走！ (找左上角的兄弟 dp[i-1][j-1] + 1)。

• 场景 2：没对上（字符不同）

  • 看格子 (2, 1)：横轴是 B，纵轴是 A。
  • “不一样！B 和 A 配不上。”
  • 思考：虽然 B 配不上 A，但小明前面的 A 和小红的 A 是配得上的呀！不能因为多写了个 B 就把之前的功劳抹杀掉。

  • 观察：

    • 看看左边 (1, 1)：小明只有 A 时，匹配了 1 个。
    • 看看上边 (2, 0)：小红没写字时，匹配了 0 个。
    • 决策：选最大的！继承左边的 1。

  • 规则 2：字母不同 ⬇️ 或 ➡️ 侧着走！ (继承左边或上边的最大值 max(dp[i-1][j], dp[i][j-1]))。

• 继续推演 (关键点)：

  • 填到 (3, 2) 时：横轴 C，纵轴 C。
  • 一样！斜着找左上角 (2, 1) 的值。
  • dp[2][1] 是 1 (之前匹配了A)，所以 1 + 1 = 2。
  • 现在的 LCS 是 AC。

• 最终结果：

  • 填到右下角，结果是 3。说明 LCS 是 ACE。

4. 代码：翻译官 (20 min)

• 数据准备：

  • 字符串下标是个大坑。为了配合 DP 数组从 1 开始，我们教学生一个小技巧：给字符串前面垫个空格。

  string s1, s2;
  cin >> s1 >> s2;
  int n = s1.length();
  int m = s2.length();
  
  // 垫个空格，让下标对齐 (或者直接用 s1[i-1] 但容易晕)
  s1 = " " + s1; 
  s2 = " " + s2;
  
  int dp[1005][1005]; // 二维表格
  

• 核心逻辑：

  for(int i = 1; i <= n; i++) {       // 遍历小明的作文
          for(int j = 1; j <= m; j++) {   // 遍历小红的作文
                  if(s1[i] == s2[j]) {
                          // 规则1：撞衫了！斜着走 + 1
                          dp[i][j] = dp[i-1][j-1] + 1;
                  } else {
                          // 规则2：没对上。继承左边或上边最好的成绩
                          dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                  }
          }
  }
  cout << dp[n][m]; // 输出右下角的最终结果
  

5. 实战：洛谷 P1439 (20 min)

• 题目介绍：

  • 题目名称：【模板】最长公共子序列
  • 虽然题目数据范围很大 ()，标准解法需要 的 LIS 转换技巧。
  • 但在本节课，我们先提交我们刚写的 代码。
  • 预期结果：会拿 50 分（因为超时）。

• 教学意义：

  • 告诉学生：“看！我们的逻辑是对的，只是不够快。对于几千个字的作文，这个程序是完美的。对于几万个字的作文，我们以后会学习更高级的魔法（LIS 转换）来解决它。”
  • 任务：能够独立写出 的朴素版 LCS 代码并运行通过样例。

课后作业：侦探笔记

1. 手绘作业：画出 BDCAB 和 DABC 的 DP 表格，并圈出 LCS 是哪几个字？（答案应该是 ABC 或 DAB，长度 3）。
2. 代码练习：在 OJ 上提交代码，通过 50% 的测试点。
3. 思考题：如果要求“最长公共子串”（必须连续），表格的填法哪里要改？
   • 提示：如果字符不一样，还能继承吗？断了就是断了，要归零！

给教练的建议

• 关于下标：我强烈建议使用 s1 = " " + s1 这种“垫空格大法”。对于小学生来说，处理 dp[i] 对应 s[i-1] 这种错位逻辑非常痛苦，垫空格可以让逻辑完美对齐，减少 50% 的 Bug。
• 关于箭头：在黑板演示填表时，一定要画箭头。
  • ↘️ 红色箭头代表“命中”。
  • ➡️ ⬇️ 蓝色箭头代表“继承”。
  • 这能帮学生建立动态的路径感。