大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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);
}