题目

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：
[困难] 329. 矩阵中的最长递增路径 - 图1

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：
[困难] 329. 矩阵中的最长递增路径 - 图2

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

输入：matrix = [[1]]
输出：1

解答 & 代码

解法 0：朴素的递归回溯（超时）

class Solution {
private:
    int backTrace(vector<vector<int>>& matrix, vector<vector<bool>>& used, int row, int col, int pre)
    {
        int rows = matrix.size();
        int cols = matrix[0].size();
        if(row < 0 || row >= rows || col < 0 || col >= cols || matrix[row][col] <= pre)
            return 0;

        used[row][col] = true;
        int up = backTrace(matrix, used, row - 1, col, matrix[row][col]);
        int down = backTrace(matrix, used, row + 1, col, matrix[row][col]);
        int left = backTrace(matrix, used, row, col - 1, matrix[row][col]);
        int right = backTrace(matrix, used, row, col + 1, matrix[row][col]);
        used[row][col] = false;
        return 1 + max(max(up, down), max(left, right));
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<bool>> used(rows, vector<bool>(cols, false));
        int maxLen = 0;
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int len = backTrace(matrix, used, i, j, -1);
                maxLen = max(len, maxLen);
            }
        }
        return maxLen;
    }
};

解法 1：记忆化 DFS

使用朴素的递归回溯（DFS），同一个格子会被多次访问，每次访问都要重新计算从该格子出发的最长递增路径的长度，因此会超时。
而实际上从每个格子出发的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法，额外使用 **memo** 来缓存结果，memo[i][j] 代表从第 i 行第 j 列的格子出发的最长递增路径的长度。递归过程中，如果 memo[i][j] != 0，则说明之前已访问过这一格，并计算过，因此直接返回 memo[i][j] 即可，否则递归计算从第 i 行第 j 列的格子出发的最长递增路径的长度，并保存到 memo[i][j]。

class Solution {
private:
    int backTrace(vector<vector<int>>& matrix, vector<vector<int>>& memo, int row, int col, int pre)
    {
        int rows = matrix.size();
        int cols = matrix[0].size();
        // 递归结束条件：如果越界 or 非递增，则直接返回长度 0
        if(row < 0 || row >= rows || col < 0 || col >= cols || matrix[row][col] <= pre)
            return 0;
        // 如果 memo 中已经存储了第 row 行第 col 列的结果，直接返回
        if(memo[row][col] != 0)
            return memo[row][col];

        // 递归求上、下、左、右四个方向的最长递增路径的长度，取最大值 + 1（当前格子）
        int up = backTrace(matrix, memo, row - 1, col, matrix[row][col]);
        int down = backTrace(matrix, memo, row + 1, col, matrix[row][col]);
        int left = backTrace(matrix, memo, row, col - 1, matrix[row][col]);
        int right = backTrace(matrix, memo, row, col + 1, matrix[row][col]);
        memo[row][col] = 1 + max(max(up, down), max(left, right));    // 存储到 memo
        return memo[row][col];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> memo(rows, vector<int>(cols, 0));
        int maxLen = 0;
        // 计算从矩阵每个位置出发的最长递增路径长度，取最大值
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int len = backTrace(matrix, memo, i, j, -1);
                maxLen = max(len, maxLen);
            }
        }
        return maxLen;
    }
};

复杂度分析：设矩阵 m 行 n 列

时间复杂度 O(mn)：
空间复杂度 O(mn)：

执行结果：

执行结果：通过

执行用时：40 ms, 在所有 C++ 提交中击败了 73.79% 的用户
内存消耗：15.7 MB, 在所有 C++ 提交中击败了 47.13% 的用户