Medium

题目描述

给你一个下标从 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

解题思路

这道题考查动态规划在矩阵路径问题中的应用。

解题思路：

由于我们只能向右移动（列数增加），且需要保证移动到的单元格值严格大于当前值，我们可以用动态规划逐列处理。

核心思路是：设 dp[i][j] 表示从第一列开始，到达位置 (i, j) 的最大移动次数。

  1. 初始化：第一列的所有单元格移动次数都是 0（起点）

  2. 状态转移：对于第 j 列的每个位置 (i, j)，它可以从第 j-1 列的三个位置转移而来：

    • (i-1, j-1) → (i, j)
    • (i, j-1) → (i, j)
    • (i+1, j-1) → (i, j)

    转移的条件是 grid[i][j] > grid[prev_i][j-1]

  3. 优化：可以只用一维数组滚动更新，因为每次只需要前一列的信息

为了简化边界处理，我们可以逐列从左到右处理，对每一列都检查能从上一列的哪些位置转移过来。

最终答案就是所有可达位置中移动次数的最大值。

代码实现

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(m, 0);
        
        for (int j = 1; j < n; j++) {
            vector<int> newDp(m, -1);
            for (int i = 0; i < m; i++) {
                // 从 (i-1, j-1) 转移
                if (i > 0 && dp[i-1] != -1 && grid[i][j] > grid[i-1][j-1]) {
                    newDp[i] = max(newDp[i], dp[i-1] + 1);
                }
                // 从 (i, j-1) 转移
                if (dp[i] != -1 && grid[i][j] > grid[i][j-1]) {
                    newDp[i] = max(newDp[i], dp[i] + 1);
                }
                // 从 (i+1, j-1) 转移
                if (i < m-1 && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1]) {
                    newDp[i] = max(newDp[i], dp[i+1] + 1);
                }
            }
            dp = newDp;
        }
        
        int result = 0;
        for (int moves : dp) {
            if (moves != -1) {
                result = max(result, moves);
            }
        }
        return result;
    }
};

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [0] * m
        
        for j in range(1, n):
            new_dp = [-1] * m
            for i in range(m):
                # 从 (i-1, j-1) 转移
                if i > 0 and dp[i-1] != -1 and grid[i][j] > grid[i-1][j-1]:
                    new_dp[i] = max(new_dp[i], dp[i-1] + 1)
                # 从 (i, j-1) 转移
                if dp[i] != -1 and grid[i][j] > grid[i][j-1]:
                    new_dp[i] = max(new_dp[i], dp[i] + 1)
                # 从 (i+1, j-1) 转移
                if i < m-1 and dp[i+1] != -1 and grid[i][j] > grid[i+1][j-1]:
                    new_dp[i] = max(new_dp[i], dp[i+1] + 1)
            dp = new_dp
        
        return max(moves for moves in dp if moves != -1) if any(moves != -1 for moves in dp) else 0

public class Solution {
    public int MaxMoves(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[] dp = new int[m];
        
        for (int j = 1; j < n; j++) {
            int[] newDp = new int[m];
            Array.Fill(newDp, -1);
            
            for (int i = 0; i < m; i++) {
                // 从 (i-1, j-1) 转移
                if (i > 0 && dp[i-1] != -1 && grid[i][j] > grid[i-1][j-1]) {
                    newDp[i] = Math.Max(newDp[i], dp[i-1] + 1);
                }
                // 从 (i, j-1) 转移
                if (dp[i] != -1 && grid[i][j] > grid[i][j-1]) {
                    newDp[i] = Math.Max(newDp[i], dp[i] + 1);
                }
                // 从 (i+1, j-1) 转移
                if (i < m-1 && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1]) {
                    newDp[i] = Math.Max(newDp[i], dp[i+1] + 1);
                }
            }
            dp = newDp;
        }
        
        int result = 0;
        foreach (int moves in dp) {
            if (moves != -1) {
                result = Math.Max(result, moves);
            }
        }
        return result;
    }
}

var maxMoves = function(grid) {
    const m = grid.length, n = grid[0].length;
    let dp = new Array(m).fill(0);
    
    for (let j = 1; j < n; j++) {
        const newDp = new Array(m).fill(-1);
        for (let i = 0; i < m; i++) {
            // 从 (i-1, j-1) 转移
            if (i > 0 && dp[i-1] !== -1 && grid[i][j] > grid[i-1][j-1]) {
                newDp[i] = Math.max(newDp[i], dp[i-1] + 1);
            }
            // 从 (i, j-1) 转移
            if (dp[i] !== -1 && grid[i][j] > grid[i][j-1]) {
                newDp[i] = Math.max(newDp[i], dp[i] + 1);
            }
            // 从 (i+1, j-1) 转移
            if (i < m-1 && dp[i+1] !== -1 && grid[i][j] > grid[i+1][j-1]) {
                newDp[i] = Math.max(newDp[i], dp[i+1] + 1);
            }
        }
        dp = newDp;
    }
    
    let result = 0;
    for (const moves of dp) {
        if (moves !== -1) {
            result = Math.max(result, moves);
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m × n)需要遍历矩阵的每个位置，对每个位置检查三个可能的前驱状态
空间复杂度O(m)使用滚动数组优化，只需要存储当前列和前一列的DP状态