329. Longest Increasing Path in a Matrix

Q:

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

 

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

A:

   先试试简单的dfs，记录每个点。但是这样会超时。  d*******代码如下***********

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int res = 0;
        boolean A[][] = new boolean[m][n];
        for(int i =0;i<m;i++)
            for(int j =0;j<n;j++)
                res = Math.max(res,dfs(matrix,i,j,A,matrix[i][j]-1));
        return res;
    }
    private int dfs(int[][] matrix, int i ,int j, boolean A[][],int minValue){
        int m = matrix.length,  n = matrix[0].length;
        if(i<0 || i >=m || j < 0 || j >=n || A[i][j])
            return 0;
        if(matrix[i][j]<=minValue)
            return 0;
        A[i][j] = true;
        int l = dfs(matrix, i,j-1, A,matrix[i][j]);
        int r = dfs(matrix, i,j+1, A,matrix[i][j]);
        int u = dfs(matrix, i-1,j, A,matrix[i][j]);
        int d = dfs(matrix, i+1,j, A,matrix[i][j]);
        A[i][j] = false;
        return 1+ Math.max( Math.max(l,r),Math.max(u,d));
    }
}

************改进****************
每个位置记录下其最长的increasing position（starting from it) .  毕竟，我们每个点，如果再找，也只是从比其小的位置开始。

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> M(m, vector<int>(n,-1));// how many it can go up
        int res = 0;
        for(int i =0;i<m;i++)
            for(int j =0;j<n;j++)
                res = max(res, dfs(matrix,i,j,M));
        return res;
    }
private:
    int dfs(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& M){
        if(M[i][j]>0) // if already visited
            return M[i][j];
        
        int m = matrix.size(), n = matrix[0].size();
        M[i][j] = 1;
        if(i-1 >= 0 && matrix[i-1][j] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i-1,j,M));
        }
        if(i+1 < m && matrix[i+1][j] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i+1,j,M));
        }
        if(j-1 >= 0 && matrix[i][j-1] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i,j-1,M));
        }
        if(j+1 < n && matrix[i][j+1] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i,j+1,M));
        }
        return M[i][j];
    }
};

Mistakes: