日期: 2024 年 3 月 17 日

目标

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

说明：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^6

思路

题目要我们求从矩阵第一列出发的最大移动次数。当前单元格可以移动到其后面一列的上中下三格，如果相应位置的值大于当前元素的话。

这道题可以使用动态规划来做，虽然重叠的子问题不多。从右向左，从下到上/从上到下，计算每个单元格可以移动的最大次数。然后求第一列的最大值即可。

值得注意的是这种列在外层从右向左的循环方式。如果像平时那样外层行循环内层列循环，那么写状态转移方程时，子问题可能还未计算。

官网题解给的是广度优先搜索的方法，遍历第一列起点，将能到达的第二列的格子加入集合，然后遍历这些格子，如此反复直到无法继续或者到达矩阵最大边界n-1。

代码

/**
 * @date 2024-03-16 15:08
 */
public class MaxMoves {

    public int maxMoves(int[][] grid) {
        int[][] dp = new int[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            dp[i] = new int[grid[i].length];
        }
        int res = 0;
        int i = grid.length - 1;
        for (int j = grid[i].length - 2; j >= 0; j--) {
            i = grid.length - 1;
            for (; i >= 0; i--) {
                if (i != 0 && grid[i][j] < grid[i - 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + 1);
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i != grid.length - 1 && grid[i][j] < grid[i + 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }
                if (j == 0){
                    res = Math.max(res, dp[i][0]);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        MaxMoves main = new MaxMoves();
        System.out.println(main.maxMoves(new int[][]{{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}}));
    }
}

性能

网友的题解还有网格DFS（2ms）、BFS（6ms）。虽然时间复杂度都是O(mn)，但是性能差别还是挺大的。有时间可以分析一下，性能到底差在哪里。先不追求性能100%了，先以最快的速度将题过一遍。