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

记忆化搜索，根据题意可利用 dfs 进行求解,因为路径是递增的,已走过的路径可缓存,利用 递归 + 备忘录的方式求解

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