标签: 深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 数组 动态规划 矩阵
难度: Hard
给定一个 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.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1运行时间: 109 ms
内存: 17.2 MB
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
Maxnum = 0
stores = [ [None]*n for i in range(m)]
def search_self(x,y):
nonlocal Maxnum
compares = []
if x != 0 and matrix[x-1][y] < matrix[x][y]:
compares.append(stores[x-1][y]) if stores[x-1][y] else compares.append(search_self(x-1,y))
if y != 0 and matrix[x][y-1] < matrix[x][y] :
compares.append(stores[x][y-1]) if stores[x][y-1] else compares.append(search_self(x,y-1))
if x != m - 1 and matrix[x+1][y] < matrix[x][y]:
compares.append(stores[x+1][y]) if stores[x+1][y] else compares.append(search_self(x+1,y))
if y != n - 1 and matrix[x][y+1] < matrix[x][y]:
compares.append(stores[x][y+1]) if stores[x][y+1] else compares.append(search_self(x,y+1))
stores[x][y] = max(compares) + 1 if compares else 1
Maxnum = max(stores[x][y],Maxnum)
return stores[x][y]
for i in range(m):
for j in range(n):
if not stores[i][j]:
search_self(i,j)
return Maxnum
这个题解采用深度优先搜索(DFS)的方式，对矩阵中的每个元素进行搜索。对于每个元素，分别向上、下、左、右四个方向搜索比当前元素值小的相邻元素，找出以当前元素为起点的最长递增路径。在搜索过程中，使用记忆化的方式存储已计算过的元素的最长递增路径长度，避免重复计算。最后，取所有元素的最长递增路径长度的最大值作为整个矩阵的最长递增路径长度。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
Maxnum = 0
stores = [ [None]*n for i in range(m)] # 记忆化数组，存储每个元素的最长递增路径长度
def search_self(x,y):
nonlocal Maxnum
compares = []
# 向上搜索
if x != 0 and matrix[x-1][y] < matrix[x][y]:
compares.append(stores[x-1][y]) if stores[x-1][y] else compares.append(search_self(x-1,y))
# 向左搜索
if y != 0 and matrix[x][y-1] < matrix[x][y] :
compares.append(stores[x][y-1]) if stores[x][y-1] else compares.append(search_self(x,y-1))
# 向下搜索
if x != m - 1 and matrix[x+1][y] < matrix[x][y]:
compares.append(stores[x+1][y]) if stores[x+1][y] else compares.append(search_self(x+1,y))
# 向右搜索
if y != n - 1 and matrix[x][y+1] < matrix[x][y]:
compares.append(stores[x][y+1]) if stores[x][y+1] else compares.append(search_self(x,y+1))
stores[x][y] = max(compares) + 1 if compares else 1 # 更新当前元素的最长递增路径长度
Maxnum = max(stores[x][y],Maxnum) # 更新整个矩阵的最长递增路径长度
return stores[x][y]
for i in range(m):
for j in range(n):
if not stores[i][j]: # 如果当前元素的最长递增路径长度还没有计算过，则进行搜索
search_self(i,j)
return Maxnum
在解决矩阵中的最长递增路径问题时，DFS是一个理想的选择，因为它能够深入探索可能的递增序列，直到这一路径达到终点。DFS允许我们从一个节点开始，深入探索其所有可能的递增路径，直到无法继续为止，然后回溯到前一个节点，探索另一条可能的路径。这种深度探索非常适合此类问题，因为我们需要找到最长的递增路径。相比之下，BFS从每个节点开始广泛搜索所有邻居，这在寻找最短路径问题中更常用，但对于寻找单个最长路径的问题，它不如DFS有效率，因为它需要更多的资源来同时跟踪所有在同一层的路径。此外，DFS与记忆化结合使用时，可以显著减少重复计算，使算法更加高效。
题解中实现了记忆化来防止对同一路径的重复计算。记忆化是通过使用一个二维数组 'stores' 实现的，该数组与输入矩阵同维度。每个元素 'stores[i][j]' 存储从矩阵位置 (i, j) 开始的最长递增路径长度。在DFS过程中，每次访问一个元素时，首先检查 'stores' 数组中相应位置是否已经有值。如果已经计算过（即 'stores[i][j]' 不为空），则直接使用该值，而无需重新计算。这样，每个元素的最长递增路径长度只被计算一次，大大减少了不必要的计算量，提高了效率。
记忆化数组 'stores' 的作用是存储每个矩阵元素为起点的最长递增路径的长度。这样，在DFS过程中，当我们尝试计算一个元素的最长递增路径时，首先会检查 'stores' 数组。如果该位置已经有值，直接使用这个值而不再进行进一步的DFS搜索，这就避免了重复计算相同的路径长度。通过这种方式，'stores' 数组减少了计算量，因为它确保每个元素的路径长度只计算一次，无论这个元素在DFS过程中被访问多少次。这种方法不仅提高了效率，还能减少递归调用的栈空间使用，从而减少内存消耗。