Longest Increasing Path in a Matrix

Question

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

Solution

核心想法不難，用 DFS 去遍歷然後更新 global variable 就可以。但用 naive DFS 會得到 TEL。看了解答後，發現由於 DFS 會重複計算很多點，因此可以使用 memorization 來提高效率，即用一個 int[][] 來記錄該點遍歷完後的 max，如果踩到這個點，直接返回值就可以 return

    final int[][] steps = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix == null) {
            return 0;
        }
        int row = matrix.length, col = matrix[0].length;
        int[][] cache = new int[row][col];
        int max = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int len = dfs(matrix, i, j, row, col, cache);
                max = Math.max(max, len);
            }
        }
        return max;
    }

    public int dfs(int[][] matrix, int i, int j, int row, int col, int[][] cache) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        int max = 1;
        for (int[] step : steps) {
            int x = i + step[0], y = j + step[1];
            if (x >= row || x < 0 || y >= col || y < 0 || matrix[x][y] <= matrix[i][j]) {
                continue;
            }
            int len = 1 + dfs(matrix, x, y, row, col, cache);
            max = Math.max(max, len);
        }
        cache[i][j] = max;
        return max;
    }

我用的方法是 public void dfs，也就是沒有 return 值，但不知道為什麼一直有 bug，記錄在下面，之後可以回來想。跟劉哥討論完，我下面的寫法有兩個錯誤：

1. 當 cache[i][j] != 0 的時候，也應該要去 update cache，不能只在當 dfs 走不下去的時候才更新
2. 在 cache[i][j] 的 len = Math.max(len, cache[i][j] + length - 1);但在 dfs 走不下去時的 cache[initial_i][initial_j] = Math.max(length, cahce[][]) 就好

不過這樣雖然對了，但還是會拿到 TLE。用這樣的寫法，即便是有了 cache，也只會在外層迭代時，譬如從 (1,0)，dfs 走回 (0,0) 時可以拿值來用。但其實你在裡面 dfs 其他點，雖然都算過，但因為這個寫法並不會去記錄，所以相當於沒什麼 improvement，可能只比 naive DFS 好那麼一些而已。Memorization 的精髓在於讓每個點只計算一次，之後走到就可以直接拿來用，因此還是要讓自己習慣寫有 return 的 DFS

    int len = 1;
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0 || matrix == null) {
            return 0;
        }
        int[][] steps = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int[][] cache = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dfs(matrix, steps, i, j, i, j, 1, cache);
            }
        }

        return len;
    }

    public void dfs(int[][] matrix, int[][] steps, int i, int j, int initial_i, int initial_j, int length, int[][] cache) {

        if (cache[i][j] != 0) {
            len = Math.max(len, cache[i][j] + length);
            return;
        }
        for (int[] step : steps) {
            int x = i + step[0], y = j + step[1];
            if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0 || matrix[x][y] <= matrix[i][j]) {
                len = Math.max(len, length);
                cache[initial_i][initial_j] = Math.max(length - 1, cache[initial_i][initial_j]);
                continue;
            } else {
                dfs(matrix, steps, x, y, initial_i, initial_j, length + 1, cache);    
            }
        }
        return;
    }