题意

• 在n*m的地图中，每个点有权值，并且在任一点都可以向四周比自己权值小的点走动，求最多走动多少步

思路

• 对于走动最长路径的最后一个点，他一定是由上下左右中比他小且已走路径最长的点走来，对于倒数第二个点同理，故需要维护每个点可以走的最长路径，记dp[i][j]为从(i,j)开始走的最长路径，dp[i][j]=max(上下左右权值比他小的值的最长路径+1)
• 需要注意的是，维护状态转移方程的同时，需要先将每个走到的点最短路径初始化为1，即至少可以走自己这一步，以保证使用记忆化搜索时，走到权值最小的点也能正确维护
• 本题如果使用递推的话，总需要从地图中权值最小的点开始按升序维护，等价于，可能会超时

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N=120;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int mp[N][N];
int dp[N][N];
int n,m;
int deal (int x,int y){
    if(x<1||y<1||x>n||y>m)return 0;
    if(dp[x][y]!=0)return dp[x][y];
    dp[x][y]=1;
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(mp[tx][ty]<mp[x][y]) dp[x][y]=max(deal(tx,ty)+1,dp[x][y]);   
    }
    return dp[x][y];
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> mp[i][j];            
        }
    }    
    int ans=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max( ans , deal(i,j) );
        }
    }
    cout << ans <<endl;
    return 0;
}