链接：矩阵中的最长递增路径
深度优先搜索
对矩阵的每个元素调用dfs进行深度优先搜索，即可得到从该元素出发的最长递增路径，然后更新全局的最长路径，即可得到答案。
不过本题用朴素的dfs会超时，需要用记忆化搜索来优化，即在遍历的过程中添加一个记忆矩阵存储从每个位置出发的最长递增路径，之后的递归中如果再次访问这个位置，直接返回记忆矩阵中纯粹的路径长度。
PS：使用记忆矩阵有个条件需要满足，比如对A这个位置dfs得到的最大递增路径长度为a，对对应了一个路径P。之后搜索时，出现从B能走到A，则B一定不在A的最长路径对应的路径P中。抽象起来，就是任意两个位置之间是单向连接，比如A和B两个位置，就只能时B走向A，而不能A走向B。
PSS：这题如果把递增改成不递减，即允许值相等的两个相邻位置构成路径，则不能使用记忆化搜索，原因是值相等的两个相邻位置之间是双向连接。
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
max_length = 0
memory = [[0]*n for _ in range(m)]
dis = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(m):
for j in range(n):
length = self.dfs(matrix, i, j, dis, memory)
max_length = max(max_length, length)
return max_length
def dfs(self, matrix, i, j, dis, memory):
if memory[i][j] != 0:
return memory[i][j]
m = len(matrix)
n = len(matrix[0])
length = 1
for dx, dy in dis:
x = i+dx
y = j+dy
if 0<=x<m and 0<=y<n and matrix[i][j] < matrix[x][y]:
length = max(length, 1+self.dfs(matrix, x, y, dis, memory))
memory[i][j] = length
return length
