Mlog10: LeetCode --矩阵中的最长递增路径

image

文章目录：

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

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

image

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

image

5. 总结

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