动态规划：记忆化搜索

记忆化搜索和递推都是为了解决子问题重复计算而产生的

虽然动态规划的转移图是一个DAG，但是一个状态可以被其他的状态复用多次

因此为了提高动态规划的效率，记忆化搜索便产生了

但是有时候，状态转移图是不容易描述的，这个时候我们就不能再称记忆化搜索是动态规划的一种实现了

它纯粹就是为了不再重复计算而已

比如滑雪这道题（如果想看动态规划的例子，强烈建议看区间动规的记忆化实现，很自然）

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxr=105; 5 const int maxc=105; 6 int r,c,ans; 7 int dx[5]={0,1,-1,0,0}; 8 int dy[5]={0,0,0,1,-1}; 9 int a[maxr][maxc],f[maxr][maxc];10 bool check(int x,int y,int nx,int ny)11 {12if(nx<1||nx>r||ny<1||ny>c) return 0;13if(a[x][y]>a[nx][ny]) return 1;14return 0;15 }16 int dfs(int x,int y)17 {18if(f[x][y]!=1) return f[x][y];19int ret=1;20for(int i=1;i<=4;i++)21{22 int nx=x+dx[i];23 int ny=y+dy[i];24 if(check(x,y,nx,ny))25 ret=max(ret,dfs(nx,ny)+1);26}27f[x][y]=ret;28return ret;29 }30 void init()31 {32for(int i=0;i<105;i++)33 for(int j=0;j<105;j++)34 f[i][j]=1;35 }36 int main()37 {38init();39scanf("%d%d",&r,&c);40for(int i=1;i<=r;i++)41 for(int j=1;j<=c;j++)42 scanf("%d",&a[i][j]);43for(int i=1;i<=r;i++)44 for(int j=1;j<=c;j++)45 {46 ans=max(ans,dfs(i,j));47 }48printf("%d",ans);49 }