329. Longest Increasing Path in a Matrix

[Woodyiiiiiii]

记忆化深度搜索(使用缓存)。

不能用BFS。

class Solution {
    public int longestIncreasingPath(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;
        int[][] xy = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
        int[][] cache = new int[m][n];
        int res = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                boolean[][] v = new boolean[m][n];
                int k = DFS(matrix, v, xy, m, n, i, j, 0, cache);
                res = Math.max(res, k);
            }
        }

        return res;

    }

    private int DFS(int[][] matrix, boolean[][] v, final int[][] xy, int m, int n, int i, int j, int len, int[][] cache) {
        
        // use cache
        if (cache[i][j] != 0) {
            return cache[i][j];
        }

        v[i][j] = true;

        ++len;

        int l = 0;
        for (int k = 0; k < 4; ++k) {
            int ii = i + xy[k][0];
            int jj = j + xy[k][1];
            if (ii >= 0 && ii < m && jj >= 0 && jj < n
                    && !v[ii][jj] && matrix[ii][jj] > matrix[i][j]) {
                l = Math.max(l, DFS(matrix, v, xy, m, n, ii, jj, 0, cache));
            }
        }

        v[i][j] = false;

        cache[i][j] = len + l;

        return cache[i][j];
        
    }
    
}

---

参考资料：

• https://leetcode.com/problems/longest-increasing-path-in-a-matrix/