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

from functools import cache
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#

class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        n, m = len(matrix), len(matrix[0])
        ans = 0
        @cache
        def dfs(x: int, y: int) -> int:
            res = 1
            for a, b in [(x, y - 1), (x + 1, y), (x, y + 1), (x - 1, y)]:
                if 0 <= a < n and 0 <= b < m and matrix[x][y] < matrix[a][b]:
                    res = max(res, dfs(a, b) + 1)
            return res
        
        for i in range(n):
            for j in range(m):
                ans = max(ans, dfs(i, j))
        return ans