Java Solution, DFS + memorization


  • 2
    P
    public class Solution{
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int[][] dis = new int[rowLen][colLen]; // to store the longest increasing length from current point
        int res = 0;
        
        for(int i = 0; i < rowLen; i++)
        {
            for(int j = 0; j < colLen; j++)
            {
                res = Math.max(res, dfs(dis, rowLen, colLen, i, j, matrix));
            }
        }
        
        return res;
    }
    
    public int dfs(int[][] dis, int rowLen, int colLen, int x, int y, int[][] matrix) {
        //if already be visited, return
        if(dis[x][y] != 0)
            return dis[x][y];
        
        for(int i = 0; i < 4; i++)
        {
            int newX = x + dx[i];
            int newY = y + dy[i];
            
            if(newX >= 0 && newY >= 0 && newX < rowLen && newY < colLen && matrix[x][y] < matrix[newX][newY])
            {
                dis[x][y] = Math.max(dis[x][y], dfs(dis, rowLen, colLen, newX, newY, matrix));
            }
        }
        
        dis[x][y]++;
        return dis[x][y];
    }

  • 0
    L

    if all all the element in the martix is same,this solution will return 1。 is this correct?


  • -1
    A

    do you really need to check visited ? it wont be circle because the value is keep increasing and it never come back to the patch that you visited.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.