给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
1
2
3
| 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
|
初写思路:
建立dp[][],表示在matrix[][]为终点的最大路径长度,初始值设为1
遍历矩阵,对于每一个元素,找到其旁边比他大的元素,然后比较他们的dp大小
dp递推式为: dp[大的相邻点] = Math.max(dp[大的相邻点],dp[当前点]+1);
初次实现:
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
| class Solution {
void tryFill(int matrix[][],int a,int b,int dp[][]){
int m = matrix.length;
int n = matrix[0].length;
if(a-1>=0&&matrix[a-1][b]>matrix[a][b]){
dp[a-1][b] = Math.max(dp[a-1][b],dp[a][b]+1);
tryFill(matrix,a-1,b,dp);
}
if(a+1<m&&matrix[a+1][b]>matrix[a][b]){
dp[a+1][b] = Math.max(dp[a+1][b],dp[a][b]+1);
tryFill(matrix,a+1,b,dp);
}
if(b-1>=0&&matrix[a][b-1]>matrix[a][b]){
dp[a][b-1] = Math.max(dp[a][b-1],dp[a][b]+1);
tryFill(matrix,a,b-1,dp);
}
if(b+1<n&&matrix[a][b+1]>matrix[a][b]){
dp[a][b+1] = Math.max(dp[a][b+1],dp[a][b]+1);
tryFill(matrix,a,b+1,dp);
}
}
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int dp[][] = new int[m][n];
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
dp[i][j] = 1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
tryFill(matrix,i,j,dp);
int max = -1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
max = Math.max(max,dp[i][j]);
return max;
}
}
|
最后结果超时,140个样例过了130多个
分析原因,判断是dp迭代的过程进行了太多重复工作,对此进行优化
优化后的思路(DFS+DP)
重新定一个一个数组directions来表示上下左右的移动
在tryFill中不再进行逐次逐层的递归查找,而是直接递归找到底,在递归的过程中更新dp数组
在这个实现中,可以理解为每一个点会感染他附近比他更大的点,会向附近比他大的点一直传递下去; 只要发生感染,就会一路传到底,所有传到的点都能直接确定 最终 的dp,就不需要像原方案那样一直递归比较了,极大地降低了时间复杂度
最终代码
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
| class Solution {
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int tryFill(int matrix[][],int a,int b,int dp[][]){
if(dp[a][b]!=0) return dp[a][b];
int m = matrix.length;
int n = matrix[0].length;
int maxLen = 1;
for(int dir[] : directions){
int newM = a+dir[0];
int newN = b+dir[1];
if(newM>=0&&newM<m&&newN>=0&&newN<n&&matrix[newM][newN] > matrix[a][b]){
int len = 1 + tryFill(matrix, newM, newN, dp);
maxLen = Math.max(maxLen,len);
}
}
dp[a][b]=maxLen;
return maxLen;
}
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int dp[][] = new int[m][n];
int maxLen = 1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
maxLen = Math.max(maxLen,tryFill(matrix,i,j,dp));
return maxLen;
}
}
|
