题解 | 矩阵最长递增路径

1、解题思路

1. 记忆化搜索与动态规划：使用深度优先搜索（DFS）遍历每个单元格，并记录从该单元格出发的最长递增路径长度。为了避免重复计算，使用一个记忆化矩阵 dp 来存储已经计算过的单元格的最长路径长度。时间复杂度：O(nm)，每个单元格最多被处理一次。空间复杂度：O(nm)，用于存储 dp 矩阵。
2. 关键步骤：对于每个单元格，检查其四个邻接单元格是否满足递增条件。递归计算邻接单元格的最长递增路径，并更新当前单元格的最长路径。使用 dp 矩阵避免重复计算。

2、代码实现

C++

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

    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int n = matrix.size(), m = matrix[0].size();
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int max_len = 1;
        for (auto& dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j]) {
                max_len = max(max_len, 1 + dfs(matrix, dp, x, y));
            }
        }
        dp[i][j] = max_len;
        return max_len;
    }
};

Java

import java.util.*;


public class Solution {
    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m];
        int max_len = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                max_len = Math.max(max_len, dfs(matrix, dp, i, j));
            }
        }
        return max_len;
    }

    private int dfs(int[][] matrix, int[][] dp, int i, int j) {
        if (dp[i][j] != 0) return dp[i][j];
        int max_len = 1;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length &&
                    matrix[x][y] > matrix[i][j]) {
                max_len = Math.max(max_len, 1 + dfs(matrix, dp, x, y));
            }
        }
        dp[i][j] = max_len;
        return max_len;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        if not matrix or not matrix[0]:
            return 0
        n, m = len(matrix), len(matrix[0])
        dp = [[0] * m for _ in range(n)]
        max_len = 0
        for i in range(n):
            for j in range(m):
                max_len = max(max_len, self.dfs(matrix, dp, i, j))
        return max_len

    def dfs(self, matrix, dp, i, j):
        if dp[i][j] != 0:
            return dp[i][j]
        max_len = 1
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x, y = i + dx, j + dy
            if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] > matrix[i][j]:
                max_len = max(max_len, 1 + self.dfs(matrix, dp, x, y))
        dp[i][j] = max_len
        return max_len

3、复杂度分析

1. 记忆化搜索：dp[i][j] 存储从 (i, j) 出发的最长递增路径长度。如果 dp[i][j] 已经计算过，直接返回其值，避免重复计算。
2. 递归终止条件：所有邻接单元格的值都不大于当前单元格的值时，当前单元格的最长路径长度为 1。
3. 方向遍历：检查四个方向（上、下、左、右）的单元格是否满足递增条件。
4. 效率：时间复杂度：O(nm)，每个单元格最多被处理一次。空间复杂度：O(nm)，用于存储 dp 矩阵。
5. 适用性：适用于大规模矩阵（n, m ≤ 1000）。记忆化搜索确保了每个单元格只被计算一次，提高了效率。