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

- 日理万妓 2023-03-01 12:58 15阅读 0赞

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

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]  
[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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20230208/b8356479b9684237b943ae87aa4d44ec.png
[leetcode]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/