2019-4-22
文章目录：
- 题目要求
- 解题思路
- 具体实现
- 改进之路
- 总结
1. 题目要求
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 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]。注意不允许在对角线方向上移动。
--题目来源于 leetcode
2. 解题思路
2.1 二维数组存储数据 int[][] matrix，int[][] dpn 记录路径.
2.2 参考动态规划之记忆化搜索 滑雪问题:
image
上图显示为R*C的雪场，R是行数，C是列数。圆圈内的数字表示的是雪场的海拔高度h，根据常识我们知道，滑雪只有从上往下滑行才可能滑的动，现在我们想要求出能够滑行的最长距离，上面的例子我们可以很直接判断出25-24-......-1这个顺时针方向螺旋的滑雪方式可以滑的最远。
那么这个问题如何用编程来实现呢？我们发现这是一个典型的递推，DP(i, j)表示从坐标（i，j）出发所能滑行的最大长度，且有：DP(i, j)=optimal{DP(i±1, j±1)}+1.
2.3 DP记忆化搜索
dfs(problem a){
if(a has been solved)
then: consult the record.
else//get the optimal solution of problem a.
divide the problem a into several sub-problems(a1,a2,...,ak)
get the solution of problem a by dfs(a1),dfs(a2),...,dfs(ak).
finally write the optimal solution into record.
}
3. 具体实现
3.1 示例代码
package cxy.com;
public class LongestIncrementalPath {
static int row;//行
static int colcumn;//列
public static void main(String[] args) {
/**
* [
[9,9,4],
[6,6,8],
[2,1,1]
]
*/
int[][] m = {{9,9,4},{6,6,8},{2,1,1}};//示例
int length = LongestIncrementPath(m);
System.out.println("最长递增路径的长度:"+length);
}
public static int LongestIncrementPath(int[][] matrix) {
if(matrix==null||matrix.length==0)return 0;
int max=1;
row=matrix.length;
colcumn=matrix[0].length;
int dpn[][]=new int[row][colcumn];//记录该点出发的最长路径，走过就记录长度，没有就是初值==0；
for(int i=0;i<row;i++){//初值：没走过就是==0；
for(int j=0;j<colcumn;j++){
dpn[i][j]=0;
}
}
for(int i=0;i<row;i++){//以每个点为起点扫描
for(int j=0;j<colcumn;j++){
int t= longestPath(i,j,matrix,dpn);//方法：以该点出发的最大长度
if(t>max)max=t;//比较：max记为最大
}
}
return max;
}
static int longestPath(int x,int y,int [][]mat,int dpn[][]){
if(x<0||y<0||x>=row||y>=colcumn)//越界判断；
return 0;
if(dpn[x][y]!=0)return dpn[x][y];//走过的话，直接取值
int max=0;
//----------向左走
if(y-1>=0 && mat[x][y]<mat[x][y-1]){
int temp;
//走过的话，直接取值
if(dpn[x][y-1]!=0)temp=dpn[x][y-1];
else temp=longestPath(x,y-1,mat,dpn);//递归
max=max>temp?max:temp;//记录最大
}
//----------向右走
if(y+1<colcumn && mat[x][y]<mat[x][y+1]){
int temp;
if(dpn[x][y+1]!=0)temp=dpn[x][y+1];
else temp=longestPath(x,y+1,mat,dpn);
max=max>temp?max:temp;
}
//------------向下走
if(x-1>=0 && mat[x][y]<mat[x-1][y]){
int temp;
if(dpn[x-1][y]!=0)temp=dpn[x-1][y];
else temp=longestPath(x-1,y,mat,dpn);
max=max>temp?max:temp;
}
//------------向上走
if(x+1<row && mat[x][y]<mat[x+1][y]){
int temp;
if(dpn[x+1][y]!=0)temp=dpn[x+1][y];
else temp=longestPath(x+1,y,mat,dpn);
max=max>temp?max:temp;
}
//记为走过了，并存下 以此点出发的路径长度
if(dpn[x][y]==0)dpn[x][y]=max+1;
return dpn[x][y];
}
}
3.2 执行结果与分析：
最长递增路径的长度:4
2018-5-29
4. 改进之路
通过 leetcode 可以看出，执行时间相对较短，但是内存消耗大。参考评论区的其他大佬们的思路和答案，可以有另外一种更优的解法。
---leetcode 玩家 gyx2110的答案
package cxy.com;
public class LongestIncrementalPath {
static int row;//行
static int colcumn;//列
public static void main(String[] args) {
/**
* [
[9,9,4],
[6,6,8],
[2,1,1]
]
*/
int[][] m = {{9,9,4},{6,6,8},{2,1,1}};//示例
int length =longestIncreasingPath(m);
System.out.println("最长递增路径的长度【1】:"+length);
}
public static int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0)
return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int[][] map = new int[m][n];
int res = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = Math.max(res, dfs(matrix, i, j, map, dirs));
}
}
return res;
}
// dfs求以点(i,j)结尾的最长递增路径
public static int dfs(int[][] matrix, int i, int j, int[][] map, int[][] dirs) {
if (map[i][j] != 0)
return map[i][j];
int res = 1;
for (int[] dir : dirs) {
int x = i + dir[0], y = j + dir[1];
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] >= matrix[i][j])
continue;
// 当周围的点小于当前点才递归
res = Math.max(res, 1 + dfs(matrix, x, y, map, dirs));
}
map[i][j] = res;
return res;
}
}
执行结果与分析：
最长递增路径的长度【1】:4
2019-5-29
5. 总结
记忆化搜索 = 搜索的形式 + 动态规划的思想。
网友评论