Leetcode 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).

思路：

1. 对数组中每个元素A，都尝试寻找以A为起点的最长路径。
2. 用一个最大值路径变量记录当前寻找到的最长路径。
3. 由于尝试遍历每个元素，数组中某些位置会被重复查找，此时可以通过哈希表来记录以当前位置为起点的最长路径，如果已经查找过，则直接返回值。如果没有被查找过，在算出最大路径值以后存放到哈希表中，下次就不用再计算了。

public class LIPInMatrix329 {

    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        m = matrix.length; n = matrix[0].length;
        int[][] cache = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = Math.max(ans, dfs(matrix, i, j, cache));
            }
        }
            
        return ans;
    }

    private int dfs(int[][] matrix, int x, int y, int[][] cache) {
        if (cache[x][y] != 0) {
            return cache[x][y];
        }
        
        cache[x][y] = 1;
        for (int[] d : dirs) {
            int tx = x + d[0], ty = y + d[1];
            if (0 <= tx && tx < m && 0 <= ty && ty < n && matrix[tx][ty] > matrix[x][y]) {
                cache[x][y] = Math.max(cache[x][y], 1 + dfs(matrix, tx, ty, cache));
            }
        }
        return cache[x][y];
    }
}