递推📦

Quote

1. 什么是递推？

递推（Recurrence / Iterative Transition），本质上是：

已知前面若干项，通过某种规律，推出后面的项。

也就是：

从已知结果出发
一步一步算出后续答案
当前状态依赖之前状态

最简单例子：斐波那契数列

1 1 2 3 5 8 13 ...

规律：

f[n] = f[n-1] + f[n-2]

意思：

第 n 项 = 前两项之和

已知：

f[1]=1
f[2]=1

然后一路推出后面所有值。

2. 递推和递归区别（考试常问）

很多人会混淆。

递归（函数自己调用自己）

int f(int n){
    if(n<=2) return 1;
    return f(n-1)+f(n-2);
}

特点：

自上而下求解
会反复调用
容易爆栈
效率低（若无记忆化）
递推（循环推出来）

f[1]=1;
f[2]=1;
for(int i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2];

特点：

自下而上
快
稳定

3. 递推优于递归

因为很多题目：

数据范围大
要求快速
状态有规律
暴力搜索会超时

递推通常：

O(n)
O(n log n)

而暴力可能：

O(2^n)

4. 递推题的核心思想（最重要）

做递推题时只问自己三件事：

① 状态是什么？

定义：

f[i] 表示什么？

例如：

前 i 项方案数
到第 i 层的方法数
长度 i 的答案
前 i 天最大收益

② 转移怎么来？

即：

f[i] 如何由前面推出？

例如：

f[i]=f[i-1]+f[i-2]

③ 初值是什么？

例如：

f[1]=1
f[2]=2

初值错，全部错。

5. 常见递推类型

数列型递推

如：

斐波那契
阶乘
Lucas 数列

形式：

f[i]=...

方案计数型

问：

有多少种方法？

例如：

上楼梯
走格子
拼图

常见：

f[i]=f[i-1]+f[i-2]

最值递推

问：

最大收益
最短距离
最少次数

例如：

f[i]=max(...)
f[i]=min(...)

二维递推

例如网格路径：

f[i][j]=f[i-1][j]+f[i][j-1]

前缀递推

例如：

sum[i]=sum[i-1]+a[i]

6. 入门例子：爬楼梯

每次走 1 步或 2 步，走到第 n 阶多少种方法？

分析：

到第 n 阶：

最后一步走 1 阶 → 来自 n-1
最后一步走 2 阶 → 来自 n-2

所以：

f[n]=f[n-1]+f[n-2]

初值：

f[1]=1
f[2]=2

C++代码

int f[1005];
f[1]=1;
f[2]=2;

for(int i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2];

7. 做递推题万能步骤（比赛实战）

第一步：

定义状态：

f[i] = ...

第二步：

考虑最后一步 / 最后一次操作

这是找转移公式最快的方法。

第三步：

写初值

第四步：

for 循环推到 n

8. 递推和动态规划关系

很多同学问：

递推和 DP 是不是一样？

答案：

DP ≈ 更高级的递推

动态规划本质也是：

定义状态
状态转移
初始化
递推计算

所以蓝桥杯中：

很多 DP 题其实就是递推题升级版

9. 算法课常考递推模型

一维

f[i]

二维

f[i][j]

滚动数组优化

只保留前几项

例如斐波那契只需 2 个变量。

10. 初学者最容易错的地方

状态定义不清

不知道 f[i] 表示什么。

初值错

最常见。

下标越界

f[i-2]

注意 i 从几开始。

long long 溢出

方案数题常爆 int。

11. 一句话理解递推

递推就是：把大问题拆成前面已经算过的小问题，再一步步推到答案。

12. 频率极高的题型

台阶问题
数塔问题
网格路径
背包入门
数列求值
字符串计数
状态压缩前置题

先刷这 5 题：

斐波那契数列
爬楼梯
杨辉三角
网格路径数
最小花费路径

递推📦