← 目录 / 算法文档 · 模块八 递推与递归 / 8.1 递推

8.1　递推

用"已知的结果"推出"下一个结果"，一步一步向前——这就是递推。它是动态规划的前身，也是理解递归的基础。

本页目录
① 什么是递推

递推的核心思想只有一句话：当前状态 = f（之前的状态）。

想象爬楼梯。你站在第 5 级台阶上，是因为你从第 4 级（或第 3 级）迈过来的。第 4 级是怎么到的？从第 3 级（或第 2 级）来的……每一级的答案，都建立在它之前的答案上。只要知道了最开始几级的情况，就能一路推算到任意一级。

递推的三个要素：

递推三要素
① 初始状态
最开始的已知值，递推的起点。没有它，推导链就没有出发点。
② 递推关系式
描述"第 n 项"和"之前几项"之间规律的公式。这是解题的核心。
③ 循环求解
从初始状态出发，按关系式一步步算到目标，用数组存下每一步的结果。
② 斐波那契数列：最经典的递推

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34 ……

规律：从第 3 项开始，每一项等于前两项之和。用数学式子写就是：

f(1) = 1，f(2) = 1，f(n) = f(n−1) + f(n−2)　　（n ≥ 3）

初始状态：f(1)=1，f(2)=1。递推关系：f(n) = f(n-1) + f(n-2)。三要素全齐，直接写代码：

C++ · 斐波那契数列
1const int MAXN = 50;
2long long f[MAXN];
3
4int main() {
5 f[1] = 1; f[2] = 1; // ① 初始状态
6 for (int i = 3; i <= 10; i++) // ③ 循环求解
7 f[i] = f[i-1] + f[i-2]; // ② 递推关系式
8 for (int i = 1; i <= 10; i++)
9 cout << f[i] << " "; // 1 1 2 3 5 8 13 21 34 55
10}
③ 执行过程图解

循环从 i=3 开始，每次用已知的两个值推出新的一个，绿色格子是已知值，红色是当前正在求的值：

f 数组的填充过程（求前 8 项）
i = 3
1
f[1]
1
f[2]
2
f[3]
?
f[4]
?
f[5]
?
f[6]
?
f[7]
?
f[8]
f[2]+f[1]=2
i = 4
1
f[1]
1
f[2]
2
f[3]
3
f[4]
?
f[5]
?
f[6]
?
f[7]
?
f[8]
f[3]+f[2]=3
i = 5
1
f[1]
1
f[2]
2
f[3]
3
f[4]
5
f[5]
?
f[6]
?
f[7]
?
f[8]
f[4]+f[3]=5
完成
1
f[1]
1
f[2]
2
f[3]
3
f[4]
5
f[5]
8
f[6]
13
f[7]
21
f[8]
绿色格子是已知（已推出）的值，红色是当前正在计算的目标，橙色是它依赖的前两项。
每一步只需要"往左看两格"，循环结束后整个数组就填满了。
④ 更多递推模型

递推不止一种形式，下面是竞赛中常见的几类：

C++ · 爬楼梯（每次可走 1 或 2 步，到第 n 级有多少种走法）
1// 到第 i 级 = 从第 i-1 级走一步 + 从第 i-2 级走两步
2// 本质和斐波那契完全一样，换了个描述
3long long dp[MAXN];
4dp[1] = 1; dp[2] = 2; // 初始：到第1级1种，到第2级2种
5for (int i = 3; i <= n; i++)
6 dp[i] = dp[i-1] + dp[i-2];
C++ · 数字三角形：每格的最大路径和
1// 三角形第 i 行第 j 列：可从上一行第 j-1 或第 j 列走来
2for (int i = 2; i <= n; i++)
3 for (int j = 1; j <= i; j++)
4 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];
5 // 当前格 = max(左上格, 右上格) + 当前格的值
C++ · 最长不下降子序列长度（LIS 的 O(n²) 递推版）
1// dp[i]：以 a[i] 结尾的最长不下降子序列长度
2for (int i = 1; i <= n; i++) {
3 dp[i] = 1; // 初始：至少只有自己这一个
4 for (int j = 1; j < i; j++)
5 if (a[j] <= a[i]) // j 可以接在 i 前面
6 dp[i] = max(dp[i], dp[j] + 1);
7}
💡
这三个例子虽然题目不同，但结构一模一样：确定 dp 数组的含义 → 写出递推关系式 → 处理边界（初始状态）→ 循环填表。这四步就是递推（也是动态规划）的通用解题框架。
⑤ 递推的通用写法

无论哪种递推题，代码骨架几乎都是这样：

C++ · 递推通用模板
1// 一维递推
2dp[0] = 初始值; dp[1] = 初始值; // ① 边界
3for (int i = 2; i <= n; i++) // ③ 循环
4 dp[i] = f(dp[i-1], dp[i-2], ...); // ② 关系式
5
6// 二维递推（如网格/矩阵）
7// 初始化第 0 行和第 0 列
8for (int i = 1; i <= n; i++)
9 for (int j = 1; j <= m; j++)
10 dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...);
⚠️
三个常见错误：
① 忘记初始化边界——dp 数组默认是 0，如果初始值不是 0，必须手动设置。
② 循环起点写错——如果 dp[i] 依赖 dp[i-1] 和 dp[i-2]，循环必须从 i=2（或 i=3）开始，从 i=1 开始会越界。
③ 数组越界——dp 数组的大小要比 n 至少大 1，下标通常从 1 开始而不是 0。
⑥ 递推 vs 递归

递推和递归都能解决"用之前的结果推出当前结果"的问题，但方向相反：

对比项递推（本节）递归（下一节）
方向 从小到大，自底向上 从大到小，自顶向下
实现方式 for 循环 + 数组 函数调用自身
优点 效率高，无函数调用开销，不会栈溢出 思路直接，代码与数学定义接近
缺点 需要想清楚填表顺序，二维时容易搞错方向 重复计算多（需加记忆化优化），深度大时栈溢出
适用场景 能明确推导顺序的问题，竞赛中首选 推导方向不固定、子问题结构复杂的问题
📖
本节小结
・递推 = 初始状态 + 递推关系式 + 循环，三要素缺一不可。
・dp 数组存下每一步的结果，避免重复计算，时间复杂度通常是 O(n) 或 O(n²)。
・竞赛中递推几乎就是动态规划的雏形——把 dp[i] 的含义想清楚，关系式就自然出来了。
・下一节学递归，理解两者的关系之后，动态规划就水到渠成了。