动态规划第 九 课——功夫熊猫的跳跃（小学版）

—— 只有比我矮的才能踩（最长上升子序列 LIS）

• 课时时长：90 分钟

• 核心目标：

  1. 思维突破：从“看邻居”升级为“扫描历史”（双重循环逻辑）。
  2. 状态定义：理解 dp[i] 代表“必须以第 i 个桩子结尾”的最大步数。
  3. 难点攻克：理解为什么要初始化为 1，以及为什么**最终答案不是 dp[n]**。
  4. 实战应用：解决 LIS（Longest Increasing Subsequence）问题。

• 所需教具：

  • 5 张打印了数字的大贴纸（1, 7, 3, 5, 9）。
  • 黑板与粉笔。
  • 奖励小贴纸（用来标记“最大步数”）。

课程时间表

详细教学流程

1. 引入：师父的规矩 (10 min)

• 故事背景：

  “功夫熊猫阿宝要练轻功。师父在地上打了一排高低不平的梅花桩，高度分别是 1, 7, 3, 5, 9。”

• 铁律：

  1. 只能往右边跳（时间不能倒流）。
  2. 只能往高处跳（步步高升，矮的桩子踩不上去）。
  3. 目标：阿宝想知道，他最多能连续踩几个桩子？

• 直觉挑战：

  • 让学生盯着数组 1, 7, 3, 5, 9 看。

  • 学生尝试：

    • 路线 A：1 -> 7 -> 9 (踩了 3 个)
    • 路线 B：1 -> 3 -> 5 -> 9 (踩了 4 个！赢了！)

  • 提问：“如果桩子有 1000 个，眼睛看不过来怎么办？我们需要教电脑一种‘思考方法’。”

2. 互动：真人 DP 演示 (20 min) <-- 核心物理建模

• 角色扮演：

  • 请 5 位高矮不一的同学上台，排成一排。
  • 给他们贴上数字号码牌：1, 7, 3, 5, 9。
  • 每个同学手里拿一只粉笔，准备写自己的“战绩” (dp值)。

• 推演过程（采访模式）：

  • 第 1 位同学 (高度 1)：

    • 老师：“你前面有人吗？”
    • 学生：“没人。”
    • 老师：“那你自己就是第 1 步。在手里写 1。”

  • 第 2 位同学 (高度 7)：

    • 老师：“回头看看，你能从谁身上跳过来？”
    • 学生：“1 比我矮，可以跳。”
    • 老师：“1 的战绩是 1，你接在他后面，你的战绩是多少？”
    • 学生：“1 + 1 = 2。” (写上 2)

  • 第 3 位同学 (高度 3)：

    • 老师：“回头看看，如果你从 7 跳过来行吗？” (不行，7太高)。
    • “从 1 跳过来行吗？” (行)。
    • “那你的战绩是？” (1 + 1 = 2)。

  • 第 4 位同学 (高度 5) —— 关键点！：

    • 老师：“重点来了！ 回头看，你能踩谁？”

    • 学生扫描：

      • 看到 1 (战绩1)：如果接他，我是 2。
      • 看到 7 (战绩2)：太高，踩不了。
      • 看到 3 (战绩2)：比我矮，能踩！如果接他，我是 2 + 1 = 3！

    • 老师：“你有两个选择（接1或接3），你选哪个？”

    • 学生：“当然选战绩最好的师兄！我选 3，所以我现在的战绩是 3。”

  • 第 5 位同学 (高度 9)：

    • 回头扫描所有人：1, 7, 3, 5 都比我矮。
    • 谁最强？5 最强（战绩是3）。
    • 抱住 5 的大腿，我的战绩是 3 + 1 = 4！

• 总结逻辑：“我要想站得高，就得回头在所有比我矮的人里面，挑一个最强的，接在他后面！”

3. 逻辑：接力赛逻辑 (20 min)

• 定义 dp[i]：

  • 很多学生会以为 dp[i] 是“前 i 个桩子的最大值”。
  • 纠正：dp[i] 代表“必须踩中第 i 个桩子”时的最大步数。

• 初始化：

  • 每个人刚站上去的时候，至少踩了自己脚下这 1 个。所以所有 dp[i] = 1。

• 状态转移方程：

  • 对于每一个 i (现在的我)：
  • 循环 j 从 1 到 i-1 (回头看所有的师兄)：
  • 如果 height[i] > height[j] (只要他比我矮)：
    • dp[i] = max(dp[i], dp[j] + 1) (挑战一下：是保持现状，还是接在他后面更强？)

4. 代码：双重循环 (25 min)

• 板书代码框架：

  int a[105]; // 桩子高度
  int dp[105]; // 记录每个桩子的最好战绩
  int n; // 桩子个数
  
  cin >> n;
  for(int i=1; i<=n; i++) {
          cin >> a[i];
          dp[i] = 1; // 初始化：每个人最少都是 1（自己）
  }
  
  // 外层循环：我是当前的桩子 i
  for(int i = 1; i <= n; i++) {
          // 内层循环：我回头看前面的每一个桩子 j
          for(int j = 1; j < i; j++) {
                  // 只有比我矮的才能踩
                  if(a[i] > a[j]) {
                          // 核心公式：选个最强的接班
                          dp[i] = max(dp[i], dp[j] + 1);
                  }
          }
  }
  

5. 总结：陷阱扫雷 (15 min)

• 天坑警告：答案是谁？

  • 老师画图：假设高度是 1, 3, 5, 2。
  • dp 值分别是：1, 2, 3, 2。
  • “同学们，最后一个桩子（高度2）的 dp 是 2。但是最长步数明明是 3（1-3-5）！”
  • 结论：最长的一步未必在最后结束！ 阿宝可能在中间某个高桩子上就停下了。

  • 修正代码：

    int ans = 0;
    for(int i=1; i<=n; i++) {
            if(dp[i] > ans) ans = dp[i]; // 打擂台，找最大值
    }
    cout << ans;
    

课后作业：轻功大师

1. 基础题：在纸上模拟数组 [10, 9, 2, 5, 3, 7, 101, 18] 的 LIS 求解过程，写出 dp 数组的每一位。
2. 编程题：洛谷 B3637 最长上升子序列。
3. 变式题（思考）：如果师父说“只能往低处跳”（最长下降子序列），代码哪里要改？
   • 提示：把 > 改成 < 即可。

给教练的建议

• 关于时间复杂度：可以顺带提一句，这个方法是 ，如果桩子有 10 万个会超时。但是在 GESP 考级或小学阶段，掌握 就足够满分了。 的贪心+二分法属于初中/提高组内容，不要在这里讲，会晕。
• 关于初始化：一定要强调 dp[i]=1。很多学生忘了初始化，导致如果前面没有比自己矮的，dp 值就是 0，这显然不对（踩在自己身上也是 1）。