本文主要是介绍POJ-1088-动规-DFS+记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*转载请注明出处：乄心-小黄豆http://blog.csdn.net/wuxinxiaohuangdou*/
中文的就不解释了！
简单的DFS+记忆搜索！
/*336K 79MS AC*/
#include<iostream>
using namespace std;
#define MAX 105
int R,C;
int max_len[MAX][MAX];
int fina_max_len=0;
int len;
int temp_max_len;
int map[MAX][MAX];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int cur_i,int cur_j)
{if(max_len[cur_i][cur_j]>0) /*记忆化搜索-大大减少时间！*/{len+=max_len[cur_i][cur_j];}else{for(int i=0;i<4;i++){if(map[cur_i+dir[i][0]][cur_j+dir[i][1]]<map[cur_i][cur_j]&&map[cur_i+dir[i][0]][cur_j+dir[i][1]]!=-1){int pre_len;//这个变量作用是看是不是通过记忆化搜索直接得到的值。len++;//满足条件就步数加1.pre_len=len-1;dfs(cur_i+dir[i][0],cur_j+dir[i][1]);if(len>temp_max_len)temp_max_len=len;if(len-pre_len!=1) //说明是通过记忆化搜索得到的，所以dfs回溯的时候要多减去这个得到的长度！len-=max_len[cur_i+dir[i][0]][cur_j+dir[i][1]];len--; //回溯一次就步数减一步。}}}
}
int main()
{cin>>R>>C;memset(map,-1,sizeof(map));memset(max_len,0,sizeof(max_len));int i,j;for( i=1;i<=R;i++)for( j=1;j<=C;j++){cin>>map[i][j];}for(i=1;i<=R;i++)for( j=1;j<=C;j++){temp_max_len=0;len=0;dfs(i,j);max_len[i][j]=temp_max_len; //记忆化存储，以后再到这里不用再计算直接拿值就好了！//cout<<"temp_max_len="<<temp_max_len<<endl;if(temp_max_len>fina_max_len)fina_max_len=temp_max_len;}cout<<fina_max_len+1<<endl; //因为长度是从0开始的初值，最后答案要加1.只能加在这里！return 0;
}
这篇关于POJ-1088-动规-DFS+记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
