题解 | #矩阵最长递增路径#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int dfs(vector<vector<int> >& matrix,vector<vector<int>>&dp,int i,int j){
        if(dp[i][j]!=0)return dp[i][j];
        dp[i][j]++;
        for(int k=0;k<4;k++){
            int nexti=i+dirs[k][0];
            int nextj=j+dirs[k][1];
            if(nexti>=0&&nexti<matrix.size()&&nextj>=0&&nextj<matrix[0].size()&&matrix[nexti][nextj]>matrix[i][j]){
                dp[i][j]=max(dp[i][j],dfs(matrix,dp,nexti,nextj)+1);
            }
        }
        return dp[i][j];
        
    }



    int solve(vector<vector<int> >& matrix) {
        // write code here
        vector<vector<int>>dp(matrix.size(),vector<int>(matrix[0].size(),0));
        int res=0;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                res=max(res,dfs(matrix,dp,i,j));
            }
        }
        return res;
    }
};

写一个深度搜索

如果dp[i][j]有值，说明之前已经遍历过了

如果妹纸，先给自己加个1

然后从四个方向遍历，找最长的递增序列，本质还是递归