329 Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

1. Question

Example 1:

Input: 
nums = 
[
 [9,9,4],
 [6,6,8],
 [2,1,1]
] 

Output: 4 

Explanation:
The longest increasing path is [1, 2, 6, 9].

Example 2:

Input:
 nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 

Output:4 

Explanation: 
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.2. Implementation

(1) Memoization

思路: 从matrix的每个点作为起点，通过DFS找出所有可能的递增路径，然后找到最长的路径。但我们发现，DFS的过程会有很多重复计算，所以我们通过一个m * n的2维矩阵cache来存储每个点上的最长路径值，这样就可以保证每个点最多只计算一次

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = getLongestIncreasingPathByDFS(i, j, matrix, cache, directions);
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }

    public int getLongestIncreasingPathByDFS(int row, int col, int[][] matrix, int[][] cache, int[][] directions) {
        if (cache[row][col] != 0) {
            return cache[row][col];
        }

        int curMaxLen = 1;

        for (int[] direction : directions) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (isValid(row, col, nextRow, nextCol, matrix)) {
                int len = 1 + getLongestIncreasingPathByDFS(nextRow, nextCol, matrix, cache, directions);
                curMaxLen = Math.max(curMaxLen, len);
            }
        }

        cache[row][col] = curMaxLen;
        return curMaxLen;
    }

    public boolean isValid(int curRow, int curCol, int nextRow, int nextCol, int[][] matrix) {
        return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[curRow][curCol] < matrix[nextRow][nextCol];
    }
}

3. Time & Space Complexity

Memoization: 时间复杂度O(mn), 空间复杂度O(mn)