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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here

        s = [[-1, 0], [1, 0], [0, -1], [0, 1]]

        def dfs(path, nums, i, j):
            if path[i][j] != 0:
                return path[i][j]
            
            path[i][j] += 1
            for k in range(4):
                nextI = i + s[k][0]
                nextJ = j + s[k][1]

                if nextI >= 0 and nextI < len(nums) and nextJ >=0 and nextJ < len(nums[0]) and nums[nextI][nextJ] > nums[i][j]:
                    path[i][j] = max(path[i][j], dfs(path, nums, nextI, nextJ) + 1)

            return path[i][j]

        path = [[0 for i in range(len(matrix[0]))] for i in range(len(matrix))]
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                res = max(res, dfs(path, matrix, i, j)) # 每个点出发的最长路径

        return res