问题描述
https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 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]。注意不允许在对角线方向上移动。
思路
我们可以对每一个点求出最长递增路径的长度，这样当相邻的点比该点小的时候，我们将该点的最长递增路径的长度加1，就是这个相邻点的最长递增路径的可能值。
这里面一定不会有重复访问的现象，因为是最长递增路径，不存在相同的值，我们可以放心的使用其他点已经求出的最长递增路径。
那么这个函数的参数也就出来了，dfs(i, j)。i，j表示是哪个点，函数求出的结果是这点为起始的最长递增路径长度。这个函数怎么求呢？首先自身就是一条路径，也就是最少是1。然后我们往四个方向扩散，这里判断越界，并且要确定这四个方向的值比当前大，否则不能扩散，假设我们已经求出了其他几个方向（小于等于四）的最长递增路径，这些方向上的点的值都是比当前大的，那么这个点的最长递增路径长度就是，这几个方向的最长递增路径的最大值加1，最终要和1比较一下更大，因为可能所有方向的值都小于等于当前。
最终我们可以加上记忆化，因为我们一旦算出来i，j的最长递增路径的长度之后，我们就可以重复的使用它，不会改变了。这可以节省时间。
示例代码
示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:
return 0
h, w = len(matrix), len(matrix[0])
memo = {}
def dfs(i, j):
if (i, j) in memo:
return memo[i, j]
memo[i, j] = 1
cur = matrix[i][j]
for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
_i, _j = i + di, j + dj
if -1 < _i < h and -1 < _j < w \
and matrix[_i][_j] > cur:
memo[i, j] = max(memo[i, j], 1 + dfs(_i, _j))
return memo[i, j]
return max(dfs(i, j) for i in range(h) for j in range(w))
|
优化空间使用矩阵来记忆化搜索：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:
return 0
h, w = len(matrix), len(matrix[0])
memo = [[0] * w for _ in range(h)]
def dfs(i, j):
if memo[i][j]:
return memo[i][j]
memo[i][j] = 1
cur = matrix[i][j]
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
_i, _j = i + dx, j + dy
if -1 < _i < h and -1 < _j < w \
and matrix[_i][_j] > cur:
memo[i][j] = max(memo[i][j], 1 + dfs(_i, _j))
return memo[i][j]
return max(dfs(i, j) for i, j in itertools.product(range(h), range(w)))
|