211 - 329 矩阵中的最长递增路径
题目
解答
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:
return 0
M, N = len(matrix), len(matrix[0])
dp = [[0]*N for i in range(M)]
def dfs(i, j):
if not dp[i][j]:
val = matrix[i][j]
dp[i][j] = 1+max(
dfs(i-1, j) if i and val > matrix[i-1][j] else 0,
dfs(i+1, j)if i < M-1 and val > matrix[i+1][j] else 0,
dfs(i, j-1)if j and val > matrix[i][j-1] else 0,
dfs(i, j+1)if j < N-1 and val > matrix[i][j+1] else 0,
)
return dp[i][j]
return max(dfs(x, y) for x in range(M) for y in range(N))Last updated