LeetCode 329 Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
<pre>nums = [ [<font color="red">9</font>,9,4], [<font color="red">6</font>,6,8], [<font color="red">2</font>,<font color="red">1</font>,1] ] </pre>
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
<pre>nums = [ [<font color="red">3</font>,<font color="red">4</font>,<font color="red">5</font>], [3,2,<font color="red">6</font>], [2,2,1] ] </pre>
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
题目大意：
给定一个整数矩阵，计算其最长递增路径的长度。 从每一个单元格出发，你可以向四个方向移动：左右上下。你不可以沿着对角线移动也不能移出边界。（亦即，环绕是不允许的）。
Floyd解题思路：
这是经典题，类似于LIS题，只要将以每个点为终点的最长路径长度存起来，就可以类推它的邻近点的最长长度（DP）。f(x,y)=max{f(x,y),4个邻近点的f+1}
由于这是求最长路径题且为矩阵，可以考虑按步长计算，就是Floyd的思路，就是先计算步长为1,2一直到所以最长路径长度矩阵长度不再更新为止。
另一个思路也是用矩阵存起每个点最长路径长度，但用DFS搜索，直至这个点的值不为初始值为止，详见书影博客。
注意事项：
- 矩阵为空或长度为0
- 当任何值没有更新时，Floyd停止计算
Java代码：
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45public int longestIncreasingPath(int[][] matrix) {
if (matrix==null || matrix.length==0)
return 0;
int[][] path = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++)
for(int j=0;j<matrix[0].length;j++)
path[i][j] = 1;
boolean nextPath = true;
while(nextPath){
nextPath = false;
for(int i=0;i<matrix.length;i++)
for(int j=0;j<matrix[0].length;j++){
if(changeCell(matrix, path, i, j))
nextPath = true;
}
}
int max = 1;
for(int i=0;i<matrix.length;i++)
for(int j=0;j<matrix[0].length;j++)
if(path[i][j]>max)
max = path[i][j];
return max;
}
public boolean changeCell(int[][] matrix, int[][] path, int i, int j){
int pre = path[i][j];
if(i-1>=0 && matrix[i-1][j]<matrix[i][j] && path[i-1][j]+1>path[i][j])
path[i][j] = path[i-1][j]+1;
if(i+1<matrix.length && matrix[i+1][j]<matrix[i][j] && path[i+1][j]+1>path[i][j])
path[i][j] = path[i+1][j]+1;
if(j-1>=0 && matrix[i][j-1]<matrix[i][j] && path[i][j-1]+1>path[i][j])
path[i][j] = path[i][j-1]+1;
if(j+1<matrix[0].length && matrix[i][j+1]<matrix[i][j] && path[i][j+1]+1>path[i][j])
path[i][j] = path[i][j+1]+1;
if(pre!=path[i][j])
return true;
else return false;
}
算法分析：
k为最长路径长度，时间复杂度为<code>O(k_n_<sup>2</sup>)</code>，空间复杂度<code>O(n<sup>2</sup>)</code>。
DP算法II解题思路(推荐)：
求最值，考虑用DP，但DP的应用条件为有序，所以不妨将所有值排序。
先对所有数的值排序作为新的输入数组，按这个顺序，计算DP，每个点的往前4个方向的DP值+1。
如题第一个例子, 元祖里第一个为值，后两个为xy坐标
[(1, 2, 1), (1, 2, 2)...]
递归公式：
1
dp[x][y] = dp[x + dx][y + dy] + 1, ifmatrix[x][y] > matrix[x + dx][y + dy]:
注意事项：
- 当递增时，才更新DP，Line 13
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
ary = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
ary.append((matrix[i][j], i, j))
ary.sort()
dp = [[1 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
for val, _x, _y in ary:
for _dx, _dy in OFFSETS:
x, y = _x + _dx, _y + _dy
if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]):
continue
if matrix[x][y] > matrix[_x][_y]:
dp[x][y] = max(dp[x][y], dp[_x][_y] + 1)
return max(map(max, dp))
算法分析：
排序是n^2logn^2 = n^2logn, dp计算是n^2 所以时间复杂度为<code>O(n<sup>2</sup>logn)</code>，空间复杂度<code>O(n<sup>2</sup>)</code>
算法III解题思路：
这题也可以额用记忆性搜索DFS来解。
