Hard | LeetCode 329. 矩阵中的最长递增路径 | 矩阵+DFS

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能对角线 方向上移动或移动到 边界外(即不允许环绕)。

示例 1:

Hard | LeetCode 329. 矩阵中的最长递增路径 | 矩阵+DFS
输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4 
解释:最长递增路径为 [1, 2, 6, 9]。

示例 2:

Hard | LeetCode 329. 矩阵中的最长递增路径 | 矩阵+DFS
输入: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;
}
上一篇:计算智能课程设计(遗传算法求解无约束单目标优化问题)


下一篇:【codevs3411】洪水