记忆化搜索

记忆化数组

核心思想：设置一个记忆化数组f[N][N]，保存每种情况的（最优）解
并且如果这个点 f[i][j] 已经计算过了，直接返回即可，这就是记忆化搜索

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m,g[N][N]; //数组g存储每个点高度
int f[N][N]; //记忆化数组，保存每个(i,j)为起点的最优解
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

//以i，j为起点的滑雪长度
int dp(int i,int j){
    // 如果这个点已经计算过了，直接返回即可，这就是记忆化搜索
    if(f[i][j] != -1) return f[i][j]; 
    f[i][j] = 1; //长度最短至少为1
    for(int a=0;a<4;a++){
        int x = i + dx[a]; int y = j + dy[a];
        if(x>=1 && x<=n && y>=1 && y<= m && g[i][j] > g[x][y]){
            f[i][j] = max(f[i][j],dp(x,y)+1); //(i,j) 为当前位置，(x,y)为下一个要访问的位置
        }  
    }
    return f[i][j];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> g[i][j];
        }
    }
    memset(f,-1,sizeof(f));
    int res = 1;
    //循环枚举起始位置(i,j)的所有可能，找出最大值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            res = max(res,dp(i,j)); //dp(x,y)返回以位置(i,j)为起点能延申的最长长度
        }
    }
    cout << res;
    return 0;
}