一、 递推
1. 递推的定义与特点
● 递推思想：通过已知条件和递推关系式逐步推导出问题的解
● 适用场景：问题可以分解为相似的子问题，且子问题之间有明确的递推关系(状态转移)
● 核心特点：避免重复计算，通常时间复杂度为 O(n)或 O(n2)
2. 递推的关键要素
● 初始条件：明确递推的起点
● 递推关系式/状态转移：确定如何从已知解推导出未知解
● 求解顺序：明确计算顺序（正向或反向）
3.递推的常见应用场景
● 数列问题：斐波那契数列、爬楼梯问题等
● 路径计数：杨辉三角、网格路径问题等
● 动态规划基础：许多动态规划问题本质上是递推的延伸
二、递推应用演示/习题
1. 演示1：一维递推基础，顺推（斐波那契数列）
问题：计算斐波那契数列第n项
解法：使用一维数组存储中间结果，按关系顺序推导
#include<bits/stdc++.h>
using namespace std;
//设f[i]代表斐波那契数列第i项
long long f[105];
int main(){
int n;cin>>n;//求第n项
//初始化状态
f[1]=f[2]=1;
//从第3项开始推导至第n项
//递推关系/状态转移：当前项 = 前一项+前二项
for(int i=3;i<=n;i++){
f[i] = f[i-1] + f[i-2];
}
//输出第n项
cout<<f[n];
return 0;
}
输入样例1： 6 输出样例1： 8
拓展：其他类似于爬楼梯，纸张折痕等，都可以参考这种思路，把问题求解过程变成求数列第n项的问题
台阶问题：一次走1步或者2步，上n级台阶方案数量？
//初始化状态
f[1] = 1; f[2]=2
//从第三项开始递推
f[i]=f[i-1] + f[i-2]
将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到 7 条折痕，那么对折 n 次，可得到几条折痕？
//从第一项开始递推
f[i] = f[i-1] * 2 + 1
//当然这一题还有O(1)的做法
2^n - 1
2. 演示2，一维递推变式，反推（猴子吃桃问题）
问题：一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；接下来的每一天它都会吃剩余的桃子的一半外加一个。第 n 天早上起来一看，只剩下 1 个桃子了。请问小猴买了几个桃子？ 。
解法：第n天剩1个桃子，求第一天剩几个，本质上也是求数列的第n项，只是用最后一天剩下的1个桃子来作为初始状态
#include<bits/stdc++.h>
using namespace std;
//设f[i]代表猴子倒数第i天的桃子数量
//第1天的桃子数量就是数列第n项
long long f[105];
int main(){
int n;cin>>n;//求第n项
//初始化状态
f[1]=1;
//从第2项开始推导至第n项
//递推关系/状态转移：当前项 = 前一项+前二项
for(int i=2;i<=n;i++){
f[i] = (f[i-1]+1) * 2;
}
//输出第n项
cout<<f[n];
return 0;
}
输入样例1： 4 输出样例1： 22
3. 演示3：杨辉三角
问题：根据规律，输出n行的杨辉三角
解法：每行的第一列最后一列均为1，其他位置均为 “上一行 + 上一行前一列”
#include<bits/stdc++.h>
using namespace std;
//设f[i][j] 代表杨辉三角i行j列的位置
int f[25][25];
int main() {
int n;
cin >> n; //输出n行的杨辉三角
//为方便大家观察和理解递推思想，我们把1的位置单独拎出来初始化
//tips：实际上这一步可以直接结合在递推中进行
for (int i = 1; i <= n; i++) {
f[i][1] = 1; //所有第一列都是1
f[i][i] = 1; //每行的最后一列是1
}
//递推 : 除去已经初始化完成的位置
//其他位置： 当前项 = 上一行 + 上一行前一列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
//不是第一列或者最后一列才需要遵循推导归路
if (j != 1 && j != i) {
f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
}
cout << f[i][j] << " "; //推导完直接输出
}
cout << endl;//记得换行
}
return 0;
}
4. 演示4：路径计数，二维递推（网格路径问题）
问题：一个N×N的网格，你一开始在(1,1)，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达(N,N)，即右下角有多少种方法。
解法：
● 这里以4*4的网格为例，根据只能移向右和向下的移动规则，则移动到第一行第一列的位置方案只能是1，因为只能从左边或上方的格子移动过来
● 初始化完成后，我们可以开始推导剩下的格子路线有什么规律，以[2,2]的格子为例子，根据移动规则，这个格子只能从上方[1,2]和左方[2,1]移动到达，也意味着到达上述两地点的路线，都可以到达[2,2]，那么路线数量[2,2] = [1,2] + [2,1]
● 根据上述规律，我们可以总结出递推规律：[i,j] = [i-1,j] + [i,j-1]，那么以此类推剩下的单元格，最后右下角的位置就代表了左上角起点[1,1]到达[n,n]的路线数量
#include<bits/stdc++.h>
using namespace std;
//设f[i][j] 代表[1,1]到达[i,j]的路线数量
int f[25][25];
int main() {
int n;
cin >> n; //n*n地图
//初始化状态
for (int i = 1; i <= n; i++) f[1][i] = 1; //第一行
for (int i = 1; i <= n; i++) f[i][1] = 1; //第一列
//递推：从[2,2]开始递推
//递推规律/状态转移：当前位置 = 上方 + 左方
for(int i=2;i<=n;i++){
for(int j=2;j<=n;j++){
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
//输出到达[n,n]的路线数量
cout<<f[n][n];
return 0;
}
输入样例1： 4 输出样例1： 20
5 演示4拓展：路径计数带障碍物
问题：一个N×N的网格，你一开始在(1,1)，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达(N,N)，即右下角有多少种方法。但是这个问题太简单了，所以现在有M个格子上有障碍，即不能走到这M个格子上。（数据保证起始点和终止点无障碍物，并且起点到终点至少存在一条通路）。
解法：
● 虽然增加了障碍物，但思路依然可以延续上述的方式，我们可以增加一个对应地图大小的vis标记数组来标记[i,j]位置是否可以通行，不能通行的地方路线数量为0，不需要推导。例如[3,3]是障碍物，那我们推导时跳过这个位置就行。
● 额外需要注意的一点，障碍物应在初始化数组前标记，因为初始化过程中碰到障碍物的话，应停止初始化，因为后续位置也无法到达，不注意这一点可能会导致递推结果出错。
#include<bits/stdc++.h>
using namespace std;
//设f[i][j] 代表[1,1]到达[i,j]的路线数量
int f[25][25];
//vis[i][j]为1代表[i,j]不能通行，为0代表可以通行
bool vis[25][25];
int main() {
int n,m;
cin >> n >> m; //n*n地图 ，m个障碍物
//标记障碍物
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y; // 障碍物坐标
vis[x][y] = 1;
}
//初始化状态
for (int i = 1; i <= n; i++) {
if (vis[1][i] == 1) break;
f[1][i] = 1; //第一行
}
for (int i = 1; i <= n; i++) {
if (vis[i][1] == 1) break;
f[i][1] = 1; //第一列
}
//递推：从[2,2]开始递推
//递推规律/状态转移：当前位置 = 上方 + 左方
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= n; j++) {
if (vis[i][j] == 0) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
}
//输出到达[n,n]的路线数量
cout << f[n][n];
return 0;
}
输入样例1：3 1 输出样例1：5
3 1
● 练习过程中若地图比较大，可能会导致递推结果溢出int类型，所以记得开long long或者根据题目取模噢