329. Longest Increasing Path in a Matrix
九章算法班里讲过的一道题，用记忆化搜索。
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix:
return 0
# write your code here
A = matrix
max_length = 0
dp = [[0 for _ in range(len(A[0]))] for _ in range(len(A))]
visited = [[False for _ in range(len(A[0]))] for _ in range(len(A))]
for i in range(len(A)):
for j in range(len(A[0])):
max_length = max(max_length, self.dfs(dp, visited, A, i, j))
return max_length
def dfs(self, dp, visited, A, i, j):
if visited[i][j]:
return dp[i][j] # starting from i,j the longest subsequence
length = 1
for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
if 0 <= x < len(A) and 0 <= y < len(A[0]) and A[x][y] < A[i][j]:
length = max(length, self.dfs(dp, visited, A, x, y) + 1)
dp[i][j] = length
visited[i][j] = True
return length
