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:
nums = [ [9,9,4], [6,6,8], [2,1,1] ]Return 4The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [ [3,4,5], [3,2,6], [2,2,1] ]Return 4The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
思路一：
DFS， 会TLE， 程序如下所示：
class Solution { private int longest = 1, curLen = 1; public int longestIncreasingPath(int[][] matrix) { int row = matrix.length; if (row == 0){ return 0; } int col = matrix[0].length; int[][] cache = new int[row][col]; for (int i = 0; i < row; ++ i){ for (int j = 0; j < col; ++ j){ curLen = 0; dfs(matrix, i, row, j, col, Integer.MAX_VALUE); } } return longest; } public void dfs(int[][] matrix, int i, int row, int j, int col, int pre){ if (i < 0||i >= row||j < 0||j >= col){ return; } if (pre == Integer.MAX_VALUE){ curLen = 1; } else if (matrix[i][j] > pre){ curLen ++; } else { longest = Math.max(longest, curLen); return; } dfs(matrix, i + 1, row, j, col, matrix[i][j]); dfs(matrix, i - 1, row, j, col, matrix[i][j]); dfs(matrix, i, row, j - 1, col, matrix[i][j]); dfs(matrix, i, row, j + 1, col, matrix[i][j]); curLen --; } }思路二：
思路一的升级版，思路一的问题在于DFS深度很深时，元素会大量的重复访问，可以在思路一中引入一个缓存，用于储存 i 位置开始出现的最大递增序列长度，如果新的位置j访问i位置时（i为j的下一相邻位置），则直接加上i位置的缓存长度即可（因为如果合法的话，可以直接相加，想想是不是这样），就免去了从j位置到i位置时，在从i位置展开做DFS的重复工作。程序如下所示：
class Solution { private int longest = 1; public int longestIncreasingPath(int[][] matrix) { int row = matrix.length; if (row == 0){ return 0; } int col = matrix[0].length; int[][] cache = new int[row][col]; for (int i = 0; i < row; ++ i){ for (int j = 0; j < col; ++ j){ longest = Math.max(longest, dfs(matrix, i, row, j, col, Integer.MIN_VALUE, cache)); } } return longest; } public int dfs(int[][] matrix, int i, int row, int j, int col, int pre, int[][] cache){ if (i < 0||i >= row||j < 0||j >= col){ return 0; } if (matrix[i][j] <= pre){ return 0; } if (cache[i][j] != 0){ return cache[i][j]; } int a = 1 + dfs(matrix, i + 1, row, j, col, matrix[i][j], cache); int b = 1 + dfs(matrix, i - 1, row, j, col, matrix[i][j], cache); int c = 1 + dfs(matrix, i, row, j - 1, col, matrix[i][j], cache); int d = 1 + dfs(matrix, i, row, j + 1, col, matrix[i][j], cache); longest = Math.max(a, Math.max(b, Math.max(c, d))); cache[i][j] = longest; return longest; } }