YMBlog

动态规划第二课——寻宝地图与机器人（小学版）

2026-01-20
114
#动态规划

  • 核心题目：

    1. 数字三角形 (IOI 1994 / 洛谷 P1216) —— 理解“决策”
    2. 不同路径 (LeetCode 62) —— 理解“来源”

  • 课时安排： 90-120 分钟（二维数组通常比一维需要更多消化时间）

  • 教学目标：
    1. 从“一维记账本”升级为“二维藏宝图”（Excel 表格思维）。
    2. 理解 的坐标含义（行和列）。
    3. 学会用双层 for 循环来填表。

第一部分：热身与引入（10分钟）

—— 维度升级：从“跳格子”到“走迷宫”

  1. 复习： 简单回顾爬楼梯。

    • “上节课我们拿的是长条形的记账本（一维数组）。今天，我们要去探险了，地图是长宽都有的（二维数组）。”

  2. 概念引入：

    • 在黑板上画一个 的方格图。
    • 提问： “如果我要描述我在第 3 行第 4 列，怎么表示？”
    • 板书： map[3][4]。强调：前面是楼层（行），后面是房间号（列）。

第二部分：数字三角形——“倒着走的智慧”（35分钟）

—— 对应大纲中的“游戏化教学”

  1. 游戏场景：

    • 画出一个 4 层的数字金字塔（如下）： 

                  7
           3 8
          8 1 0
         2 7 4 4

    • 规则： “探险家在塔顶，每次只能向左下或右下走一格。走到最底层时，把路过的数字加起来，怎么走拿到的分最高？”

  2. 陷阱演示（贪心算法的失效）：

    • 让孩子试着“眼光短浅”地走：
    • 第一步：7 往下看，3 和 8，选 8。
    • 第二步：8 往下看，1 和 0，选 1。
    • 结果：7+8+1+... 可能会走进死胡同。
    • 结论： “只看眼前的一步是不行的，我们要统筹全局。”

  3. Excel 填表法（从下往上）：

    • 魔法时刻： “最好的办法不是从山顶往下看，而是从山底往上推！”
    • 拿出这句口诀：“如果是你站在这一层，你会选楼下左边的路，还是楼下右边的路？”

    • 模拟推导（在黑板上修改数字）：

      • 倒数第一层： 2, 7, 4, 4 （没得选，就是它们自己）。
      • 倒数第二层（关键）：
        • 看那个 8：它下面是 2 和 7。选谁？肯定选 7。所以走到这个 8 的最大得分是 。
        • 看那个 1：它下面是 7 和 4。选谁？肯定选 7。得分 。
        • 看那个 0：它下面是 4 和 4。随便选，得分 。

    • 结果： 此时倒数第二层变成了 15, 8, 4。金字塔变矮了！

    • 继续往上推，直到推到塔尖。塔尖的那个数字就是答案。

  4. 状态转移方程（口语版）：

    • 我也变强了 = 我原本的值 + max(左下角小弟的值, 右下角小弟的值)

第三部分：机器人的地图——“格子的来源”（25分钟）

—— 对应大纲中的“路径问题”

  1. 场景切换：

    • 刚才比的是谁分数高（求 Max），现在我们比谁的路线多（求 Sum）。
    • 画一个 的网格。起点左上角，终点右下角。
    • 规则： 机器人只能向下或向右走。

  2. 关键提问（来源分析）：

    • 指着中间的一个格子 问：
    • “机器人要想踩到这个格子上，它上一脚只能在哪里？”
    • 学生回答： “只能是从上面走下来，或者从左边走过来。”

  3. 推导公式（加法原理）：

    • “没错！所以：”
    • 走到这里的方案数 = 走到上面的方案数 + 走到左边的方案数
    • 代码语言： dp[i][j] = dp[i-1][j] + dp[i][j-1];

  4. 填表实战（Base Case 的重要性）：

    • 第一行： 只能一直向右走，所以第一行所有格子都填 1。
    • 第一列： 只能一直向下走，所以第一列所有格子都填 1。
    • 中间的格子： 疯狂做加法。让学生上台填几个，把网格填满。

第四部分：代码落地与双层循环（30分钟）

—— 突破编程难点

  1. 二维数组的定义： 

    int dp[105][105]; // 开大一点，要在 main 函数外面开（防止爆栈，虽然小学题涉及不到）

  2. 机器人路径的代码框架（C++）：

    • 重点讲解为什么要用两层 for 循环。
    • “外层循环控制行（一层一层填），内层循环控制列（一个格子一个格子填）。”
    #include <iostream>
using namespace std;

int main() {
        int m, n; // m行 n列
        cin >> m >> n;
        int dp[20][20];

        // 1. 初始化边界 (Base Case)
        // 就像盖房子，先把墙角砌好
        for(int i = 0; i < m; i++) dp[i][0] = 1; // 第一列全为1
        for(int j = 0; j < n; j++) dp[0][j] = 1; // 第一行全为1

        // 2. 双层循环填表 (Excel 填数)
        // 从第1行第1列开始（因为第0行和第0列已经填好了）
        for(int i = 1; i < m; i++) {       // 遍历每一行
                for(int j = 1; j < n; j++) {   // 遍历该行的每一列
                        // 核心公式：左边 + 上边
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
        }

        // 3. 输出右下角那个格子的数
        cout << dp[m-1][n-1] << endl; 

        // 4. (可选) 调试神技：打印地图
        // 带着学生把 dp 数组打印出来看一看，非常壮观
        return 0;
}

第五部分：课后总结与教练话术

  1. 总结口诀：

    • “三角形从下往上推，选大的加。”
    • “长方形从左上往右下填，左加上的和。”

  2. 教练避坑指南：

    • 下标从 0 还是从 1 开始？
      • 这是一个大坑。对于数字三角形，建议从 1 开始（dp[1][1]），这样方便理解物理位置。
      • 对于二维数组矩阵，如果习惯从 0 开始，就要注意 越界的问题。
      • 建议统一口径： 初学阶段，为了防止越界，可以教学生多开一行一列，全部从下标 1 开始用。这样 dp[i-1] 永远是安全的（访问的是下标 0）。

配套练习题单

  • 必做： 洛谷 P1216 [USACO1.5] 数字三角形 Number Triangles
  • P1002 [NOIP 2002 普及组] 过河卒
  • 必做： LeetCode 62. 不同路径 (Unique Paths)
  • 选做（进阶）： LeetCode 63. 不同路径 II (Unique Paths II) —— 引入了障碍物，逻辑变成：如果有障碍物，dp值直接填 0，否则公式不变。非常适合检验理解程度。
← 上一篇 C++魔法代码学院：GESP 一级提纲 下一篇 → 动态规划第三课——背包大挑战（0/1背包）（小学版）