记忆化搜索

1、思路

2、代码模板：

#include<iostream>
#include<cstring>

using namespace std;

const int N=310;

int n,m;
int h[N][N];
int f[N][N];

int dx[4]={-1,0,1,0};//上下左右移动
int dy[4]={0,1,0,-1};

int dp(int x,int y)//求以(x,y)为起点的状态
{
    int &v=f[x][y];//这句让v等价于f[x][y]
    if(v!=-1)      //当v已经被遍历过了，重复是因为后面有递归上下左右可能走到走过的点，直接返回
        return v;
    v=1;//刚开始为1，即起点
    for(int i=0;i<4;i++)//上下左右移动
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])//如果在边界内且下一点高度小于这点的高度
            v=max(v,dp(a,b)+1);//dp(a,b)移动过去求出来最大值
    }
    return v;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&h[i][j]);//输入每块区域的高度
    memset(f,-1,sizeof f);//-1代表没有走过
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)//遍历所有以(i,j)为起点的状态，记录其中的最大值
            res=max(res,dp(i,j));
    printf("%d",res);
    return 0;
}