题意:找出最长的递增道路,可以上下左右四个方向走
DP方程:step[ i ][ j ] = max{ step[ i-1][ j ], step[ i ][ j-1], step[ i+1][ j ], step[ i ][ j+1] };
借鉴各类大牛的代码,终于写出来了第一道记忆化搜索
#include<stdio.h>
//全局变量自动赋0
int mp[101][101];//记录原始数据
int step[101][101];//记录每个地方的最大滑雪步数
int N,M;
int DP(int row,int column)//行列不要用x,y
{
int max=0;
if(step[row][column]>0) return step[row][column];//已经遍历过了 就不要在进行了
//找上下左右四个方向中step最大的然后加到该位置中
//上
if (row-1>=0 && mp[row-1][column]<mp[row][column])
{
if(max<DP(row-1,column))
max=DP(row-1,column);
}
//下
if(row+1<N && mp[row+1][column]<mp[row][column])
{
if(max<DP(row+1,column))
max=DP(row+1,column);
}
//左
if(column-1>=0 && mp[row][column-1]<mp[row][column])
{
if(max<DP(row,column-1))
max=DP(row,column-1);
}
//右
if(column+1<M && mp[row][column+1]<mp[row][column])
{
if(max<DP(row,column+1))
max=DP(row,column+1);
}
max++;//算上自己本身那一步
//return的东西非常重要;
//1-2-3-4这四个点从4开始
//找的话会把1,2,3都记录了
return step[row][column]=max;
}
int main()
{
int i,j;
scanf("%d%d",&N,&M);
for (i=0;i<N;i++)
for(j=0;j<M;j++)
{
scanf("%d",&mp[i][j]);
step[i][j]=0;
}
for (i=0;i<N;i++)
for (j=0;j<M;j++)
DP(i,j);
//step[i][j]=DP(i,j)这样会超时
//如果从4开始找就只会把4的结果记录
//1,2,3没有记录
int max=0;
for (i=0;i<N;i++)
for (j=0;j<M;j++)
if(max<step[i][j]) max=step[i][j];
printf("%d\n",max);
return 0;
}