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.

[leetcode 329] Longest Increasing Path in a Matrix

这是一道非常常规的题目，虽然是hard难度，思路却非常清晰。
这道题目的意思是在矩阵中找到一组最长序列，这个序列是递增或者递减的，返回序列的长度。我首先想到的就是以矩阵中的每个元素作为序列的起点，然后向其左上右下遍历，用一个flag记录其走过的元素，只用找递增序列就可以了，因为递减序列的尾节点就是递增序列的头结点。于是写出如下代码：

static int maxValue = 0;

public static int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    boolean[][] flag = new boolean[matrix.length][matrix[0].length];
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            dfs(matrix, flag, 0, 0, i, j,true);
        }
    }
    return maxValue;
}

private static void dfs(int[][] matrix, boolean[][] flag, int num, int preValue, int i, int j,boolean isFisrt) {
    if (isFisrt|| !(preValue >= matrix[i][j])) {
        flag[i][j] = true;
        num+=1;
        if (i - 1 >= 0 && flag[i - 1][j] == false) dfs(matrix, flag, num, matrix[i][j],  i - 1, j,false);
        if (j - 1 >= 0 && flag[i][j - 1] == false) dfs(matrix, flag, num, matrix[i][j],  i, j - 1,false);
        if (i + 1 < matrix.length && flag[i + 1][j] == false) dfs(matrix, flag, num, matrix[i][j], i + 1, j,false);
        if (j + 1 < matrix[0].length && flag[i][j + 1] == false) dfs(matrix, flag, num, matrix[i][j],  i, j + 1,false);
        flag[i][j] = false;
    }
    if (num > maxValue) maxValue = num;
}

典型的for+dfs，这个代码的dfs函数没有返回值，我是觉得写返回值太麻烦了，就用全局变量代替了，isFirst是判断是否是第一次进入，主要是第一次进入preValue没有，不能比较。虽然是一个很常见的代码，但是也没有一下子就写出来，也出了很多问题，修修改改改的，然后leetcode上显示TLE，134/137。
在意料之中，比如有一条路径，头结点遍历后，中间的节点实质上是不用再遍历了的，但是我的代码中又会继续遍历中间的节点，这个怎么处理呢，无非就是加条件，用dp来解决，dp矩阵记录当前元素点的最长序列，如果遍历的路径走到dp[i][j]>0的节点，就可以直接取值，而不需要继续遍历了，这样这个问题就解决了，代码如下：

public static int longestIncreasingPath2(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int[][] dp = new int[matrix.length][matrix[0].length];
    int res=0;
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            res=Math.max(res,dfs2(matrix, dp, 0,  i, j,true));
        }
    }

    return res;
}

private static int dfs2(int[][] matrix, int[][] dp, int preValue, int i, int j,boolean isFisrt) {
    if (isFisrt|| !(preValue >= matrix[i][j])) {
        if(dp[i][j]!=0)return dp[i][j];
        int res=0;
        if (i - 1 >= 0 ) res=Math.max(res,dfs2(matrix, dp,  matrix[i][j],  i - 1, j,false));
        if (j - 1 >= 0 ) res=Math.max(res,dfs2(matrix, dp,  matrix[i][j],  i, j - 1,false));
        if (i + 1 < matrix.length ) res=Math.max(res,dfs2(matrix, dp, matrix[i][j], i + 1, j,false));
        if (j + 1 < matrix[0].length) res=Math.max(res,dfs2(matrix, dp,  matrix[i][j],  i, j + 1,false));
        dp[i][j]=++res;
        return dp[i][j];
    }
    return 0;
}

这里没有flag矩阵，因为根本就不需要，找严格递增的序列，必然不会进入到之前走过的位置。也没有全局变量了，leetcode上就通过了，这是参考discuss上的解法，用上面的思路修改了一下。