Mlog4-矩阵中的最长递增路径

Author Avatar
Emily Chen 7月 03, 2019

2019-4-22

文章目录：

  1. 题目要求
  2. 解题思路
  3. 具体实现
  4. 改进之路
  5. 总结

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记忆化搜索

1
2
3
4
5
6
7
8
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 示例代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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的答案

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
45
46
47
48
49
50
51
52
53
54
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. 总结

记忆化搜索 = 搜索的形式 + 动态规划的思想。