力扣 329. 矩阵中的最长递增路径

题目链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
题目描述：

解题思路：

dfs+记忆化，对每个格子求它的最长递增路径，然后取最大值

代码如下

class Solution {
public:
    int dp[205][205];
    int n,m;
    int f[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
   int dfs(int x,int y,vector<vector<int>> &a){
       if(dp[x][y]!=-1) return dp[x][y];
       dp[x][y]++;
       for(int i=0;i<4;i++){
           int xx=x+f[i][0];
           int yy=y+f[i][1];
           if(xx<0||xx>=n||yy<0||yy>=m||a[x][y]>=a[xx][yy]) continue;
           //cout<<xx<<" "<<yy<<" "<<endl;
           dp[x][y]=max(dp[x][y],dfs(xx,yy,a)+1);
       }
       return dp[x][y];
   }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        n=matrix.size();
        m=matrix[0].size();
        memset(dp,-1,sizeof dp);
        int maxn=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
            //cout<<dp[i][j]<<endl;
              maxn=max(maxn,dfs(i,j,matrix));
            }
        }
        return maxn+1;
    }
};