LeetCode 329. 矩阵中的最长递增路径

https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

这个题是看到被人的面经来刷的。

自己想的dp实现出来是错的，思路完全乱掉了。先贴代码吧。

class Solution {    public int longestIncreasingPath(int[][] matrix) {        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){            return 0;        }        int row = matrix.length;        int col = matrix[0].length;        int[][] dp = new int[row][col];        int result= 0;        for(int i = 0;i < row;i  ){            for(int j = 0; j < col;j  ){                result = Math.max(result,dfs(matrix, dp, i, j, Integer.MIN_VALUE));            }        }        return result;    }    private int dfs(int[][] matrix,int[][] dp,int i,int j,int pre){        if(i<0||i>=matrix.length||j<0||j>=matrix[0].length||matrix[i][j]<=pre){            return 0;        }        if(dp[i][j] != 0){            return dp[i][j];        }        int max = 0;        pre = matrix[i][j];        max = Math.max(max,dfs(matrix, dp, i-1, j, pre));        max = Math.max(max, dfs(matrix, dp, i 1, j, pre));        max = Math.max(max,dfs(matrix, dp, i, j-1, pre));        max = Math.max(max,dfs(matrix, dp, i, j 1, pre));        dp[i][j] = max 1;        return dp[i][j];    }}

View Code

首先先定义一个dp数组来记录部分最大值。

然后两个指针遍历整个矩阵，对每个点都进行一次dfs寻找最大值。

 

进入dfs。

首先先判定一些不满足的条件，直接返回0.

如果dp中的当前位置有数据，则直接返回以加快程序速度。

然后分别对该节点的上、下、左、右进行dfs，将返回的值与当前的max比较。

然后将得到的max值更新到dp数组中并返回。

 

主函数收到值后，与当前整体最大值result比较，取较大的值。

 

2020年7月26日更新

这个题是今天的每日一题，凌晨睡觉前看了下题目就没做了，今早起床花了20多分钟又写了一次，这次终于是自己写出来了。

class Solution {    public int longestIncreasingPath(int[][] matrix) {        if(matrix.length == 0 || matrix[0].length == 0){            return 0;        }        int[][] memo = new int[matrix.length][matrix[0].length];        int res = 1;        for(int i = 0; i < matrix.length; i  ){            for(int j = 0; j < matrix[i].length; j  ){                helper(memo, matrix, i, j, -1);                res = Math.max(res, memo[i][j]);            }        }        return res;    }    int helper(int[][] memo, int[][] matrix, int row, int col, int pre){        if(row < 0 || row >= matrix.length || col < 0 || col >= matrix[row].length || matrix[row][col] <= pre){            return 0;        }        if(memo[row][col] != 0){            return memo[row][col];        }        pre = matrix[row][col];        int num = 1;        num = Math.max(num, helper(memo, matrix, row - 1, col, pre)   1);        num = Math.max(num, helper(memo, matrix, row   1, col, pre)   1);        num = Math.max(num, helper(memo, matrix, row, col - 1, pre)   1);        num = Math.max(num, helper(memo, matrix, row, col   1, pre)   1);        memo[row][col] = num;        return num;    }}

具体的思路和3个月前做的想法差不多，这里我一开始用了一个visited数组去保存每个节点是否被访问过，防止出现套娃现象，结果时间去到了333ms，是去掉visited数组的30倍。。

其实这个题根本用不着visited数组，因为如果可以从matrix[i][j] 推出matrix[i 1][j]，就代表着matrix[i 1][j] 会大于 matrix[i][j]， 那么在本轮循环中自然就不会往回走了。

而且这个题的思路根本算不上dp, 这个只是带备忘录的回溯dfs~~

来源：https://www.icode9.com/content-4-723451.html