c++ dfs搜索算法——记忆化搜索
本文介绍了记忆化搜索的核心思想和实现方法，并通过三个例题展示其应用。记忆化搜索通过保存重复计算结果来优化递归算法，关键在于使用数组或map存储状态。首先以斐波那契数列为例，对比普通递归和记忆化搜索的时间效率差异。随后解析蓝桥云课"混境之地5"问题，展示如何将暴力DFS转化为记忆化搜索。最后以"地宫取宝"为例，说明记忆化搜索在复杂路径问题中的应用。文章强调记忆
·
目录
原创作品，多多支持！
一，简介
1.核心思想：也叫带备忘录的搜索，将搜索过程中会重复计算且结果相同的部分保存下来，作为一个状态；下次访问到这个状态时，直接返回该子搜索的结果，无需重新计算。
2.实现方式：通常使用数组或map来进行记忆化，其下标一般和 dfs 的参数表对应。
3.注意事项：使用记忆化必须保证重复计算的结果是相同的，否则可能导致数据失真。
二，例题详解
1.斐波那契数列
设 F[1]=1,F[2]=1,F[n]=F[n−1]+F[n−2]，求 F[n]，结果对 1e9+7 取模。
范围：1≤n≤10000
样例输入：
5000
样例输出：
976496506
小贴士：如果直接采用递归来做，时间复杂度将接近 O(2^n)，但是我们会发现有大部分的重复计算，比如 F[n−2] 在求 F[n] 的时候算过，在求 F[n−1] 的时候又被算了一次，而 F[1] 计算次数更多了，但它们在重复计算时候的结果是相同的，所以可以采用记忆化。
普通递归写法：
#include<iostream>
using namespace std;
using ll=long long;
const ll p=1e9+7;
ll f(int n)
{
if(n<=2) return 1;
return (f(n-1)+f(n-2))%p;
}
int main()
{
int n;cin>>n;
cout<<f(n)<<'\n';
return 0;
}这样写会超时，当n=50时，编译器就会运算很久。
记忆化搜索写法：
#include<iostream>
#include<cstring>
using namespace std;
using ll=long long;
const ll p=1e9+7;
const int N=1e4+9;
ll dp[N];//dp[n]存储f(n)的值
ll f(int n)
{
if(n<=2) return 1;
//当dp[n]!=-1，说明已经计算过，直接保留，用现成的
if(dp[n]!=-1) return dp[n];
return dp[n]=(f(n-1)+f(n-2))%p;
}
int main()
{
int n;cin>>n;
memset(dp,-1,sizeof(dp));
cout<<f(n)<<'\n';
return 0;
}2.蓝桥云课——混境之地5
代码详解
1.纯暴力dfs：时间复杂度高
#include<iostream>
using namespace std;
const int N=1e3+9;
int h[N][N];//记录每个点的高度
int dp[N][N];
int n,m,k;
int ix,iy,ex,ey;//入口和出口
//判断是否出界：
bool matrix(int x,int y)
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
//先用暴力dfs（递归方式）
bool dfs(int x,int y,int t)//这里dfs要设置3个参数，现在的位置（x，y），还有用没用过背包！
{
//如果已经到出口，直接返回
if(x==ex&&y==ey) return true;
for(int i=0;i<4;i++)//向四个方向行走,之后的所有点都在这个循环里面判断
{
int nx=x+dx[i];
int ny=y+dy[i];
if(!matrix(nx,ny)) continue;
//下面分几种情况：
//还没用背包：1.下一次我不用背包2.下一次我要用背包
//已经用了背包：下一次我用不了背包了
if(t==0)
{
if(h[nx][ny]<h[x][y] && dfs(nx,ny,0)) return true;
if(h[nx][ny]<h[x][y]+k && dfs(nx,ny,1)) return true;
}
else
{
if(h[nx][ny]<h[x][y] && dfs(nx,ny,1)) return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
cin>>ix>>iy>>ex>>ey;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>h[i][j];
}
}
cout<<(dfs(ix,iy,0)?"Yes":"No")<<'\n';
return 0;
}2.采用记忆化搜索:
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e3+9;
int h[N][N];//记录每个点的高度
int n,m,k;
int ix,iy,ex,ey;//入口和出口
int dp[N][N][2];//记忆化数组，dp[x][y][t]记录的是在背包情况为t下，能否到达终点，其存储的值是true or false；
//判断是否出界：
bool matrix(int x,int y)
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
//现在采用记忆化搜索！
bool dfs(int x,int y,int t)//这里dfs要设置3个参数，现在的位置（x，y），还有用没用过背包！
{
//如果已经到出口，直接返回
if(x==ex&&y==ey) return true;
if(dp[x][y][t]!=-1) return dp[x][y][t];//若当前点已经被判断过可以or不可以到达终点，
//既然已经计算过这个状态的结果，就不需要再重复递归搜索了，直接返回之前计算好的结果即可。
for(int i=0;i<4;i++)//向四个方向行走,之后的所有点都在这个循环里面判断
{
int nx=x+dx[i];
int ny=y+dy[i];
if(!matrix(nx,ny)) continue;
//下面分几种情况：
//还没用背包：1.下一次我不用背包2.下一次我要用背包
//已经用了背包：下一次我用不了背包了
if(t==0)
{
if(h[nx][ny]<h[x][y] && dfs(nx,ny,0)) return dp[nx][ny][t] = true;
if(h[nx][ny]<h[x][y]+k && dfs(nx,ny,1)) return dp[nx][ny][t] = true;
}
else
{
if(h[nx][ny]<h[x][y] && dfs(nx,ny,1)) return dp[nx][ny][t] = true;
}
}
return dp[x][y][t] = false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
memset(dp,-1,sizeof(dp));
cin>>n>>m>>k;
cin>>ix>>iy>>ex>>ey;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>h[i][j];
}
}
cout<<(dfs(ix,iy,0)?"Yes":"No")<<'\n';
return 0;
}3.蓝桥云课——地宫取宝
这是14年蓝桥杯省赛真题。
1.暴力dfs：只能通过一半案例
时间复杂度将达到o(2^(n+m))，非常高
#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;
const int N=1e3+9;
const ll p=1e9+7;
int c[N][N];//记录每个点的宝物价值
int n,m,k;//出口点（右下角）以及手里最大宝物数量
//判断是否出界：
bool matrix(int x,int y)
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
int dx[]={1,0};
int dy[]={0,1};
//先使用暴力版本
//这里dfs(i,j,k,m) 指的是在手里宝物数量为m，最大价值为k 的情况下，从（i，j） 出发到终点的可行方案数！
//当dfs的返回值为ll or int时，往往表示的是方案数，bool则表示当前方案可行与否！
ll dfs(int x,int y,int mx,int cnt)//这里dfs要设置4个参数，现在的位置（x，y），当前手中宝物的最大价值，当前手中宝物的数量
{
//如果已经到出口，直接返回
ll res=0;
if(x==n&&y==m) return (ll)(cnt==k);
for(int i=0;i<2;i++)//向两个方向行走,之后的所有点都在这个循环里面判断
{
int nx=x+dx[i];
int ny=y+dy[i];
if(!matrix(nx,ny)) continue;
//此时有两种情况，拿或者不拿
//if(c[nx][ny]>mx) res+=(dfs(nx,ny,c[nx][ny],cnt+1))%p;
if(c[nx][ny]>mx&&cnt<k) res=(res+dfs(nx,ny,c[nx][ny],cnt+1))%p;
//else res=(res+dfs(nx,ny,mx,cnt)) %p;
/*这里不能用else的原因：
走到(nx, ny)这个点时，有两种独立的选择—— 拿宝物（满足条件时）、不拿宝物。而else会把这两种选择变成互斥关系，完全违背了题意。
当c[nx][ny] > mx且cnt < k时，你既可以拿这个宝物（cnt+1，mx 更新），也可以不拿（cnt 不变，mx 不变）。
但如果用else，就会变成：“拿了就不能不拿，不拿才会走 else 分支”，直接丢失了 “能拿但选择不拿” 的合法方案，导致最终结果偏小。
简单说：拿和不拿是两个独立的选择，不是二选一，所以不能用 else，必须分别判断、累加两种选择的方案数。
*/
res=(res+dfs(nx,ny,mx,cnt)) %p;
}
return res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
c[i][j]++;//不加这一句会有部分案例错误，因为要处理宝物价值为0的情况
//或者不加这一句，将小明的手里的价值初始化为-1也行！
}
}
//在入口，小明也可以选择拿或者不拿宝物
cout<<(dfs(1,1,0,0)+dfs(1,1,c[1][1],1))%p<<'\n';
return 0;
}2.记忆化搜索版本：
#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;
const int N=55;
const ll p=1e9+7;
int c[N][N];//记录每个点的宝物价值
int n,m,k;//出口点（右下角）以及手里最大宝物数量
ll dp[N][N][14][14];//可见记忆化数组是和dfs一模一样的，参数设置都是一样的！
//刚刚误将N设置成了1e3,这样会：
//错误代码：N=1e3+9，即使dp是 int 类型，也会占用 1009*1009*14*14*4 ≈ 770MB，超出栈内存上限，程序直接崩溃。
//判断是否出界：
bool matrix(int x,int y)
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
int dx[]={1,0};
int dy[]={0,1};
//现在用记忆化数组：
//这里dfs(i,j,k,m) 指的是在手里宝物数量为m，最大价值为k 的情况下，从（i，j） 出发到终点的可行方案数！
//当dfs的返回值为ll or int时，往往表示的是方案数，bool则表示当前方案可行与否！
ll dfs(int x,int y,int mx,int cnt)//这里dfs要设置4个参数，现在的位置（x，y），当前手中宝物的最大价值，当前手中宝物的数量
{
//如果已经到出口，直接返回
ll res=0;
if(x==n&&y==m) return (ll)(cnt==k);
//如果已判断过:
if(dp[x][y][mx][cnt]!=-1) return dp[x][y][mx][cnt];
for(int i=0;i<2;i++)//向两个方向行走,之后的所有点都在这个循环里面判断
{
int nx=x+dx[i];
int ny=y+dy[i];
if(!matrix(nx,ny)) continue;
//此时有两种情况，拿或者不拿
//if(c[nx][ny]>mx) res+=(dfs(nx,ny,c[nx][ny],cnt+1))%p;
if(c[nx][ny]>mx&&cnt<k) res=(res+dfs(nx,ny,c[nx][ny],cnt+1))%p;
//else res=(res+dfs(nx,ny,mx,cnt)) %p;
/*这里不能用else的原因：
走到(nx, ny)这个点时，有两种独立的选择—— 拿宝物（满足条件时）、不拿宝物。而else会把这两种选择变成互斥关系，完全违背了题意。
当c[nx][ny] > mx且cnt < k时，你既可以拿这个宝物（cnt+1，mx 更新），也可以不拿（cnt 不变，mx 不变）。
但如果用else，就会变成：“拿了就不能不拿，不拿才会走 else 分支”，直接丢失了 “能拿但选择不拿” 的合法方案，导致最终结果偏小。
简单说：拿和不拿是两个独立的选择，不是二选一，所以不能用 else，必须分别判断、累加两种选择的方案数。
*/
res=(res+dfs(nx,ny,mx,cnt)) %p;
}
return dp[x][y][mx][cnt] = res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
c[i][j]++;//不加这一句会有部分案例错误，因为要处理宝物价值为0的情况
//或者不加这一句，将小明的手里的价值初始化为-1也行！
}
}
//在入口，小明也可以选择拿或者不拿宝物
cout<<(dfs(1,1,0,0)+dfs(1,1,c[1][1],1))%p<<'\n';
return 0;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
8
0- 0
已为社区贡献11条内容
所有评论(0)