Topic describes

Given an m x n integer matrix matrix, find the length of the longest increasing path.

For each cell, you can move up, down, left, and right. You cannot move diagonally or out of bounds.

Answer key

Backtracking, in fact, can look like this:

But the time complexity will exceed.

The class Solution {int [] [] direction = {{0, 1}, {0, 1}, {1, 0}, {1, 0}}; int[][] matrix; int res = 0; int row; int col; int path = 0; public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; this.matrix = matrix; this.row = matrix.length; this.col = matrix[0].length; boolean[][] marked = new boolean[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { dfs(marked, i, j); } } return res; } public void dfs(boolean[][] marked, int r, int c) { if (r < 0 || r >= row || c < 0 || c >= col || marked[r][c]) { return; } marked[r][c] = true; path++; for (int[] dic : direction) { int x = dic[0] + r; int y = dic[1] + c; if (0 <= x && x < row && 0 <= y && y < col && matrix[x][y] > matrix[r][c]) { dfs(marked, x, y); } res = Math.max(res, path); } marked[r][c] = false; path--; return; }}Copy the code

The answer is to use a matrix memo to record the longest path that can be searched for each location. In this way, if you pass this location later, you do not need to search, but directly add the recorded path.

Execution time: 9 ms, beating 74.78% of all Java commits

Memory consumption: 38.8 MB, beating 29.80% of all Java commits

class Solution { int m = 0; int n = 0; int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int[][] memo; public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; this.m = matrix.length; this.n = matrix[0].length; this.memo = new int[m][n]; // Record the longest path that can be searched from each starting point. This is the key to reducing time complexity. int res = 1; // res defaults to 1 for (int I = 0; i < m; i++) { for (int j = 0; j < n; j++) { res = Math.max(res, dfs(matrix, i, j)); } } return res; } public int DFS (int[][] matrix, int I, int j) {if (memo[I][j] > 0) Memo [I][j] return memo[I][j]; int len = 1; For (int[] d: dirs) {int x = I + d[0]; int y = j + d[1]; if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) { int nextLen = 1 + dfs(matrix, x, y); len = Math.max(len, nextLen); } } memo[i][j] = len; return len; }}Copy the code