leetcode-329. 矩阵中的最长递增路径

本文主要是介绍leetcode-329. 矩阵中的最长递增路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 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]。注意不允许在对角线方向上移动。

解题思路

【TLE未ac】对每个节点深搜，找出最长路径。在节点A最长路径上的节点BCD们，其最长路径一定比A的最长路径短，所以路径上的节点不会是其他最长路径的开头。

这种优化方式，只省掉了开头，实际上经过1条路径后，路径上的节点BCD的最长路径已经能求出来了，如果能用一个dict保存BCD的最长路径，则后续节点碰到BCD时也可以直接用了，这样可以更简单。但是用栈的方式无法做记忆化，用递归会方便一些。

官方代码太优雅了。。。学到了1个新招，可以在递归的函数前，加@lru_cache(None)装饰器，来加快速度。其中None参数是记忆化的大小，maxsize = None表示不做限制

代码

TLE的：

class Solution:def longestIncreasingPath(self, matrix: List[List[int]]) -> int:start_nodes = [(row, col) for row in range(len(matrix)) for col in range(len(matrix[0]))]max_len = 0while start_nodes:start_row, start_col = start_nodes.pop()stack = [(start_row, start_col, 1)]while stack:row, col, path = stack.pop()if (row, col) in start_nodes:start_nodes.remove((row, col))max_len = max(max_len, path)if row + 1 < len(matrix) and matrix[row + 1][col] > matrix[row][col]:stack.append((row + 1, col, path + 1))if 0 <= row - 1 and matrix[row - 1][col] > matrix[row][col]:stack.append((row - 1, col, path + 1))if col + 1 < len(matrix[0]) and matrix[row][col + 1] > matrix[row][col]:stack.append((row, col + 1, path + 1))if 0 <= col - 1 and matrix[row][col - 1] > matrix[row][col]:stack.append((row, col - 1, path + 1))return max_len

官方版：

class Solution:DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]def longestIncreasingPath(self, matrix: List[List[int]]) -> int:if not matrix:return 0@lru_cache(None)def dfs(row: int, column: int) -> int:best = 1for dx, dy in Solution.DIRS:newRow, newColumn = row + dx, column + dyif 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:best = max(best, dfs(newRow, newColumn) + 1)return bestans = 0rows, columns = len(matrix), len(matrix[0])for i in range(rows):for j in range(columns):ans = max(ans, dfs(i, j))return ans