和回溯不同的是 没有返标记的过程

329. Longest Increasing Path in a Matrix

The DFS use a pre parameter to store the former value to be compared to the current value. More reasonable to

public class Solution {
    //DFS
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        if(matrix == null || m==0) return 0;
        int n = matrix[0].length;
        int[][] memo = new int[m][n];
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(0);
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                helper(matrix,i,j,memo,Integer.MAX_VALUE,result);
            }
        }
        return result.get(0);

    }
    /** memo stores the longest increasing path start from (i,j)
     Since we keep the computed value in memo array we do not need a visited array
    //pre参数的设置非常巧妙,如果不用这个参数，则我们需要在代码里进行四个方向的比较*/
    public int helper(int[][] matrix,int i,int j,int[][] memo,int pre,List<Integer> res){
        int m = matrix.length;
        int n = matrix[0].length;
        //if the value have been computed before,simply return it
        if(i<0||j<0||i>=m||j>=n||matrix[i][j]>=pre){
            return 0;
        }
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        //4 direction
        int cur = matrix[i][j];
        int tmp = 0;
        tmp = Math.max(helper(matrix,i-1,j,memo,cur,res),tmp);
        tmp = Math.max(helper(matrix,i+1,j,memo,cur,res),tmp);
        tmp = Math.max(helper(matrix,i,j-1,memo,cur,res),tmp);
        tmp = Math.max(helper(matrix,i,j+1,memo,cur,res),tmp);
        memo[i][j] = tmp + 1;
        if(memo[i][j] > res.get(0))res.set(0,memo[i][j]);
        return memo[i][j];
    }
}

417. Pacific Atlantic Water Flow

perform dfs checking from pacific side and atlantic side check the cross-over between these two and add to the final list