题解 | 矩阵最长递增路径---leetcode329-dfs- 记忆化搜索

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        mx=0
        n=len(matrix)
        m=len(matrix[0])
        dirs=[[1,0],[-1,0],[0,1],[0,-1]]
        memo=[[0]*m  for i in range(n)]
        def dfs(matrix ,row ,col,memo):
            # 已经计算
            if memo[row][col]!=0:
                return memo[row][col]

            # 对当前的计数+1 
            memo[row][col]+=1
            for dir in dirs:
                new_row=row+dir[0]
                new_col=col+dir[1] 
                if 0<=new_row<n and 0<=new_col<m and matrix[row][col]<matrix[new_row][new_col]:
                    memo[row][col]=max(memo[row][col],dfs(matrix,new_row,new_col,memo)+1)

            return memo[row][col] 
        for i in range(n):
            for j in range(m):
                mx=max(mx,dfs(matrix,i,j,memo))
        return mx