动态规划第一课——聪明的记账本

课程主题：动态规划第一课——聪明的记账本

核心题目：洛谷 P1255 数楼梯

教学目标：

理解由繁入简的拆解思维（把大问题变成小问题）。
学会画表格（状态定义）。
理解为什么是“加法原理”（最后一步的思维）。

第一部分：情景引入（10分钟）

—— 别谈算法，先谈生活

抛出问题：
- “假设咱们教室门口有 10 级台阶。老师腿短，一次只能跨 1 级；xx同学腿长，一次可以跨 1 级，也可以直接跨 2 级。”
- 提问： “如果要走到第 10 级，一共有多少种不同的走法？”
尝试暴力求解（让孩子碰壁）：
- 先算 3 级：让学生手动列举（1-1-1, 1-2, 2-1）。答案是 3 种。
- 再算 4 级：学生开始有点乱了。
- 再算 10 级：告诉他们："如果硬数，我们要数很久，而且容易漏。今天我们要学一种偷懒的方法"。

“你觉得：台阶越多，是不是走法增长得很慢，还是越来越快？” (为后面“指数级增长”埋雷)

第二部分：核心逻辑——“最后一步”思维（25分钟）

—— 这是最关键的“信奥数学思维”训练

逆向思维引导（通过画图）：
- 在黑板画出第 10 级台阶，标上旗帜。
- 提问： “想要站上第 10 级，你最后一次迈步，只能是从哪里迈上来的？”
- 引导答案： “只能是从第 9 级迈 1 步上来，或者从第 8 级迈 2 步上来。”
逻辑推导（加法原理）：
- “好，既然只能从 8 或 9 上来。那么：”
  - “走到 10 级的方法数 = 走到 9 级的方法数 + 走到 8 级的方法数”
- 板书公式（用中文写，别急着写 f(n)）：
  - \(10级的走法 = 9级的走法 + 8级的走法\)
  - 注意：我们不是在数走到 10 级的过程, 而是在数最后一步来自哪里
- 验证： “那 3 级的走法等于什么？”
  - \(2级(2种) + 1级(1种) = 3种\)。对上了！
引出“状态转移”概念：
- 这就叫“状态转移”。你要算大的，只需要知道它前面那两个小的就行了。

第三部分：为什么叫“动态规划”？（15分钟）

—— 引入数组 dp[] 作为“记账本”

故事隐喻：
- “如果我要算第 100 级，我难道要人脑一直记着吗？不行，我们需要一个‘记账本’。”
- 这个记账本在 C++ 里就是数组，我们给它起个高大上的名字叫 dp 数组（或者 f 数组）。
手动填表游戏（必做）：
- 在黑板上画一排格子，标上下标 1 到 10。
- 填初值（Base Case）：
  - 第 1 格填 1（只有 1 种走法）。
  - 第 2 格填 2（1+1 或 2，共 2 种）。
- 填后续：
  - 第 3 格填几？（指着前两格：1+2=3）
  - 第 4 格填几？（指着前两格：2+3=5）
  - 让学生上台接着填，直到填满。
总结规律：
- “看，我们没有递归，没有在那算得晕头转向。我们只是在做简单的加法。这就是动态规划！”
- DP = 递推 + 记忆

第四部分：代码落地（25分钟）

—— 从数学语言翻译成 C++

变量映射：
- 记账本 \(\rightarrow\) int dp[100];
- 台阶数 \(\rightarrow\) 数组下标 i
- 规则 \(\rightarrow\) dp[i] = dp[i-1] + dp[i-2];

编写代码（带学生手写）：

#include <iostream>
using namespace std;

int main() {
        int n;
        cin >> n; // 输入台阶数

        // 1. 定义记账本
        int dp[100];

        // 2. 填写最开始的已知情况 (Base Case)
        // 这一步最重要，初始值错了全盘皆输
        dp[1] = 1;
        dp[2] = 2;

        // 3. 开始循环填表 (从第3级开始，因为1和2都有了)
        for(int i = 3; i <= n; i++) {
                // 今天的核心公式
                dp[i] = dp[i-1] + dp[i-2];
        }

        // 4. 输出我们要的那一页账单
        cout << dp[n] << endl;

        return 0;
}

调试环节：
- 让学生输入 5，看看输出是不是 8。
- 让学生输入 10，看看输出对不对。

第五部分：课后思考与坑（15分钟）

—— 埋下伏笔

讨论1： “如果我们可以一次跨 1 级、2 级、3 级，公式会变成什么样？”
- 答案：\(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)
- 目的：检查他们是否真的理解了“来源”的概念。
讨论2： 如果有的台阶是坏的，不能踩，怎么办？
- 答案：
  - \(dp[i]\)如果是坏的台阶: \(dp[i] = 0\)
  - \(dp[i]\)如果是好的台阶: \(dp[i] = dp[i-1] + dp[i-2]\)
- 目的: 状态还能加条件, dp不止这一种
- 坏台阶不是“算不出来”，而是“根本走不到”。
小坑提示：
- 数组越界问题：如果 \(n=1\) 怎么办？代码里直接访问 dp[2] 会出问题吗？（引导他们思考特判）。

第六部分：总结

“今天我们学的，不是一个题，而是一种思考方式。”

“当你遇到一个很难的问题时，不要慌，问自己三句话：”

最后一步是怎么来的？
大问题能不能拆成小问题？
小问题的答案，我能不能记下来？

“只要这三步走通了，你已经在用动态规划了。”

教练备课 Tips

关于信奥思维： 告诉家长和孩子，这节课学的不仅仅是编程，而是递推思想（Recurrence Relation），这是高中数学数列的内容，现在他们就能掌握，非常了不起。
互动话术： 当孩子写出 dp[i] = dp[i-1] + dp[i-2] 时，狠狠表扬：“你现在写的这个公式，是 800 年前一位叫斐波那契的数学家发现的，你和他一样聪明！”