Appearance
第6章 递推算法
🎯 本章学习目标
通过本章的学习，你将能够：
- 理解递推思想：掌握递推的核心——从已知出发，逐步推算未知
- 掌握递推三要素：能找出初始条件、递推关系式和终止条件
- 实现一维递推：能用变量迭代或数组实现斐波那契等一维递推
- 解决经典问题：掌握爬楼梯、汉诺塔、兔子繁殖等经典递推模型
- 实现二维递推：能用二维数组解决路径计数、数字三角形等问题
- 处理边界条件：正确处理首行首列、障碍格等边界情况
- 区分递推与递归：理解二者的区别和联系
- 防止数据溢出：知道什么时候该用 long long 类型
- 选择实现方式：根据问题特点选择变量迭代法或数组存储法
- 编写递推代码：独立完成过河卒、数字三角形等编程题
🗺️ 本章知识图谱
递推算法
├── 基础概念
│ ├── 递推的核心思想
│ ├── 递推三要素
│ │ ├── 初始条件（起点）
│ │ ├── 递推关系式（怎么推）
│ │ └── 终止条件（到哪停）
│ └── 递推 vs 递归
├── 一维递推
│ ├── 斐波那契数列
│ ├── 爬楼梯问题
│ ├── 汉诺塔问题
│ ├── 兔子繁殖问题
│ └── 铺砖问题
├── 二维递推
│ ├── 路径计数（无障碍）
│ ├── 过河卒（含障碍）
│ ├── 数字三角形（最大路径和）
│ └── 杨辉三角
├── 实现方式
│ ├── 变量迭代法（O(1)空间）
│ └── 数组存储法（O(n)/O(n²)空间）
├── 边界处理
│ ├── 初始条件（多个初值）
│ ├── 首行/首列特殊处理
│ ├── 障碍格（dp=0）
│ └── 数组越界防范
└── 注意事项
├── 数据类型溢出（用long long）
├── 下标一致性（0开始vs1开始）
└── 递推方向（顺序不能错）一、什么是递推？
递推（Recurrence）的核心思想：从已知的初始条件出发，通过递推关系式逐步演算，最终推导出目标结果。
通俗地说，就是"知道前几个，算下一个"。就像多米诺骨牌——推倒第一块（初始条件），后面的每一块都被前一块推倒（递推关系），直到最后一块倒下（终止条件）。
💡 生活中的递推：你第一天背了10个单词，以后每天比前一天多背2个，第n天背多少个？答案：10 + 2×(n-1)。这就是最简单的递推——首项已知，公差确定，逐项推算。
二、递推三要素
做任何递推题，先问自己三个问题：
| 要素 | 含义 | 关键问题 |
|---|---|---|
| ① 初始条件 | 递推的起点，已知的最小情况的值 | "最早能确定的是哪些值？" |
| ② 递推关系式 | 如何从前面的状态推出当前状态 | "f(n) 与 f(n-1)、f(n-2) 等是什么关系？" |
| ③ 终止条件 | 递推到何时停止 | "算到哪个值就得到答案了？" |
易错点 ⚠️： 三要素缺一不可！初始条件设错，后面全盘皆错；递推关系式推导有误，结果必然不对；终止条件搞错，可能多算少算或死循环。
递推关系式的推导方法
递推关系式不会凭空出现，从特例入手找规律是最实用的推导方法：
- 手动模拟：先算出 n=1, 2, 3, 4 时的结果
- 观察规律：对比相邻项，猜测 f(n) 与前面哪些项有关
- 验证猜想：用更多特例验证猜测是否成立
- 写出公式：确认规律后写出递推关系式
🔥 高频考点：考试中递推题往往不直接给出公式，需要你自己从问题描述中推导。务必先手动算前几项找规律，不要急着写代码！
三、递推与递归的区别
递推和递归都涉及"自己与自己的关系"，但实现思路截然不同：
| 对比维度 | 递推（循环实现） | 递归（函数自调用） |
|---|---|---|
| 思考方向 | 自底向上（bottom-up），从已知推未知 | 自顶向下（top-down），把大问题拆成小问题 |
| 实现方式 | 循环结构，逐步迭代 | 函数调用自身 |
| 时间效率 | 无函数调用开销，更快 | 有调用开销，可能大量重复计算 |
| 空间效率 | 可做到 O(1) | 需要栈空间，通常 O(n) |
| 栈溢出风险 | 无 | 有（层数过深时） |
| 代码可读性 | 直观，按部就班 | 简洁但对初学者不直观 |
cpp
#include <iostream>
using namespace std;
// 递推写法：从小到大，逐步迭代
long long fib_iter(int n) {
if (n <= 2) return 1;
long long a = 1, b = 1; // a=F(n-2), b=F(n-1)
for (int i = 3; i <= n; i++) {
long long c = a + b; // F(n) = F(n-2) + F(n-1)
a = b;
b = c;
}
return b;
}
// 递归写法：自顶向下，层层分解
long long fib_recur(int n) {
if (n <= 2) return 1; // 递归终止条件
return fib_recur(n - 1) + fib_recur(n - 2);
}
int main() {
cout << fib_iter(40) << endl; // 瞬间完成
// cout << fib_recur(40) << endl; // 明显变慢，大量重复计算
return 0;
}易错点 ⚠️： 递归求斐波那契存在指数级重复计算——fib(3) 被算2次，fib(2) 被算3次，n=40 时递归已明显卡顿，而递推瞬间完成。考试中只要求结果时，优先用递推。
四、经典一维递推问题
4.1 斐波那契数列（Fibonacci）
问题描述： 斐波那契数列定义如下：
- F(1) = 1, F(2) = 1
- F(n) = F(n-1) + F(n-2)（n ≥ 3）
前几项为：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
递推三要素：
- 初始条件：F(1) = 1, F(2) = 1
- 递推关系式：F(n) = F(n-1) + F(n-2)
- 终止条件：计算到 F(n) 时停止
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long f[105];
f[1] = 1; // 初始条件
f[2] = 1; // 初始条件
for (int i = 3; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2]; // 递推关系式
}
cout << f[n] << endl; // 终止条件：输出第n项
return 0;
}
// 输入: 10
// 输出: 55🔥 高频考点：斐波那契数列增长极快！F(46) ≈ 18亿，F(47) 就超过
int范围（约21亿）。考试中 n 稍大就要用long long。
4.2 爬楼梯问题
问题描述： 一段楼梯有 n 级台阶，每次可以走1级或2级，走到第 n 级共有多少种不同的走法？
推导过程（从特例入手）：
| n | 走法枚举 | 走法数 f(n) |
|---|---|---|
| 1 | 走1级 | 1 |
| 2 | 1+1，直接走2级 | 2 |
| 3 | 1+1+1，1+2，2+1 | 3 |
| 4 | 1+1+1+1，1+1+2，1+2+1，2+1+1，2+2 | 5 |
观察：f(3)=3 = f(2)+f(1)，f(4)=5 = f(3)+f(2)。
规律： 到达第 n 级的最后一步只有两种可能：
- 从第 n-1 级走 1级 上来 → f(n-1) 种
- 从第 n-2 级走 2级 上来 → f(n-2) 种
因此 f(n) = f(n-1) + f(n-2)。
易错点 ⚠️： 公式和斐波那契一样，但初始条件不同！f(2) = 2 而不是 1。这是最容易照搬公式出错的地方——务必根据题意重新确定初始条件。
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long f[105];
f[1] = 1; // 到第1级：1种走法
f[2] = 2; // 到第2级：2种走法（1+1 或 2）
for (int i = 3; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
cout << f[n] << endl;
return 0;
}
// 输入: 5
// 输出: 84.3 汉诺塔递推（移动次数）
问题描述： 有三根柱子 A、B、C，A 柱上套着 n 个从小到大的圆盘。每次只能移动一个圆盘，且大盘不能放在小盘上面。求把 n 个圆盘从 A 柱移到 C 柱最少需要移动多少次？
推导过程（从特例入手）：
| n | 移动策略 | 次数 H(n) |
|---|---|---|
| 1 | 直接把圆盘从 A 移到 C | 1 |
| 2 | 小盘A→B，大盘A→C，小盘B→C | 3 |
| 3 | 先把2个盘A→B（3次），最大盘A→C（1次），再把2个盘B→C（3次） | 7 |
规律： 要移动 n 个圆盘：
- 把上面 n-1 个圆盘从 A 移到 B（借助 C）→ H(n-1) 次
- 把最大的圆盘从 A 移到 C → 1 次
- 把 n-1 个圆盘从 B 移到 C（借助 A）→ H(n-1) 次
因此 H(n) = 2 × H(n-1) + 1，H(1) = 1。
进一步可得通项公式：H(n) = 2ⁿ - 1。
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long h[105];
h[1] = 1; // 1个圆盘：移动1次
for (int i = 2; i <= n; i++) {
h[i] = 2 * h[i - 1] + 1; // 递推：H(n) = 2*H(n-1) + 1
}
cout << h[n] << endl;
return 0;
}
// 输入: 4
// 输出: 15
// 验证: H(4) = 2*7 + 1 = 15 = 2^4 - 1🔥 高频考点：汉诺塔在四级中常考移动次数的递推计算（而非模拟移动过程）。公式 H(n) = 2ⁿ - 1 必须牢记，考试可直接用于验证答案。
4.4 铺砖问题
问题描述： 用 1×2 的多米诺骨牌铺满一个 2×n 的矩形，有多少种不同的铺法？
推导过程（从特例入手）：
| n | 铺法示意 | 铺法数 f(n) |
|---|---|---|
| 1 | 竖放1块 | 1 |
| 2 | 两块竖放 或 两块横放 | 2 |
| 3 | 竖放+2×2铺法 或 横放+2×1铺法 | 3 |
规律： 考虑最右侧的铺法：
- 竖放1块：占 2×1 空间，剩下 2×(n-1) → f(n-1) 种
- 横放2块：上下各横放一块，占 2×2 空间，剩下 2×(n-2) → f(n-2) 种
因此 f(n) = f(n-1) + f(n-2)，f(1) = 1, f(2) = 2。
💡 这个公式和爬楼梯完全一样，但问题场景不同。关键是学会从边界情况切入，分析"最后一步"的两种可能。
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long f[105];
f[1] = 1; // 2×1：1种（竖放）
f[2] = 2; // 2×2：2种（两竖或两横）
for (int i = 3; i <= n; i++) {
// 最后竖放1块 + 最后横放2块
f[i] = f[i - 1] + f[i - 2];
}
cout << f[n] << endl;
return 0;
}
// 输入: 5
// 输出: 84.5 兔子繁殖问题
问题描述： 有一对刚出生的小兔子，小兔子出生后第3个月开始每个月生一对小兔子。假如兔子不死，问第 n 个月共有多少对兔子？
推导过程（逐月模拟）：
| 月份 n | 幼兔（当月出生） | 成兔（可繁殖） | 总数 f(n) |
|---|---|---|---|
| 1 | 1对 | 0对 | 1 |
| 2 | 0对 | 1对 | 1 |
| 3 | 1对（成兔生的） | 1对 | 2 |
| 4 | 1对 | 2对 | 3 |
| 5 | 2对 | 3对 | 5 |
规律分析：
- 第 n 个月的成兔数 = 第 n-1 个月的总数（所有兔子都会长大）
- 第 n 个月新生的幼兔数 = f(n-2)（成兔是两个月前出生的）
- 因此：f(n) = 上月总数 f(n-1) + 新生幼兔 f(n-2)
即 f(n) = f(n-1) + f(n-2)，f(1) = 1, f(2) = 1。
💡 这就是斐波那契数列的起源问题——斐波那契在《算盘全书》中以兔子繁殖为例子引入了这个数列。虽然公式相同，但推导过程值得反复体会。
cpp
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long f[105];
f[1] = 1; // 第1月：1对幼兔
f[2] = 1; // 第2月：1对成兔（还不能生）
for (int i = 3; i <= n; i++) {
// 当月总数 = 上月总数 + 当月新生（两月前的兔子数 = 可繁殖的成兔数）
// 当月新生幼兔 = 可繁殖成兔数 = 两个月前的兔子总数
//（第i-2月的所有兔子到第i月都长大成熟了）
f[i] = f[i - 1] + f[i - 2];
}
cout << f[n] << endl;
return 0;
}
// 输入: 10
// 输出: 55五、经典二维递推问题
当问题涉及二维网格或表格时，递推关系从"依赖前面的项"变为"依赖上方和左方的格"，这就是二维递推。
5.1 过河卒问题
问题描述： 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒只能向下或向右走。棋盘上有一个马（位于 (mx, my)），马的控制点（马走"日"字能到达的格子）不能走。求从起点 (0,0) 到终点 (n,m) 的路径条数。
推导过程：
设 dp[i][j] 表示从起点 (0,0) 走到 (i,j) 的路径条数。
- 初始条件：dp[0][0] = 1（起点只有1种方式）；第一行和第一列的格子都只有1种走法（一路走到底），但若遇到马的控制点则路径数为0
- 递推关系式：dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上面或左边走来）
- 终止条件：计算到 dp[n][m] 时停止
马的控制点有8个方向：(±1,±2) 和 (±2,±1)。
cpp
#include <iostream>
using namespace std;
int main() {
int n, m, mx, my;
cin >> n >> m >> mx >> my; // 终点(n,m)，马的位置(mx,my)
long long dp[25][25] = {0};
bool blocked[25][25] = {false};
// 标记马的位置和8个控制点为障碍
int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
for (int k = 0; k < 9; k++) {
int nx = mx + dx[k];
int ny = my + dy[k];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
blocked[nx][ny] = true;
}
}
// 递推
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (blocked[i][j]) {
dp[i][j] = 0; // 障碍格：路径数为0
continue;
}
if (i == 0 && j == 0) {
dp[0][0] = 1; // 起点
} else if (i == 0) {
dp[i][j] = dp[i][j - 1]; // 第一行：只能从左边来
} else if (j == 0) {
dp[i][j] = dp[i - 1][j]; // 第一列：只能从上面来
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 上面+左边
}
}
}
cout << dp[n][m] << endl;
return 0;
}
// 输入: 6 6 3 2
// 输出: 17🔥 高频考点：过河卒是二维递推的经典考题，几乎每年都会以不同形式出现。关键要点：① 障碍格令 dp[i][j]=0；② 边界（第一行/列）的路径数需单独递推，不能直接填1；③ 使用
long long防止路径数溢出。
5.2 数字三角形
问题描述： 给定一个数字三角形，从顶部出发，每次可以走到左下方或右下方的相邻数字，求从顶到底的路径上数字之和的最大值。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5推导过程：
设 dp[i][j] 表示从顶部走到第 i 行第 j 列时的最大路径和。
- 初始条件：dp[0][0] = a[0][0]（顶点数字）
- 递推关系式：
- 左端（j=0）：只能从正上方走来 → dp[i][0] = dp[i-1][0] + a[i][0]
- 右端（j=i）：只能从左上方走来 → dp[i][i] = dp[i-1][i-1] + a[i][i]
- 中间：取左上方和正上方的较大值 → dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
- 终止条件：最后一行的最大值 max(dp[n-1][j])
cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[105][105] = {0};
long long dp[105][105] = {0};
// 读入数字三角形
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cin >> a[i][j];
}
}
dp[0][0] = a[0][0]; // 初始条件：顶点
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
// 左端：只能从正上方来
dp[i][j] = dp[i - 1][j] + a[i][j];
} else if (j == i) {
// 右端：只能从左上方来
dp[i][j] = dp[i - 1][j - 1] + a[i][j];
} else {
// 中间：取上方两个方向的较大值
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
}
}
}
// 答案为最后一行的最大值
long long ans = 0;
for (int j = 0; j < n; j++) {
ans = max(ans, dp[n - 1][j]);
}
cout << ans << endl;
return 0;
}
// 输入:
// 5
// 7
// 3 8
// 8 1 0
// 2 7 4 4
// 4 5 2 6 5
// 输出: 30
// 最优路径: 7→3→8→7→5 = 30易错点 ⚠️： 数字三角形的边界处理是关键——左端和右端的递推来源不同，不能统一用
max。考试中如果忽略边界，会导致数组下标越界或取到错误的0值。
六、递推的边界处理
边界处理是递推题中最容易丢分的环节，以下是常见边界问题及应对策略：
| 边界问题 | 典型场景 | 处理方法 |
|---|---|---|
| 初始条件多解 | 斐波那契需 f(1) 和 f(2) 两个初值 | 逐个列出所有初始条件，不要遗漏 |
| 首行/首列特殊 | 过河卒第一行只能从左来 | 单独循环初始化，或在主循环中判断 |
| 数组越界 | dp[i][j] 访问 dp[i-1][j] 时 i=0 | 从 i=1 开始递推，i=0 单独处理 |
| 障碍格 | 过河卒马的控制点 | 令障碍格 dp=0，且不参与递推传播 |
| 数据溢出 | 斐波那契、路径计数 | 统一使用 long long |
| 下标从0还是1 | 杨辉三角从0开始，斐波那契从1开始 | 根据题目习惯选择，保持一致 |
易错点 ⚠️： 过河卒中第一行/第一列的格子，如果前面有障碍格，后面的格子路径数也应该是0（无法绕过障碍到达）。因此边界不能简单填1，而要逐格递推——这是最常见的丢分点！
七、递推的两种代码实现方式
| 方式 | 空间复杂度 | 适用场景 | 典型问题 |
|---|---|---|---|
| 变量迭代法 | O(1) | 只需最终结果，递推只依赖前1~2项 | 斐波那契、爬楼梯、汉诺塔 |
| 数组存储法 | O(n) 或 O(n²) | 需保存中间结果，或依赖多个前驱状态 | 杨辉三角、过河卒、数字三角形 |
选择原则：
- 只需要 f(n) 且公式只依赖前1~2项 → 变量迭代法，节省空间
- 需要输出所有中间结果，或二维递推 → 数组存储法
- 考场上拿不准时 → 优先用数组存储法，逻辑清晰、不易出错
八、📝 实战练习
练习题 1（单选题）
题目： 已知数列定义如下：a₁ = 1, a₂ = 2, a₃ = 3，且对于 n ≥ 4，有 aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃。求 a₈ 的值。 A. 37 B. 48 C. 61 D. 68
🔑 点击查看答案与解析
答案： D
解析： 逐项递推计算：
| n | 计算过程 | aₙ |
|---|---|---|
| 1 | 初始值 | 1 |
| 2 | 初始值 | 2 |
| 3 | 初始值 | 3 |
| 4 | a₃+a₂+a₁ = 3+2+1 | 6 |
| 5 | a₄+a₃+a₂ = 6+3+2 | 11 |
| 6 | a₅+a₄+a₃ = 11+6+3 | 20 |
| 7 | a₆+a₅+a₄ = 20+11+6 | 37 |
| 8 | a₇+a₆+a₅ = 37+20+11 | 68 |
a₈ = 68，选 D。
易错点 ⚠️： 三阶递推（依赖前三项）需要三个初始值。考试中不要看到类似斐波那契的形式就只设两个初值，务必数清楚递推公式依赖几项！
练习题 2（单选题）
题目： 将 n 个圆盘从 A 柱移到 C 柱（借助 B 柱），每次只能移动一个圆盘且大盘不能放在小盘上面。若移动一个圆盘需要1秒钟，H(n) 表示移动 n 个圆盘所需的最少次数，则 H(5) 的值及 H(n) 的通项公式分别为？ A. 15, H(n) = 2ⁿ - 1 B. 31, H(n) = 2ⁿ - 1
C. 31, H(n) = 2n - 1 D. 63, H(n) = 2ⁿ - 1
🔑 点击查看答案与解析
答案： B
解析：
递推关系式：H(n) = 2 × H(n-1) + 1，H(1) = 1。
逐项计算：
| n | 计算过程 | H(n) |
|---|---|---|
| 1 | 初始值 | 1 |
| 2 | 2×1+1 | 3 |
| 3 | 2×3+1 | 7 |
| 4 | 2×7+1 | 15 |
| 5 | 2×15+1 | 31 |
通项公式推导：H(n) = 2ⁿ - 1（可用数学归纳法证明）。
H(5) = 2⁵ - 1 = 31，选 B。
🔥 考试技巧：汉诺塔题的关键是理解"先移 n-1 个盘到辅助柱，再移最大盘，最后移 n-1 个盘到目标柱"的三步策略，由此自然得到递推公式 H(n)=2H(n-1)+1。通项 2ⁿ-1 建议直接记住，考试中可用于快速验证。
练习题 3（填空题）
题目： 在一个 4×4 的网格中（从 (0,0) 到 (4,4)），每次只能向右或向下走一步，但 (2,2) 处有障碍不能经过。问共有多少条不同的路径？
🔑 点击查看答案与解析
答案： 34
解析：
使用二维递推，dp[i][j] 表示从 (0,0) 到 (i,j) 的路径数。障碍格 (2,2) 令 dp[2][2] = 0。
填充 dp 表（第一行和第一列均为1，障碍处为0）：
1 1 1 1 1
1 2 3 4 5
1 3 0 4 9
1 4 4 8 17
1 5 9 17 34递推过程（以关键格为例）：
- dp[2][2] = 0（障碍）
- dp[2][3] = dp[1][3] + dp[2][2] = 4 + 0 = 4
- dp[3][2] = dp[2][2] + dp[3][1] = 0 + 4 = 4
- dp[3][3] = dp[2][3] + dp[3][2] = 4 + 4 = 8
- dp[4][4] = dp[3][4] + dp[4][3] = 17 + 17 = 34
验证（容斥原理）：
- 无障碍总路径数 = C(8,4) = 70
- 经过 (2,2) 的路径数 = C(4,2) × C(4,2) = 6 × 6 = 36
- 不经过 (2,2) 的路径数 = 70 - 36 = 34 ✓
cpp
#include <iostream>
using namespace std;
int main() {
int n = 4;
long long dp[10][10] = {0};
bool blocked[10][10] = {false};
blocked[2][2] = true; // 障碍格
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (blocked[i][j]) {
dp[i][j] = 0;
continue;
}
if (i == 0 && j == 0) dp[0][0] = 1;
else if (i == 0) dp[i][j] = dp[i][j - 1];
else if (j == 0) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[n][n] << endl; // 输出: 34
return 0;
}🔥 高频考点：含障碍的路径计数是过河卒问题的简化版，核心思路完全一致——障碍格 dp=0，其余格 dp[i][j]=dp[i-1][j]+dp[i][j-1]。无障碍时可用组合数 C(m+n, m) 快速验证。
练习题 4（单选题）
题目： 小明爬楼梯，每次可以走 1 级或 2 级。问爬 10 级楼梯共有多少种不同的走法？（ ） A. 55
B. 89
C. 144
D. 233
🔑 点击查看答案与解析
答案： B
解析：
这是经典的爬楼梯问题，递推关系式：f(n) = f(n-1) + f(n-2)
- 到第 n 级的最后一步，要么从 n-1 走 1 级上来，要么从 n-2 走 2 级上来
- 初始条件：
f(1) = 1（只有1种走法），f(2) = 2（1+1 或 2）
逐项计算：
- f(1) = 1
- f(2) = 2
- f(3) = f(2) + f(1) = 2 + 1 = 3
- f(4) = 3 + 2 = 5
- f(5) = 5 + 3 = 8
- f(6) = 8 + 5 = 13
- f(7) = 13 + 8 = 21
- f(8) = 21 + 13 = 34
- f(9) = 34 + 21 = 55
- f(10) = 55 + 34 = 89
选 B。
💡 注意：爬楼梯数列和斐波那契数列类似，但起始项不同。f(1)=1, f(2)=2 对应斐波那契的 f(2)=1, f(3)=2 错开了一位。
练习题 5（判断题）
题目： 递推算法必须用递归函数来实现。（ ）
🔑 点击查看答案与解析
答案： 错误 ❌
解析： 递推是一种算法思想，递归是一种代码实现方式。递推可以用循环（迭代）实现，也可以用递归实现。实际上，递推用循环实现效率更高（避免递归调用的开销和栈溢出风险）。
🍎 生活比喻：递推是"从一楼往上爬楼梯"（从已知往目标推），递归是"从十楼往下问"（把大问题拆成小问题）。两种方式都能到达目的地，但方向相反。
练习题 6（填空题）
题目： 数字三角形递推公式：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]，其中左端 j=0 和右端 j=i 需要特殊处理。
左端的递推式应为：dp[i][0] = ________
右端的递推式应为：dp[i][i] = ________
🔑 点击查看答案与解析
答案：
- 左端：
dp[i-1][0] + a[i][0]（只能从正上方走来） - 右端：
dp[i-1][i-1] + a[i][i]（只能从左上方走来）
解析：
数字三角形第 i 行第 j 列：
- 左端（j=0）：只能从正上方（i-1, 0）走下来，没有左上方
- 右端（j=i）：只能从左上方（i-1, i-1）走下来，没有正上方
- 中间：可以从左上方或正上方走下来，取较大值
⚠️ 易错点：如果忽略边界直接写
max(dp[i-1][j-1], dp[i-1][j])，当 j=0 时会访问 dp[i-1][-1] 导致越界！边界必须单独处理。
练习题 7（填空题）
题目： 假设一对刚出生的小兔，一个月后长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔。如果没有死亡，问第 6 个月共有多少对兔子？
答案： ______ 对
🔑 点击查看答案与解析
答案： 8
解析：
这是经典的兔子繁殖问题，就是斐波那契数列。
设 f(n) 为第 n 个月的兔子对数：
- 第 1 个月：1 对（刚出生的小兔）→ f(1) = 1
- 第 2 个月：1 对（长成大兔，还不能生）→ f(2) = 1
- 第 3 个月：原来的1对大兔 + 新生的1对小兔 = 2对 → f(3) = f(2) + f(1) = 2
- 第 4 个月：f(4) = f(3) + f(2) = 2 + 1 = 3
- 第 5 个月：f(5) = 3 + 2 = 5
- 第 6 个月：f(6) = 5 + 3 = 8
递推公式：f(n) = f(n-1) + f(n-2)，本质就是斐波那契数列。
💡 记忆要点：当月兔子数 = 上月兔子数 + 上上月兔子数（上上月的兔子这个月都能生小兔子了）。
练习题 8（编程题）
题目： 猴子吃桃问题：猴子第一天摘了若干个桃子，每天吃一半多一个，到第 7 天早上想再吃时，只剩下 1 个桃子了。求第一天共摘了多少个桃子？
提示：用倒推法——从第 7 天的 1 个桃子，反推第 6 天、第 5 天...直到第 1 天。
🔑 点击查看答案与解析
参考答案：
cpp
#include <iostream>
using namespace std;
int main() {
int peach = 1; // 第7天早上剩下1个
// 倒推：从第6天推到第1天，共推6次
for (int day = 6; day >= 1; day--) {
// 当天桃子数 = (前一天桃子数 + 1) × 2
// 因为：前一天吃了一半多一个，剩下的是一半少一个
// 所以：剩下的 = 当天/2 - 1 → 当天 = (剩下的 + 1) * 2
peach = (peach + 1) * 2;
}
cout << peach << endl;
return 0;
}
// 输出：190解析：
这是一道经典的倒推递推题。正向计算不知道初始值，但知道最终结果和变化规律，可以倒着推。
正推公式：当天剩下 = 前一天总数 / 2 - 1 倒推公式：前一天总数 = (当天剩下 + 1) × 2
从第 7 天的 1 个开始倒推 6 次：
- 第 6 天：(1 + 1) × 2 = 4
- 第 5 天：(4 + 1) × 2 = 10
- 第 4 天：(10 + 1) × 2 = 22
- 第 3 天：(22 + 1) × 2 = 46
- 第 2 天：(46 + 1) × 2 = 94
- 第 1 天：(94 + 1) × 2 = 190
💡 递推技巧：正向不好算就试试倒推！知道终点和变化规则，反向推导也是递推的常用思路。
九、📊 考点总结表
| 考点 | 重要程度 | 出题形式 | 易错点 |
|---|---|---|---|
| 递推三要素 | ⭐⭐⭐⭐ | 选择/填空/编程 | 遗漏初始条件或递推式写错 |
| 斐波那契及变体 | ⭐⭐⭐⭐⭐ | 选择/程序阅读/编程 | 初始条件记错，递推项数搞错 |
| 爬楼梯问题 | ⭐⭐⭐⭐ | 选择/编程 | 起始项和斐波那契错开一位 |
| 汉诺塔 H(n)=2ⁿ-1 | ⭐⭐⭐⭐ | 选择/判断 | 通项公式记混，n=1时验证 |
| 过河卒（含障碍） | ⭐⭐⭐⭐⭐ | 编程题 | 边界有障碍时不能直接填1，要逐格递推 |
| 数字三角形 | ⭐⭐⭐⭐ | 编程题 | 左右两端边界处理错误导致越界 |
| 边界处理 | ⭐⭐⭐⭐⭐ | 贯穿所有编程题 | 首行首列、障碍格考虑不周 |
| long long 防溢出 | ⭐⭐⭐⭐ | 贯穿所有题 | 路径数、斐波那契数容易溢出int |
| 递推 vs 递归 | ⭐⭐⭐ | 选择/判断 | 递推是思想，递归是实现方式 |
⭐ 必背速记卡
┌─────────────────────────────────────────────┐
│ 递推算法 · 必背速记卡 │
├─────────────────────────────────────────────┤
│ 1. 递推三要素：初始条件+递推式+终止条件 │
│ 2. 斐波那契：f(n)=f(n-1)+f(n-2), f(1)=1,f(2)=1│
│ 3. 爬楼梯：f(n)=f(n-1)+f(n-2), f(1)=1,f(2)=2│
│ 4. 汉诺塔：H(n)=2ⁿ-1，递推式 H(n)=2H(n-1)+1 │
│ 5. 兔子繁殖 = 斐波那契数列 │
│ 6. 路径计数：dp[i][j]=dp[i-1][j]+dp[i][j-1]│
│ 7. 过河卒：障碍格dp=0，阻断后续路径 │
│ 8. 过河卒边界有障碍时，后面的格子路径数为0 │
│ 9. 数字三角形：dp[i][j]=max(左上,正上)+a[i][j]│
│ 10. 数字三角形两端：只能从一个方向来 │
│ 11. 递推实现：变量迭代法 O(1)，数组法 O(n) │
│ 12. 优先用数组法：逻辑清晰不易错 │
│ 13. 路径数、斐波那契数用 long long 防溢出 │
│ 14. 递推方向不能反：必须保证算当前时前面已算出│
│ 15. 正向不行就倒推，知道终点也能递推 │
└─────────────────────────────────────────────┘