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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # I = [[0]*len(matrix[0]) for i in range(len(matrix))]
        import functools
        @functools.cache
        def dfs(i, j):
            v0 = dfs(i-1, j) + 1 if i-1>=0 and matrix[i-1][j]>matrix[i][j] else 1
            v1 = dfs(i, j-1) + 1 if j-1>=0 and matrix[i][j-1]>matrix[i][j] else 1
            v2 = dfs(i+1, j) + 1 if i+1<len(matrix) and matrix[i+1][j]>matrix[i][j] else 1
            v3 = dfs(i, j+1) + 1 if j+1<len(matrix[0]) and matrix[i][j+1]>matrix[i][j] else 1
            return max(v0, v1, v2, v3)

        m = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                m = max(m, dfs(i, j))

        return m
        # write code here