329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

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

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution:

DFS and dynamic programming.

We can calculate all the maximum length for all cells if the path start at the current cell using DFS. 

So if his neighbor is greater than the current cell, we DFS to its neighbors, and find the max for all 4 directions.

If we only do DFS, we can't pass the time limit, because we actully calculate some cells multiple times.

For example:

nums = [
  [3,4,5],
  [1,2,6],
  [7,8,9]
]

Cell 4 will be visited twice, first as the right neighbor of element 3 and then as the top element of cell 2. We need a array to keep all visited values,
If the element is visited, we can simply apply the maximum length rather than run DFS again from that cell.
The maxLength of current element would be maximum of all qualified neighbors + 1.

  public int longestIncreasingPath(int[][] matrix) {  
     if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;  
     int m=matrix.length;  
     int n=matrix[0].length;  
     int res=1;  
     int[][] dp=new int[m][n];  
     for(int i=0;i<m;i++){  
       for(int j=0;j<n;j++){  
       res=Math.max(res,helper(matrix,i,j,dp));  
       }  
     }  
     return res;  
   }  
   public int helper(int[][] matrix, int i, int j, int[][] dp){  
     if(dp[i][j]!=0) return dp[i][j];  
     int res=1;  
     if(i>0 && matrix[i-1][j]>matrix[i][j]){  
       res=Math.max(helper(matrix,i-1,j,dp)+1,res);  
     }  
     if(i+1<matrix.length && matrix[i+1][j]>matrix[i][j]){  
       res=Math.max(helper(matrix,i+1,j,dp)+1,res);  
     }  
     if(j>0 && matrix[i][j-1]>matrix[i][j]){  
       res=Math.max(helper(matrix,i,j-1,dp)+1,res);  
     }  
     if(j+1<matrix[0].length && matrix[i][j+1]>matrix[i][j]){  
       res=Math.max(helper(matrix,i,j+1,dp)+1,res);  
     }  
     dp[i][j]=res;  
     return res;      
   }