大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
概述
记忆化搜索算法事实上是一种对递归算法的优化
因为在递归算法中有很多重复计算，导致了非常离谱的时间和空间复杂度
所以我们采用记住计算结果的方式，能很大程度上减少复杂度
算法核心结构
此算法可以被抽象成为以下的结构：
f（problem p）{
if(p has been solved){
return the result
}else{
divide the p into some sub-problems (p1, p2, p3...)
f(p1);
f(p2);
f(p3);
...
}
例题1 AcWing 901. 滑雪
十分典型的记忆化搜索题目，主要体现在if(f[x][y]!=-1) return f[x][y];上。
#include<iostream>
#include<cstring>
using namespace std;
const int N=304;
int r,c;
int f[N][N];
int g[N][N];
int dx[]={
0,-1,0,1},dy[]={
-1,0,1,0};
int dp(int x,int y)
{
if(f[x][y]!=-1) return f[x][y];
f[x][y]=1;
for(int i=0;i<4;i++)
{
int xi=x+dx[i],yi=y+dy[i];
if(xi>=1&&xi<=r&&yi>=1&&yi<=c&&g[xi][yi]<g[x][y])
f[x][y]=max(f[x][y],dp(xi,yi)+1);
}
return f[x][y];
}
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>g[i][j];
memset(f,-1,sizeof(f));
int res=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
res=max(res,dp(i,j));
cout<<res;
return 0;
}
例题2 AcWing 2067. 走方格
第十一届蓝桥杯省赛原题，除了记忆化搜索方法，还有正常dp方法可供选择。
#include<iostream>
using namespace std;
const int N=32;
int n,m;
int f[N][N];
int dfs(int x,int y)
{
if(x&1||y&1)
{
if(f[x][y]) return f[x][y];
if(x<n) f[x][y]+=dfs(x+1,y);
if(y<m) f[x][y]+=dfs(x,y+1);
}
return f[x][y];
}
int main()
{
cin>>n>>m;
f[n][m] = n & 1 || m & 1;//判断nm是否同为偶数
cout<<dfs(1,1);
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/164443.html原文链接：https://javaforall.net
