🧭 椰程信奥 · CSP复赛专题系列

专题13 · 递推

递推，就是从初始条件出发，沿着递推关系，一步步把答案“推”出来。
它和递归是同一件事的两种写法：递归是逆向拆小，递推是正向填表。
本讲用「昆虫繁殖」「踩方格」两道经典题，把“初始条件 + 递推关系”这两大关键彻底练熟。

昆虫繁殖（双数组递推）踩方格（三状态递推）通用填表三步法

路线图

递推全景（对应视频 12′03″）

🔑 概念与套路　0–3′

递推 = 初始条件 + 递推关系；与递归的区别（正向填表 vs 逆向拆解）；一维 dp 填表三步法。

🐛 例题1 昆虫繁殖　3–7′

成虫产卵管、卵 2 月长成成虫。用 a[i]（成虫）/ b[i]（卵） 两个数组分别递推。

🚶 例题2 踩方格　7–12′

只走北/东/西且不重复。用 u/r/l 三状态 递推，得到 f(n)=2f(n-1)+f(n-2)。

本讲一句话：把"第 i 步的答案"用"前面若干步"表示出来，再给一个起跑的初始值—— 递推就这回事。难点永远只有两个：初始条件写对、递推关系写对。

概念

递推：从“已知”推到“未知”

两大关键

① 初始条件：最小子问题的答案（数组最前面的几格）。
② 递推关系：第 i 步的结果，如何用更早的步骤表示。

递推 vs 递归

递推（循环 / 填表）：从 i=0、1 往大里算，正向，没有栈。
递归（函数自调用）：从大问题往小里拆，逆向，靠栈保存现场。

⚠️ 常见误解：“递推不就是循环吗？”——循环是语法外壳， 递推是思想：用“前面算好的结果”推出“现在的结果”。只要满足“依赖前面、可从小算到大”，就是递推。

✅ 为什么竞赛偏爱递推：递归会爆栈、会重复计算；递推自底向上、空间 O(1)、天然不重复——这正是专题12台阶问题的结论。

3D🎲 递推 = 自底向上堆台阶🖱 拖拽旋转 · 双击复位

为什么用 3D：递推 vs 递归的核心是「有没有回头重算」。立体台阶每一级都由下面两级撑起来，学生能看出递推是只往上、不回头。

动画①

同一个问题，两条路：填表 vs 拆解

目标：算 f(6)（f(1)=f(2)=1，f(i)=f(i-1)+f(i-2)）。左边看递归怎么“往下拆”，右边看递推怎么“往上填”。

✅ 递归是先拆到底、再往回加；递推是先把最小的写好，一路向右填。两者答案相同，但递推没有调用栈、不会爆。

例题1

昆虫繁殖：成虫产卵管，卵 2 月长成成虫

题目规则

每对成虫过 x 个月产 y 对卵；每对卵要过 2 个月长成成虫；成虫不死；第 0 月只有 1 对成虫。问第 z 月末共有成虫多少对。

为什么要两个数组

“本月成虫”和“本月新产卵”是两种不同状态，互相依赖。单数组硬凑会漏掉“卵滞后 2 月”这个延迟。拆成 a[i]（成虫）、b[i]（卵）最清楚。

递推关系：a[i] = a[i-1] + b[i-2]　（上月成虫 + 2月前产的卵长成的成虫）

递推关系：b[i] = a[i-x] × y　（i < x 时为 0；x 个月前的成虫每对产 y 对卵）

初始条件：a[0] = 1　（第一个月只有一对成虫）

⚠️ 最容易写错的两点：把 b[i-2] 写成 b[i-1]（忘了卵要 2 个月）；把 b[i] = a[i-x] 写成 a[i]（忘了要乘 y，或忘了是“x 个月前”而不是“上月”）。

动画②

昆虫繁殖：逐月推演表

从月 0 开始，一月至一月地推。每推一月，先猜 a[i] 是多少，再点「下一步」对照公式。

样例

动画③

生命周期可视化：为什么是 b[i-2]？

上层是“成虫数”，下层是“卵数”。看一对卵从产出到长成成虫，要跨过 2 个月才汇入成虫。

✅ 第 i-2 月产的卵 b[i-2]，到第 i 月才变成成虫 —— 所以 a[i] 加的是 b[i-2] 而不是 b[i-1]。这个“延迟 2 个月”是本题的灵魂。

例题1

昆虫繁殖 · 完整代码

// a[i] 第 i 月成虫，b[i] 第 i 月新增卵
long long a[Z+5], b[Z+5];
a[0] = 1;                      // 初始：1 对成虫
for (long long i = 1; i <= z; i++){
  long long egg = (i-2 >= 0) ? b[i-2] : 0;
  a[i] = a[i-1] + egg;         // 本月成虫
  b[i] = (i >= x) ? a[i-x] * y : 0; // 本月新卵
}
cout << a[z];

坑① 漏掉 i-2 越界保护：i=1 时 b[i-2]=b[-1]，数组越界 → 结果随机。用 (i-2>=0)?b[i-2]:0 守住边界。

坑② b[i] 写成 a[i]*y：那是“本月成虫”产的卵，但题目说“过 x 个月才产”，应是 a[i-x] 那批成虫产的。

坑③ 用 int：z 到 50、y 到 20，a[i] 指数级增长，必须用 long long。

✅ 复杂度：只循环 0..z 一次，O(z) 时间、O(z) 空间，轻松过。

例题2

踩方格：只走北/东/西，格子不重复踩

题目规则

无限方格，从原点出发；每步只能北 / 东 / 西（不能向南）；走过的格塌陷，不能重复踩。问走 n 步共有多少种走法。

为什么能递推

只看“最后一步朝哪个方向”，就能把总走法拆成 向北 / 向东 / 向西 三类，互不重叠又穷尽。

设 u[i]、r[i]、l[i] 为第 i 步向北 / 向东 / 向西的走法数，f(i) = u[i] + r[i] + l[i]

u[i] = u[i-1] + r[i-1] + l[i-1]　；　r[i] = u[i-1] + r[i-1]　；　l[i] = u[i-1] + l[i-1]

初始 u[1] = r[1] = l[1] = 1　（已知 f(1)=3，f(2)=7，f(3)=17，f(4)=41）

⚠️ “向东不能从西来”：若第 i 步向东，第 i-1 步不能是向西（否则会立刻踩回刚离开的格）。这正是 r[i] 比 u[i] “少一项”的原因。

动画④

踩方格：u / r / l 三列递推

一行行往下填，每填一行，先猜 u[i]、r[i]、l[i] 各是多少，再点「填下一行」对照公式。

步数 n

动画⑤

踩方格：把所有合法路径画出来数

用 DFS 枚举所有不重复的合法路径，一条条看。n=3 时一共 17 条 —— 与递推 f(3)=17 完全一致。

步数 n

例题2

踩方格 · 完整代码

long long u[N+2], r[N+2], l[N+2];
u[1] = r[1] = l[1] = 1;        // 初始
for (long long i = 2; i <= n; i++){
  u[i] = u[i-1] + r[i-1] + l[i-1];
  r[i] = u[i-1] + r[i-1];      // 不能从西来
  l[i] = u[i-1] + l[i-1];      // 不能从东来
}
cout << u[n] + r[n] + l[n];

// 进一步化简为单数组：
// f[1]=3, f[2]=7, f[i]=2*f[i-1]+f[i-2]

坑① 把 r[i] 写成 u[i-1]+r[i-1]+l[i-1]：那会允许“东←西”的回头路径，而题目不能重复踩格，所以 r[i] 少一项 l[i-1]。

坑② 初始写错：第 1 步三个方向各 1 种，必须是 u[1]=r[1]=l[1]=1，而不是 u[0]=...。

✅ 化简：f(i)=u+r+l = (u+r+l) + (u+r) + (u+l) = 2f(i-1) + (u[i-1]+r[i-1]+l[i-1]) = 2f(i-1)+f(i-2)。单数组也能写，但三状态更不容易错。

动画⑥

递推填表通用模板：一维 dp 三步法

例：g[i] = g[i-1] + i（前缀和 / 三角数），g[0]=0。从左到右填，体会“三步法”。

① 初始条件

把最小子问题的答案先写好（数组最前面几格）。这是递推的“起跑线”。

② 递推关系

第 i 格只依赖它左边的若干格。循环从 i 小往大填，绝不引用未算的格。

③ 取答案

目标值就是某一格（通常是最后一格）的内容。输出它。

选型

什么时候用递推，什么时候用递归？

维度	递归（逆向拆解）	递推（正向填表）
思考方向	大问题 → 小问题	小问题 → 大问题
实现	函数自己调自己	一层循环填数组
栈 / 空间	深度 = 递归层数，深了会爆栈	O(1) 额外空间
重复计算	易重复，需记忆化	天然不重复
适用	树形 / 分叉结构（放苹果、回溯）	链式 / 线性（本题两例）

✅ 判据：如果“第 i 步只依赖前面有限的几步”，就果断写递推；如果“大问题能自然分成几个同类小问题”，才用递归 + 记忆化。本题昆虫与踩方格都是典型线性递推。

诊断

递推易错辨析

① 昆虫繁殖里，“卵 2 个月长成成虫”应该体现在哪？

② 踩方格中，为什么 r[i]（向东）比 u[i]（向北）少一个来源？

③ 递推写完后，最先要核对的是什么？

拿分

一道题 100 分是分档给的——不会正解也要先拿保底

复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分，加起来往往就是一等奖和二等奖的分界。

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例，再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

考场纪律：每档设时间上限，到点还没调通就 立刻提交当前版本，保住已有分数，再往上冲。最常见的翻车是"正解写了 50 分钟没过，连暴力分都没交上去"。

拿分

本讲 2 道题，各自的四档怎么走

昆虫繁殖 · INSECT

第1档 · 2 分钟
z ≤ x（还没到成熟期）→ 只有最初的 1 对

第2档 · 8 分钟
按月模拟每一对虫的年龄，z ≤ 30 稳过

第3档 · 10 分钟
只做「没有成熟期」（x == 1）的简化版

第4档 · 15 分钟
双数组（成虫 / 幼虫）按月递推，先手推两个月再写代码

踩方格 · SQUARE

第1档 · 2 分钟
n == 0 → 1；n == 1 → 3

第2档 · 8 分钟
DFS 枚举所有走法并判重，n ≤ 10 稳过

第3档 · 10 分钟
只做「只往北和东」的两方向版本，先拿部分分

第4档 · 15 分钟
三状态递推：f[i] = 2·f[i−1] + g[i−1]，g[i] = f[i−1] + g[i−1]

50 分钟时间盒（一题的节奏）：
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查 freopen 与文件名。

课堂上别让学生"从头想正解"。先要求每个人 15 分钟内交出第 1、2 档，再放开冲正解。这个顺序一换，平均分通常能涨一大截——因为它杜绝了"想了 40 分钟，交上去 0 分"。

当堂检测

椰程信奥当堂测评

① 昆虫繁殖 x=1,y=2,z=8，第 8 月末成虫总数是？

② 踩方格 n=4 时，走法总数是？

③ 递推相比递归最大的工程优势是？

椰程锦囊 · 递推三步自检
① 初始条件写对了吗？（最小子问题）
② 递推关系引用的下标越界了吗？滞后几步搞清楚了吗？
③ 答案取的是哪一格？用样例手算一遍再交。💡

专题13 · 递推

递推全景（对应视频 12′03″）

🔑 概念与套路 0–3′

🐛 例题1 昆虫繁殖 3–7′

🚶 例题2 踩方格 7–12′

递推：从“已知”推到“未知”

两大关键

递推 vs 递归

同一个问题，两条路：填表 vs 拆解

昆虫繁殖：成虫产卵管，卵 2 月长成成虫

题目规则

为什么要两个数组

昆虫繁殖：逐月推演表

生命周期可视化：为什么是 b[i-2]？

昆虫繁殖 · 完整代码

踩方格：只走北/东/西，格子不重复踩

题目规则

为什么能递推

踩方格：u / r / l 三列递推

踩方格：把所有合法路径画出来数

踩方格 · 完整代码

递推填表通用模板：一维 dp 三步法

① 初始条件

② 递推关系

③ 取答案

什么时候用递推，什么时候用递归？

递推易错辨析

一道题 100 分是分档给的——不会正解也要先拿保底

① 特判档：先别想算法，看数据范围表

② 暴力档：按题意最直白地写一遍

③ 特殊性质档：题目里那句「若……」

④ 正解档：思路定了，就赢了八成

本讲 2 道题，各自的四档怎么走

昆虫繁殖 · INSECT

踩方格 · SQUARE

椰程信奥当堂测评

目录

🔑 概念与套路　0–3′

🐛 例题1 昆虫繁殖　3–7′

🚶 例题2 踩方格　7–12′