递推和递归
递推
递推算法的核心在于自底向上，由已知条件推导出结果。关键在于确定状态转移方程、边界条件和关系式。
直接通过题目来理解递推思想。以棋盘路径问题为例：从 A 点到 B 点的路径数，且经过马能到达的点都无效。
首先定义移动方向和标记数组。
// 马走日，移动的位置（马能到达的点）
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};// 标记数组
int rd[110][110]={0};// 记录每个点的路径数
将马能到达的位置全标记成 1，包括初始位置。
for(int i=0;i<=7;i++){
int nx=cx+mx[i];
int ny=cy+my[i];
if(nx<0 || ny<0 || nx>n || ny>m)continue;
vis[nx][ny]=1;
}
vis[cx][cy]=1;
初始化边界，起点置为一。注意左边界和上边界的处理，如果该点被马标记则路径数为 0。
rd[0][0]=1;
for(int i=1;i<=n;i++){
rd[i][0]=rd[i-1][0];
if(vis[i][0]==1)rd[i][0]=0;
}
for(int i=1;i<=m;i++){
rd[0][i]=rd[0][i-1];
if(vis[0][i]==1)rd[0][i]=0;
}
卒只能向下或向右移动，因此到达点 (i, j) 的路径数等于上方点与左方点路径数之和。
关系式：rd[i][j] = rd[i-1][j] + rd[i][j-1]
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==1)continue;
rd[i][j]=rd[i-1][j]+rd[i][j-1];
}
}
完整代码如下。注意数据范围可能溢出，需使用 long long。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mx[] = {-1,-1,-2,-2,1,1,2,2};
int my[] = {-2,2,-1,1,-2,2,-1,1};
int vis[110][110]={0};
int rd[110][110]={0};
signed main(){
int n,m,cx,cy;
cin>>n>>m>>cx>>cy;
vis[cx][cy]=1;
for(int i=0;i<=7;i++){
int nx=cx+mx[i];
int ny=cy+my[i];
if(nx<0 || ny<0 || nx>n || ny>m)continue;
vis[nx][ny]=1;
}
rd[0][0]=1;
for(int i=1;i<=n;i++){
rd[i][0]=rd[i-1][0];
if(vis[i][0]==1)rd[i][0]=0;
}
for(int i=1;i<=m;i++){
rd[0][i]=rd[0][i-1];
if(vis[0][i]==1)rd[0][i]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==1)continue;
rd[i][j]=rd[i-1][j]+rd[i][j-1];
}
}
cout<<rd[n][m]<<endl;
return 0;
}
核心要点： 递推有两要素：边界条件和关系式。只要正确推出这两个要素，再从已知推未知，就可以轻松解决递推问题。
递归
经典引入
递归算法是直接或间接调用自身函数，通过循环回溯解决小问题，最后得出大问题的答案。核心是找到终止条件，否则会导致无限循环。
以斐波那契数列为例，公式为 f(n) = f(n-1)+f(n-2)。在函数中，当前第 n 位函数调用前两位，直到最底层返回结果。
int fb(int x){
if(x==1 || x==2)return 1;
return fb(x-1)+fb(x-2);
}
完整代码示例：
#include<bits/stdc++.h>
using namespace std;
int fb(int x){
if(x==1 || x==2)return 1;
return fb(x-1)+fb(x-2);
}
int main(){
int n;
cin>>n;
while(n--){
int num;
cin>>num;
cout<<fb(num)<<endl;
}
}
深入理解
结合正则表达式最长字符串匹配问题。规则如下：
( )及内容视为一组。|为分界线，两边长度互不干扰，取最大值。x为普通字符。
例如 ((xx|xxx)x|(x|xx))xx，先拆分组，计算每组最大长度，再累加普通字符。
核心逻辑是不断找组，根据符号判断。由于代码较完整，直接展示带注释的解法。
#include<bits/stdc++.h>
using namespace std;
int i=0;
string s;
int Longest(){
int m_cnt=0;
int cnt=0;
while(i < s.size()){
if(s[i] == '('){
i++;
int n = Longest();
cnt += n;
} else if(s[i] == 'x'){
cnt++;
i++;
} else if(s[i] == '|'){
m_cnt = max(m_cnt,cnt);
cnt=0;
i++;
} else {
i++;
break;
}
}
return max(cnt,m_cnt);
}
int main(){
cin>>s;
cout<<Longest();
}
核心要点： 递归最重要的一步是找到终止条件。找到式子间的关系，再循环调用即可解决问题。
BFS 广度优先搜索
基础模板
BFS 是一种图的遍历算法，从浅到深，宽度遍历。从一个节点开始，找它的邻居，再找邻居的邻居。
实现方式主要有两种：邻接矩阵和邻接表。邻接矩阵结构简单但空间复杂度高；邻接表适合数据量大的情况。
邻接矩阵实现
适用于无向图，n 个点，m 条边。
#include<bits/stdc++.h>
using namespace std;
int g[105][105];
int vis[105];
int n,m;
void bfs(int start){
queue<int> q;
q.push(start);
vis[start] = 1;
while(!q.empty()){
int cur = q.front();
q.pop();
for(int i=1;i<=n;i++){
if(g[cur][i] == 1 && vis[i] == 0){
vis[i] = 1;
q.push(i);
}
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v;
cin >> u >> v;
g[u][v] = 1;
g[v][u] = 1;
}
bfs(1);
return 0;
}
邻接表实现
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[105];
int vis[105];
int n,m;
void bfs(int start){
queue<int> q;
q.push(start);
vis[start] = 1;
while(!q.empty()){
int cur = q.front();
q.pop();
for(int i=0;i<adj[cur].size();i++){
int nxt = adj[cur][i];
if(vis[nxt] == 0){
vis[nxt] = 1;
q.push(nxt);
}
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs(1);
return 0;
}
BFS 最短路问题
在无向图中求两点间最短路径。BFS 第一次走到某个点时，即为最短路径。
需要记录步数，结构体存储节点 ID 和步数。
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[105];
int vis[105];
int n,m;
int a,b;
struct node{
int id;
int step;
};
void bfs(int start){
queue<node> q;
node tmp;
tmp.id = start;
tmp.step = 0;
q.push(tmp);
vis[start] = 1;
while(!q.empty()){
int curId = q.front().id;
int curStep = q.front().step;
q.pop();
for(int i=0;i<adj[curId].size();i++){
node nxt;
nxt.id = adj[curId][i];
nxt.step = curStep + 1;
if(nxt.id == b){
cout << nxt.step << endl;
return;
}
if(vis[nxt.id] == 0){
vis[nxt.id] = 1;
q.push(nxt);
}
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> a >> b;
bfs(a);
return 0;
}
DFS 深度优先搜索
基础模板
DFS 算法纵向搜索，尽可能深地探入，直到无法搜索，然后回溯。核心思想是递归调用。
同样提供邻接矩阵和邻接表两种实现。
邻接矩阵实现
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int a[N][N];
int vis[N];
void dfs(int cur){
vis[cur]=1;
for(int i=1;i<=n;i++){
if(a[cur][i]==1 && vis[i]==0){
dfs(i);
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v;
cin >> u >> v;
a[u][v]=1;
a[v][u]=1;
}
dfs(1);
return 0;
}
邻接表实现
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
vector<int>a[N];
int vis[N];
void dfs(int cur){
vis[cur]=1;
for(int i=1<a[cur].size();i++){
int nxt=a[cur][i];
if(vis[nxt]==0){
dfs(i);
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int u,v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1);
return 0;
}
迷宫问题
DFS 版
迷宫问题通常要求判断能否从起点走到终点。支持上下左右移动，不能穿墙。
多组测试数据时，建议使用邻接矩阵而非邻接表，因为输入新数据时旧数据会被清空，避免清理动态数组的麻烦。
需要方向数组控制移动：nx[]={-1,0,0,1}, ny[]={0,-1,1,0}。
#include<bits/stdc++.h>
using namespace std;
int n;
char maze[110][110];
int vis[110][110];
int xA,yA,xB,yB;
int nx[]={-1,0,0,1};
int ny[]={0,-1,1,0};
bool judge(int x,int y){
if(x<0 || y<0 || x>=n || y>=n)return false;
if(maze[x][y]=='.')return true;
else return false;
}
bool dfs(int sx,int sy){
int cur_x=sx;
int cur_y=sy;
vis[cur_x][cur_y]=1;
if(cur_x == xB && cur_y == yB)return true;
for(int i=0;i<4;i++){
int nxt_x=cur_x+nx[i];
int nxt_y=cur_y+ny[i];
if(judge(nxt_x,nxt_y) && vis[nxt_x][nxt_y]==0){
if(dfs(nxt_x,nxt_y))return true;
}
}
return false;
}
int main(){
int k;
cin>>k;
while(k--){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char c;
cin>>c;
maze[i][j]=c;
vis[i][j]=0;
}
}
cin>>xA>>yA>>xB>>yB;
bool ans=dfs(xA,yA);
if(ans)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
BFS 版
BFS 版本用于求解迷宫最短路。DFS 需要罗列所有路径，复杂度指数级；BFS 第一次走到终点即为最短路，复杂度 O(n)。
基本思路相同，主要区别在于使用队列存储状态。
#include<iostream>
#include<queue>
using namespace std;
int n;
char maze[110][110];
int vis[110][110];
int xA, yA, xB, yB;
int nx[] = {-1, 0, 0, 1};
int ny[] = {0, -1, 1, 0};
bool judge(int x, int y) {
if (x < 0 || y < 0 || x >= n || y >= n) return false;
if (maze[x][y] == '.') return true;
else return false;
}
void bfs(int sx, int sy) {
queue<pair<int, int>> q;
q.push({sx, sy});
vis[sx][sy] = 1;
while (!q.empty()) {
int cur_x = q.front().first;
int cur_y = q.front().second;
q.pop();
if (cur_x == xB && cur_y == yB) {
return;
}
for (int i = 0; i < 4; i++) {
int nxt_x = cur_x + nx[i];
int nxt_y = cur_y + ny[i];
if (judge(nxt_x, nxt_y) && vis[nxt_x][nxt_y] == 0) {
q.push({nxt_x, nxt_y});
vis[nxt_x][nxt_y] = 1;
}
}
}
}
int main() {
int k;
cin >> k;
while (k--) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char c;
cin >> c;
maze[i][j] = c;
vis[i][j] = 0;
}
}
cin >> xA >> yA >> xB >> yB;
bfs(xA, yA);
if (vis[xB][yB]) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
以上就是迷宫问题的基本思路和解法，希望带给大家一点启发。