Clean Java DFS & DP solution


  • 0
    S
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix == null || matrix.length == 0)  return 0;
            int m = matrix.length;
            int n = matrix[0].length;
            int[][] dp = new int[m][n];
            int max = 0;
            for(int i = 0; i < m; i++)
                for(int j = 0; j < n; j++){
                    int tmp = longestIncreasingPathDFS(matrix, i, j, m, n, dp);
                    if(tmp > max)   max = tmp;
                }
            return max;
        }
        private int longestIncreasingPathDFS(int[][] matrix, int i, int j, int m, int n, int[][] dp){
            if(dp[i][j] != 0)   return dp[i][j];
            int max = 1;
            if(i > 0 && matrix[i][j] < matrix[i-1][j]){      //can go left
                max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i-1, j, m, n, dp));
            }
            if(i < m-1 && matrix[i][j] < matrix[i+1][j]){      //can go right
                max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i+1, j, m, n, dp));
            }        
            if(j > 0 && matrix[i][j] < matrix[i][j-1]){      //can go up
                max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i, j-1, m, n, dp));
            }        
            if(j < n-1 && matrix[i][j] < matrix[i][j+1]){      //can go down
                max = Math.max(max, 1 + longestIncreasingPathDFS(matrix, i, j+1, m, n, dp));
            }
            dp[i][j] = max;
            return max;
        }
    }

Log in to reply
 

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