329. 矩阵中的最长递增路径
给定一个
m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4 解释：最长递增路径为[1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]] 输出：4 解释：最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]] 输出：1
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231- 1
法1 DFS 记忆化搜索
思路
这道题 可以 建立起 递归、记忆化搜索、动态规划三者的联系。
本题递归的计算每个位置为起点的最长递增路径，然后由于grid[i][j]为起点的最长递增路径之和 其上下左右四个位置的最长递增路径有关系，因此可以记忆化。大问题之和小问题有关系，这就有了动态规划的味道。
因为不知道起点，所以挨个遍历过去。
因为递增序列都是挨着的，所以计算的时候，如果邻居节点已经计算好了，可以直接+1
题解
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: count = [[0] * len(matrix[0]) for _ in range(len(matrix))] res = 1 for i in range(0, len(matrix)): for j in range(0, len(matrix[0])): res = max(res, self.dfs(i, j, matrix, count, -1)) # print(count) return res def dfs(self, row: int, col: int, grid: List[List[int]], count:List[List[int]], prev:int): if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]): return 0 if grid[row][col] <= prev: return 0 if count[row][col] != 0: return count[row][col] res = 1 for d in [[-1, 0], [0, -1], [1, 0], [0, 1]]: res = max(res, 1+self.dfs(row+d[0], col+d[1], grid, count, grid[row][col])) count[row][col] = res return res
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: self.res = 1 self.matrix = matrix # 默认值设置为 0 ,表示还未遍历过该节点 self.longest_path = [[0] * len(matrix[0]) for _ in matrix] self.dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]] for i in range(0, len(matrix)): for j in range(0, len(matrix[0])): # 以 (i, j) 为起点 的最长路径 if self.longest_path[i][j] == 0: self.longest_path[i][j] = self.dfs(i, j) return self.res def dfs(self, r, c): # 返回 已 r, c 为起点的最长递增路径 for dir_ in self.dirs: x, y = r + dir_[0], c + dir_[1] if (len(self.matrix) > x >= 0 and len(self.matrix[0]) > y >= 0 and self.matrix[x][y] > self.matrix[r][c]): # 计算该邻居节点 if self.longest_path[x][y] == 0: self.longest_path[x][y] = max(self.dfs(x, y), 1) # 更新当前节点 self.longest_path[r][c] = max(self.longest_path[x][y] + 1, self.longest_path[r][c]) # 更新结果 self.res = max(self.res, self.longest_path[r][c]) return self.longest_path[r][c]
另外一个版本
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: distance = [[float("inf")] * len(matrix[0]) for _ in matrix] res = 1 for i in range(0, len(matrix)): for j in range(0, len(matrix[0])): temp = self.dfs(i, j, -float("inf"), matrix, distance) res = max(res, temp) return res def dfs(self, raw, col, prev_val, matrix, distance): if raw < 0 or col < 0 or raw >= len(distance) or col >= len(distance[0]): return 0 if prev_val >= matrix[raw][col]: return 0 if distance[raw][col] != float("inf"): return distance[raw][col] temp = 0 for d in ((-1, 0), (1, 0), (0, -1), (0,1)): temp = max(temp, self.dfs(raw+d[0], col+d[1], matrix[raw][col], matrix, distance)) distance[raw][col] = temp + 1 return distance[raw][col]
class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: arr = [[0] * len(matrix[0]) for _ in matrix] dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]] res = 0 for i in range(0, len(matrix)): for j in range(0, len(matrix[0])): if arr[i][j] > 0: continue temp = self.dfs(raw=i, col=j, arr=arr, matrix=matrix, dirs=dirs) res = max(res, temp) return res def dfs(self, raw, col, arr, matrix, dirs): # 如果之前遍历过, if arr[raw][col] > 0: return arr[raw][col] arr[raw][col] = 1 temp = 0 for d in dirs: x, y = d[0] + raw, d[1] + col if len(matrix) > x >= 0 and len(matrix[0]) > y >= 0: if matrix[x][y] > matrix[raw][col]: temp = max(temp, self.dfs(x, y, arr, matrix, dirs)) arr[raw][col] += temp return arr[raw][col]