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

class Solution:
    # 记录四个方向
    dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def dfs(self, matrix: List[List[int]], dp: List[List[int]], i: int, j: int) -> int:
        if dp[i][j] != 0:
            return dp[i][j]

        # 初始化dp[i][j]为1，表示当前单元格自身是一个长度为1的路径
        dp[i][j] = 1

        for dx, dy in self.dirs:
            nexti, nextj = i + dx, j + dy
            # 判断条件：确保下一个单元格在矩阵范围内且值大于当前单元格
            if (
                0 <= nexti < len(matrix)
                and 0 <= nextj < len(matrix[0])
                and matrix[nexti][nextj] > matrix[i][j]
            ):
                # 递归调用dfs，并更新dp[i][j]为最大路径长度
                dp[i][j] = max(dp[i][j], self.dfs(matrix, dp, nexti, nextj) + 1)

        return dp[i][j]

    def solve(self, matrix: List[List[int]]) -> int:
        # 矩阵不为空
        if not matrix or not matrix[0]:
            return 0

        n, m = len(matrix), len(matrix[0])
        # i，j处的单元格拥有的最长递增路径
        dp = [[0] * m for _ in range(n)]
        res = 0

        for i in range(n):
            for j in range(m):
                # 更新最大值
                res = max(res, self.dfs(matrix, dp, i, j))

        return res