记忆化搜索的经典例题
一个显然的想法，直接枚举每一个点作为起点然后dfs，求出最大值。显然这种做法一定会TLE，我们不妨进行一下优化：由于每一个点会被重复搜索，我们不妨进行记忆化，当这一个点搜索完成后，我们记下从这个点出发的最优解。下次搜索到这个点时我们就可以O(1)返回答案，这样搜索效率大大提高，减少了很多无用的搜索，我们的算法就可以AC了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 int map[110][110],f[110][110],n,m; 7 int dx[5]={0,0,1,-1}; 8 int dy[5]={1,-1,0,0}; 9 int dfs(int x,int y) { 10 if(f[x][y]!=-1) return f[x][y]; 11 f[x][y]=0; 12 int sum=0; 13 for(int i=0;i<5;i++) { 14 int xx=x+dx[i]; 15 int yy=y+dy[i]; 16 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[x][y]>map[xx][yy]) { 17 sum=max(sum,dfs(xx,yy)); 18 } 19 } 20 return f[x][y]=sum+1; 21 } 22 int main() { 23 cin>>n>>m; 24 for(int i=1;i<=n;i++) 25 for(int j=1;j<=m;j++) 26 cin>>map[i][j]; 27 memset(f,-1,sizeof(f)); 28 int ans=0; 29 for(int i=1;i<=n;i++) 30 for(int j=1;j<=n;j++) { 31 int x=dfs(i,j); 32 ans=max(ans,x); 33 } 34 cout<<ans<<endl; 35 return 0; 36 }