YMBlog

从递归到动态规划（卡特兰数）

2026-01-23
399
#数学 #动态规划 #卡特兰数

课程概况

  • 课时时长：90 ~ 100 分钟
  • 核心题目：洛谷 P1044 [NOIP 2003 普及组] 栈
  • 教学目标：
    1. 复习栈：巩固“后进先出”的物理特性。
    2. 掌握搜索：学会用 DFS 模拟“进栈/出栈”的决策过程。
    3. 算法进阶：理解从“暴力搜索”到“二维 DP”的思维跃迁（解决超时问题）。
    4. 数学素养：认识“卡特兰数”数列及其应用场景。

教学流程时间表

环节 时长 内容 关键活动/隐喻
引入 15 min 题目情境与手动模拟 “死胡同火车站”
核心 I 25 min 递归搜索 (DFS) “决策树的分叉口”
进阶 35 min 二维动态规划 (DP) “网格地图寻宝”
归纳 15 min 卡特兰数与数学规律 “神奇的数列”
总结 10 min 练习与作业布置 巩固与拓展

详细教学内容拆解

第一部分：情境引入 —— 死胡同里的火车 (15 min)

  1. 回顾栈 (Stack)

    • 道具：粉笔盒（只能从上面拿）、死胡同停车位。
    • 概念：Push (进栈/停车)、Pop (出栈/开车)。
    • 规则：车必须按 1, 2, 3... 的顺序进站，但出站时机可以随意。

  2. 手动模拟挑战 (\(N=3\))

    • 让学生在纸上穷举 \(N=3\) 的所有出站序列。
    • 引导提问：“能不能还没进站就出站？”（不能，因为栈空了）。“能不能车都进完了还赖着不走？”（题目要求全部出站）。
    • 答案确认： \(1, 2, 5\) 种。

第二部分：教电脑做选择 —— 递归搜索 DFS (25 min)

  1. 定义“现在的状态”

    • 我们要告诉计算机，现在局面如何，只需要两个数字：
      • wait：还在排队、没进站的火车数量。
      • in_stack：已经停在栈里的火车数量。

  2. 每一步的两个选择

    • 选择 A (Push)：只要 wait > 0，就可以让一辆车进站。

      • 后果：wait - 1, in_stack + 1

    • 选择 B (Pop)：只要 in_stack > 0，就可以让一辆车出站。

      • 后果：wait 不变, in_stack - 1

  3. 代码实现 (DFS)

    • 板书代码，重点讲解递归边界与回溯逻辑。
    // 基础递归版（适合初学理解逻辑）
void dfs(int wait, int in_stack) {
        // 边界：外面没车了，栈里也没车了 -> 找到一种方案
        if (wait == 0 && in_stack == 0) {
                ans++;
                return;
        }
        // 两种选择
        if (wait > 0) dfs(wait - 1, in_stack + 1); // 进
        if (in_stack > 0) dfs(wait, in_stack - 1); // 出
}

第三部分：从超时到秒杀 —— 二维 DP 的诞生 (35 min) (重难点)

  1. 发现危机： \(N=18\) 的灾难

    • 现场演示：输入 18，程序“卡死”。
    • 原因：电脑太笨，反复计算相同的情况（画图展示重复子树）。

  2. 思维转换：画地图 (Grid Path)

    • 在黑板上画一个 \(N \times N\) 的网格。
    • X 轴：代表“已经进栈的数量” (\(i\))。
    • Y 轴：代表“已经出栈的数量” (\(j\))。
    • 起点：(0, 0)。
    • 终点：(n, n)。
    • 禁区：画出对角线。因为 出栈数不能大于进栈数 (\(j \le i\))，所以对角线左上方的格子全是“禁区”。

  3. 动态规划 (DP) —— “刷表法”

    • 状态定义：f[i][j] 表示“进 \(i\) 个、出 \(j\) 个”时，一共有多少种走法。
    • 逻辑：
      • 如果你站在 \((i, j)\)，你能去哪？
      • 向右走 (进栈)：去 \((i+1, j)\)。把现在的方案数带过去。
      • 向上走 (出栈)：去 \((i, j+1)\)。把现在的方案数带过去。

  4. 最终代码 (满分写法)

    #include <iostream>
using namespace std;

long long f[20][20]; // 记得用 long long，防止炸 int

int main() {
        int n;
        cin >> n;

        f[0][0] = 1; // 起点只有 1 种情况

        for (int i = 0; i <= n; i++) {       // 进栈数
                for (int j = 0; j <= n; j++) {   // 出栈数

                        // 核心规则：出栈数 j 不能超过进栈数 i
                        if (j > i) continue; 

                        // 1. 尝试进栈（向右走）
                        if (i < n) {
                                f[i + 1][j] += f[i][j];
                        }

                        // 2. 尝试出栈（向上走）
                        if (i > j) { // 只有栈里有车才能出
                                f[i][j + 1] += f[i][j];
                        }
                }
        }

        cout << f[n][n] << endl; // 终点
        return 0;
}

第四部分：数学家的捷径 —— 一维递推与卡特兰数 (20 min)

1. 思考：能不能更省纸？

  • 回顾：刚才我们画了一个二维表格 f[i][j]，填满了半张纸。
  • 提问：如果 ，表格要画 个格子，太大了！数学家发现，其实只需要一行格子就能算出来。
  • 新思路：“大队长”分身法
    • 假设我们有 辆火车要处理。
    • 死盯着 1号火车（大队长）。它第一个进栈，但它什么时候出栈呢？它可能把大家分成两拨：
    • 第一拨：在 1 号车出栈之前，有一堆车进来了又出去了（它们被 1 号车压在下面）。假设有 辆。
    • 第二拨：在 1 号车出栈之后，剩下的车才开始进进出出。剩下 辆（减去的 1 是大队长自己）。
    • 核心逻辑： \(\text{总方案} = \text{第一拨的方案} \times \text{第二拨的方案}\)

2. 手动模拟验证 (\(N=3\))

我们要算 dp[3]（3辆车），大队长是 1 号。

  • 情况 A：1号立刻出栈

    • 在它之前（压在下面）：0 辆。方案数 dp[0]。
    • 在它之后：剩下 2 辆。方案数 dp[2]。
    • 计算：\(1 \times 2 = 2\) 种。

  • 情况 B：1号中间出栈

    • 在它之前：1 辆（比如2号进出）。方案数 dp[1]。
    • 在它之后：剩下 1 辆（比如3号进出）。方案数 dp[1]。
    • 计算：\(1 \times 1 = 1\) 种。

  • 情况 C：1号最后出栈

    • 在它之前：2 辆（2,3号都弄完了）。方案数 dp[2]。
    • 在它之后：0 辆。方案数 dp[0]。
    • 计算：\(2 \times 1 = 2\) 种。

  • 总数：\(2 + 1 + 2 = 5\) 种。对上了！

3. 代码实现：卡特兰递推公式

  • 老师讲解代码中的 vector 用法，或者将其改为普通数组 long long dp[20] 方便学生理解。

    #include <iostream>
#include <vector> // 引入 vector 头文件
using namespace std;

int main() {
        int n;
        cin >> n;

        // dp[i] 表示 i 辆火车的出栈方案数
        // vector<long long> 是一个动态数组，初始化大小为 n+1，值全为 0
        vector<long long> dp(n + 1, 0);

        // 初始化：0 辆车只有 1 种方案（什么都不做）
        dp[0] = 1;

        // i 表示当前我们要计算多少辆车的方案（从 1 到 n）
        for (int i = 1; i <= n; i++) {
                // j 表示在 1 号车出栈之前，有多少辆车（从 0 到 i-1）
                for (int j = 0; j < i; j++) {
                        // 公式：dp[总数] += dp[左边] * dp[右边]
                        // j 是压在下面的车， (i - 1 - j) 是剩下的车
                        dp[i] += dp[j] * dp[i - 1 - j];
                }
        }

        cout << dp[n] << endl;
        return 0;
}
    • 代码解读：
      • dp[i - 1 - j] 里的 -1 很重要，因为那是 1 号车自己，它不属于左边也不属于右边，它只是个分界线。

4. 知识拓展：什么是卡特兰数？

  • 定义：刚才算出来的这个数列 1, 1, 2, 5, 14, 42, 132... 就叫卡特兰数 (Catalan Number)。它是组合数学界的“变形金刚”。

  • 通项公式（仅了解）：虽然我们用递推法（加法和乘法）算出来了，但数学家其实有一个直接计算的公式：\(C_n = \frac{C_{2n}^n}{n+1}\)

  • 三大经典应用场景（图示展示，加深记忆）：

    1. 进出栈问题：刚才讲的火车调度。

    2. 括号匹配：有 个左括号 ( 和 个右括号 )，要把它们合法地配对。比如 (()) 是对的，))(( 是错的。这也等于卡特兰数！

      • 类比：左括号是进栈，右括号是出栈。

    3. 二叉树计数：有 个节点，能摆出多少种不同形状的二叉树？

      • 类比：根节点是 1 号车，左子树是“压在下面的车”，右子树是“剩下的车”。

    4. 多边形切分：把一个凸多边形切成三角形，有多少种切法？

5. 课堂小结

  • 如果你记不住这个复杂的 dp[j] * dp[i-1-j] 公式，没关系！用前面的二维表格法（网格图）一样能拿满分，而且更不容易写错。
  • 但是，理解“把大问题拆成左边一堆、右边一堆”的思想，对以后学更难的算法（比如树形DP）非常有帮助。

课堂练习与作业

课堂练习 (随堂做)

1. 画图验证：请画出 \(N=4\) 时的 DP 表格（只填前几行），手动验证 \(N=3\) 时是否等于 5。 2. 代码找茬：老师给出一段把 long long 写成 int 的代码，或者 if (j > i) 写反的代码，让学生找出 Bug。

课后作业 (LuoGu)

1. 必做：[P1044] 栈 —— 提交 DP 代码并通过。 2. 思考：如果有 10 元和 5 元的人排队买票（票价 5 元），售票员没零钱，有多少种排队方法？（提示：这和进出栈问题是一样的，5 元是进栈，10 元是出栈）。

给老师的“避坑”指南

  1. 关于 long long：

    • \(N=18\) 时，结果是 477,638,700。虽然 int (约 21 亿) 能存下，但卡特兰数增长极快，养成开 long long 的习惯是很好的竞赛素养。

  2. 关于 DP 的两种写法：

    • 填表法 (f[i][j] = f[i-1][j] + f[i][j-1])：也就是“我从哪里来”。
    • 刷表法 (f[i+1][j] += f[i][j])：也就是“我要去哪里”。
    • 建议：对于小学生，刷表法（代码中的写法）更符合直觉，就像玩大富翁游戏一样“走到一格，就把机会分给下一格”。

  3. 不要讲排列组合公式：

    • 除非学生数学极好，否则不要讲 \(\frac{C_{2n}^n}{n+1}\)，这涉及阶乘和组合数运算，容易让编程课变成奥数课，导致学生掉线。重点放在 算法思维 (递归 -> DP) 上。
← 上一篇 动态规划小学版提纲