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

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.

Thinking:

  • Method 1:DFS， TLE
class Solution {    
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int height = matrix.length, width = matrix[0].length;
        int res = 1;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                boolean[][] visited = new boolean[height][width];
                res = Math.max(res, bfs(matrix, visited, i, j));
            }
        }
        return res;
    }
    private int bfs(int[][] matrix, boolean[][] visited, int row, int col){
        int cur = matrix[row][col];
        int height = matrix.length, width = matrix[0].length;
        int max = Integer.MIN_VALUE;
        visited[row][col] = true;
        for(int d = 0; d < 4; d++){
            int tempRow = row + dir[d][0];
            int tempCol = col + dir[d][1];
            if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !visited[tempRow][tempCol] && matrix[tempRow][tempCol] > cur){
                max = Math.max(max, bfs(matrix, visited, tempRow, tempCol));
            }
        }
        visited[row][col] = false;
        return max == Integer.MIN_VALUE? 1: max + 1;
    }
}
  • Method 2:dp + optimation
    • 通过cache存储已经测试过得结点。对于一个结点，最优解是唯一的。
    • 减去visited数组，因为本来想要排除的是来时的路径，但是上一个位置的数字一定比当前小，已经被排除了。
class Solution {    
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int height = matrix.length, width = matrix[0].length;
        int res = 1;
        int[][] cache = new int[height][width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                res = Math.max(res, bfs(matrix, i, j, cache));
            }
        }
        return res;
    }
    private int bfs(int[][] matrix, int row, int col, int[][] cache){
        if(cache[row][col] != 0) return cache[row][col];
        int cur = matrix[row][col];
        int height = matrix.length, width = matrix[0].length;
        int max = 1;
        for(int d = 0; d < 4; d++){
            int tempRow = row + dir[d][0];
            int tempCol = col + dir[d][1];
            if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && matrix[tempRow][tempCol] > cur){
                max = Math.max(max, bfs(matrix, tempRow, tempCol, cache) + 1);
            }
        }
        cache[row][col] = max;
        return cache[row][col];
    }
}