329. 矩阵中的最长递增路径-蒲公英云

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

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
在这里插入图片描述
leetcode

记忆化dfs：

class Solution {
public:
    int dir[5] = {
    1, 0, -1, 0, 1}; 
    int row, col;
    int dfs(vector<vector<int>>& road, vector<vector<int>>& matrix, int i, int j){
        if(road[i][j]) return road[i][j];
        road[i][j]++; //没路走了
        for(int d = 0; d < 4; d++){
            int newi = i + dir[d];
            int newj = j + dir[d+1];
            if(newi >= 0 && newi < row && newj >= 0 && newj < col && matrix[i][j] < matrix[newi][newj]) road[i][j] = max(road[i][j], dfs(road, matrix, newi, newj) + 1);//有路则更新
        }
        return road[i][j];
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int longroad = 0;
        row = matrix.size();
        if(row == 0) return 0;
        col = matrix[0].size();
        vector<vector<int> > road(row, vector<int>(col, 0));
        for(int i = 0; i < row; i++) 
            for(int j = 0; j < col; j++)
                longroad = max(longroad, dfs(road, matrix, i, j));
        return longroad;
    }
};