题目描述： 给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
输入: nums = [ [9,9,4], [6,6,8], [2,1,1] ] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。 示例 2:
输入: nums = [ [3,4,5], [3,2,6], [2,2,1] ] 输出: 4 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
此题可以通过深度优先搜索和记忆矩阵解答。记忆矩阵记录每个已经走过的点的最长递增路径，避免大量的重复计算。
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: # 矩阵无元素 if not matrix or not matrix[0]: return 0 row, col = len(matrix), len(matrix[0]) # 记忆矩阵 cache = [[-1 for _ in range(col)] for _ in range(row)] result = 0 for i in range(row): for j in range(col): clen = self.dfs(i, j, matrix, cache, col, row) result = max(result, clen) return result def dfs(self, i, j, matrix, cache, col, row): if cache[i][j] != -1: return cache[i][j] result = 1 direction = [[0, 1], [0, -1], [1, 0], [-1, 0]] for dire in direction: x, y = i + dire[0], j + dire[1] if x<0 or y<0 or x>row-1 or y>col-1 or matrix[x][y]<=matrix[i][j]: continue length = 1 + self.dfs(x, y, matrix, cache, col, row) result = max(length, result) cache[i][j] = result return result