# 剑指 Offer II 112. 最长递增路径#

• 标签：深度优先搜索、广度优先搜索、图、拓扑排序、记忆化搜索、动态规划
• 难度：困难

## 代码 #

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  class Solution: max_len = 0 directions = {(1, 0), (-1, 0), (0, 1), (0, -1)} def longestIncreasingPath(self, matrix: List[List[int]]) -> int: if not matrix: return 0 rows, cols = len(matrix), len(matrix[0]) record = [[0 for _ in range(cols)] for _ in range(rows)] def dfs(i, j): record[i][j] = 1 for direction in self.directions: new_i, new_j = i + direction[0], j + direction[1] if 0 <= new_i < rows and 0 <= new_j < cols and matrix[new_i][new_j] > matrix[i][j]: if record[new_i][new_j] == 0: dfs(new_i, new_j) record[i][j] = max(record[i][j], record[new_i][new_j] + 1) self.max_len = max(self.max_len, record[i][j]) for i in range(rows): for j in range(cols): if record[i][j] == 0: dfs(i, j) return self.max_len