329. 矩阵中的最长递增路径
给定一个 m x n
整数矩阵 matrix
,找出其中 最长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
示例 1:
输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4
解释:最长递增路径为 [1, 2, 6, 9]。
示例 2:
输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出:4
解释:最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3:
输入:matrix = [[1]]
输出:1
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1
解题思路
方法一: 深度优先搜索 + 记忆化矩阵
这是一道普通的深度优先搜索题目, 不过加上了深度优先的条件: 必须递增, 并且是严格递增。(严格递增可以保证在多次DFS不会出现循环的情况)
可以使用使用一个额外的矩阵保存计算的中间结果。
private int[][] detla = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private int row, column;
private int[][] longestPath;
public int longestIncreasingPath(int[][] matrix) {
row = matrix.length;
column = matrix[0].length;
longestPath = new int[row][column];
int maxLength = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
maxLength = Math.max(dfs(matrix, i, j), maxLength);
}
}
return maxLength;
}
private int dfs(int[][] matrix, int x, int y) {
if (longestPath[x][y] != 0) {
return longestPath[x][y];
}
int maxLength = 0;
for (int i = 0; i < 4; i++) {
int newx = x + detla[i][0], newy = y + detla[i][1];
if (newx >= 0 && newx < row && newy >= 0 && newy < column && matrix[newx][newy] > matrix[x][y]) {
maxLength = Math.max(dfs(matrix, newx, newy), maxLength);
}
}
return longestPath[x][y] = 1 + maxLength;
}