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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @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
        m,n = len(matrix),len(matrix[0])
        mark = [[0 for j in range(n)]  for i in range(m)]
        res = 0
        pre = -1
        for i in range(m):
            for j in range(n):
                res = max(self.dfs(matrix,i,j,pre,mark),res)
        return res
    
    def dfs(self,matrix,i,j,pre,mark):
        if i<0 or i>=len(matrix) or j<0 or j>=len(matrix[0]) or pre>=matrix[i][j]:
            return 0
        if mark[i][j]:
            return mark[i][j]
        res = 1 + max(self.dfs(matrix, i-1, j, matrix[i][j], mark),
                     self.dfs(matrix, i+1, j, matrix[i][j], mark),
                     self.dfs(matrix, i, j-1, matrix[i][j], mark),
                     self.dfs(matrix, i, j+1, matrix[i][j], mark))
        mark[i][j] = res
        return res