矩阵中移动的最大次数-LeetCode

2684. 矩阵中移动的最大次数 - Maximum Number of Moves in a Grid

🎯 问题描述（来源于LeetCode）

描述：
给定一个 m x n 的整数矩阵 grid，从第一列的任意单元格出发，每次可以向右上、右、右下三个方向移动到相邻列，且要求目标单元格的值严格大于当前单元格的值。
问最多可以移动多少步（即到达的列数减1）？如果不能移动，返回 0。

说明：

• 每一步只能移动到下一列，不能停留在同一列。
• 行索引变化为 -1, 0, +1，列索引变化固定为 +1。
• 起点可以是第一列任意行。

示例：

• 示例 1：

输入: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出: 3
解释: 可以从第0行第0列出发：2→4→9→15（步数3）

• 示例 2：

输入: grid = [[3,2,4],[2,1,9],[1,1,7]]
输出: 0
解释: 无法从任何起点移动。

💻 解题思路

思路1：记忆化搜索（DFS + 缓存）

算法步骤

1. 获取网格尺寸 m, n。
2. 定义递归函数 dfs(i, j)：返回从 (i, j) 出发能移动的最大步数（不包括当前列）。
   • 如果 j == n-1（已在最后一列），返回 0。
   • 否则，尝试三个方向（di = -1, 0, 1），若新位置 (ni, j+1) 合法且值大于 grid[i][j]，则递归计算 1 + dfs(ni, j+1)，并取最大值。
   • 使用 @cache 装饰器缓存结果，避免重复计算。
3. 计算所有起点 (i, 0) 能得到的最大步数，取最大值返回。

思路1：代码实现

from functools import cache
from typing import List

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i, j):
            if j == n-1:
                return 0
            res = 0
            for di in (-1, 0, 1):
                ni = i + di
                if 0 <= ni < m and grid[ni][j+1] > grid[i][j]:
                    res = max(res, 1 + dfs(ni, j+1))
            return res
        return max(dfs(i, 0) for i in range(m))

思路1：📊 性能分析

• 时间复杂度：$O(m \times n)$，每个状态 (i, j) 最多计算一次。
• 空间复杂度：$O(m \times n)$，缓存表大小和递归栈深度。

---

思路2：DFS + 剪枝 + 原地标记（无缓存）

算法步骤

1. 获取网格尺寸 m, n，初始化全局变量 ans = 0。
2. 定义递归函数 dfs(i, j)：
   • 更新 ans = max(ans, j)（当前到达的列数）。
   • 如果 ans == n-1（已经到达最后一列），直接返回（最优剪枝）。
   • 尝试三个方向 di = -1, 0, 1，若新位置合法且值大于当前值，则递归调用 dfs(ni, j+1)。
   • 递归结束后，将 grid[i][j] 设为 0，避免重复访问（因为后续路径不会再走值更小的格子，但实际需要保证不会重复经过同一格子，此处标记为0是为了防止在同一路径中循环，但本题由于只能向右移动，不会形成环，所以可省略；然而代码中这样写能确保不同起点不会重复访问已走过的格子，从而减少冗余搜索）。
3. 从第一列的每个起点调用 dfs(i, 0)。
4. 返回 ans（最大步数）。

思路2：代码实现

from typing import List

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        
        def dfs(i, j):
            nonlocal ans
            ans = max(ans, j)
            if ans == n-1:  # 已到达最后一列，无需继续
                return
            for di in (-1, 0, 1):
                ni = i + di
                if 0 <= ni < m and grid[ni][j+1] > grid[i][j]:
                    dfs(ni, j+1)
            grid[i][j] = 0  # 标记已访问，避免重复
        
        for i in range(m):
            dfs(i, 0)
        return ans

思路2：📊 性能分析

• 时间复杂度：最坏 $O(m \times n)$，但实际通过剪枝和标记能提前终止，平均性能较好。
• 空间复杂度：$O(L)$，递归栈深度最大为 $n$（列数），但标记会修改原数组。

思考

• 思路1 使用记忆化搜索，逻辑清晰，无副作用（不修改原数组），适用于一般场景。
• 思路2 通过全局变量记录答案并剪枝，利用原地标记减少重复搜索，代码更紧凑，但会改变输入数据。