动态规划：记忆化搜索

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

虽然动态规划的转移图是一个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 {
12     if(nx<1||nx>r||ny<1||ny>c) return 0;
13     if(a[x][y]>a[nx][ny]) return 1;
14     return 0;
15 }
16 int dfs(int x,int y)
17 {
18     if(f[x][y]!=1) return f[x][y];
19     int ret=1;
20     for(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     }
27     f[x][y]=ret;
28     return ret;
29 }
30 void init()
31 {
32     for(int i=0;i<105;i++)
33         for(int j=0;j<105;j++)
34             f[i][j]=1;
35 }
36 int main()
37 {
38     init();
39     scanf("%d%d",&r,&c);
40     for(int i=1;i<=r;i++)
41         for(int j=1;j<=c;j++)
42             scanf("%d",&a[i][j]);
43     for(int i=1;i<=r;i++)
44         for(int j=1;j<=c;j++)
45         {
46             ans=max(ans,dfs(i,j));
47         }
48     printf("%d",ans);
49 }