https:///problems/longest-increasing-path-in-a-matrix/

這個題是看到被人的面經(jīng)來刷的。

自己想的dp實現(xiàn)出來是錯的，思路完全亂掉了。先貼代碼吧。

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];
    }
}

首先先定義一個dp數(shù)組來記錄部分最大值。

然后兩個指針遍歷整個矩陣，對每個點都進行一次dfs尋找最大值。

?

進入dfs。

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

如果dp中的當(dāng)前位置有數(shù)據(jù)，則直接返回以加快程序速度。

然后分別對該節(jié)點的上、下、左、右進行dfs，將返回的值與當(dāng)前的max比較。

然后將得到的max值更新到dp數(shù)組中并返回。

?

主函數(shù)收到值后，與當(dāng)前整體最大值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數(shù)組去保存每個節(jié)點是否被訪問過，防止出現(xiàn)套娃現(xiàn)象，結(jié)果時間去到了333ms，是去掉visited數(shù)組的30倍。。

其實這個題根本用不著visited數(shù)組，因為如果可以從matrix[i][j] 推出matrix[i 1][j]，就代表著matrix[i 1][j] 會大于 matrix[i][j]， 那么在本輪循環(huán)中自然就不會往回走了。

而且這個題的思路根本算不上dp, 這個只是帶備忘錄的回溯dfs~~