企业官网建设流程全解析

leetcode 题解：Longest Matrix Path Length —— 从暴力 DFS 到去除 visited 的状态记忆化动态规划

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本文基于 leetcode 题解仓库中的 Longest-Matrix-Path-Length 题解展开，完整讲解这道矩阵路径极值问题的两种解法：会超时的暴力 DFS，以及通过「记录来向状态」去掉 visited、恢复记忆化能力（纯函数性）的动态规划解法。读完本文，你将掌握一类经典面试模型——在允许回头移动（左/右）的网格中求最长路径时，如何通过扩充状态维数绕开「路径记录不可复用」的障碍，并把指数级暴力降到多项式复杂度。

题目背景与题意

本题出自 Binary Search 平台，被收录进本仓库的 经典题目索引。题目描述如下：

给定一个二维整数矩阵，其中0表示空格，1表示墙。你可以从第0行的任意空格出发，目标是到达第n - 1行的任意空格。在移动过程中，你可以向左、向右或向下移动，要求路径中每个格子最多被访问一次，返回满足条件的最长路径长度；如果不存在可行路径，返回0。

约束条件

1 ≤ n * m ≤ 200,000

其中n和m分别是矩阵的行数与列数。

示例

Input matrix = [ [0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0] ] Output 10

解释：可行的最长路径为(0, 0) → (0, 1) → (0, 2) → (0, 3) → (1, 3) → (1, 2) → (1, 1) → (2, 1) → (2, 2) → (2, 3)，共访问 10 个格子。注意(1, 0)是墙，因此第一列被切断，必须绕行。

这道题的难点在于：移动方向包含横向的「向左/向右」，这不同于只能向下/向右的标准路径 DP。横向移动意味着路径可能回头，而「每个格子最多访问一次」的限制让朴素的状态定义无法直接记忆化。

思路一：暴力 DFS（会超时）

思路

最直接的解法是枚举所有可能的路径。对于当前单元格，根据题意只有三种移动选择：

• 向左（j - 1）
• 向右（j + 1）
• 向下（i + 1）

由于不能重复访问已经走过的格子，很自然地想到用一个visited集合记录访问过的位置，防止路径绕回成环。

当遇到不可访问点时，返回无穷小float('-inf')表示「此路不通」。不可访问点包括三类：

1. 边界外的点：j < 0或j >= n
2. 已经访问过的点：(i, j) in visited
3. 有障碍物的点：matrix[i][j] == 1

这种解法本质上是暴力枚举所有可能的路径，没有任何剪枝与复用。

代码

代码支持：Python3

class Solution: def solve(self, matrix): m, n = len(matrix), len(matrix[0]) visited = set() def dp(i, j): if (i, j) in visited: return float('-inf') if j < 0 or j >= n: return float('-inf') if i >= m: return 0 if matrix[i][j] == 1: return float('-inf') visited.add((i, j)) ans = 1 + max(dp(i+1, j), dp(i,j+1), dp(i, j-1)) visited.remove((i, j)) return ans ans = max([dp(0, j) for j in range(n)]) return 0 if ans == float('-inf') else ans

复杂度分析

• 时间复杂度：$O(2^{mn})$ —— 路径最长可达 $mn$ 步，每一步最多产生 3 个分支，递归树规模随路径长度指数增长，在n * m ≤ 200,000的约束下必然超时（TLE）。
• 空间复杂度：$O(m*n)$ —— 递归深度与visited集合大小均与路径长度同阶。

为什么朴素记忆化不可行：visited 破坏了纯函数性

这类「暴力枚举所有可能 + 求极值」的题目，很多都可以用动态规划解决。但本题不能直接记忆化。

原因在于：上面的递归函数dp(i, j)不是纯函数。本仓库的 动态规划专题 明确指出，可用于记忆化的递归函数必须满足两个条件：

1. 递归函数不依赖外部变量
2. 递归函数不改变外部变量

只有满足这两点，函数才能保证「参数一定，返回值也一定确定」，从而可以安全地缓存（记忆化）。

而我们的暴力解法中，dp依赖并修改了外部变量visited：同一个(i, j)，在visited中已有其他格子的不同组合下，返回值是不同的——这取决于「当前是从哪条路径走过来的」。因此dp(i, j)的结果不唯一，直接对其做lru_cache会导致错误地复用一个路径上下文下的结果。这本质上违反了动态规划的「无后效性」要求（子问题的解一旦确定就不再受后续决策影响，见 无后效性详解）。

那么如何解决？有两种方向：

• 把 visited 序列化进函数参数：状态空间变为 $O(2^{m*n})$ 量级，空间必然爆炸，不可行。
• 想办法去掉 visited：让状态只由坐标 + 少量附加信息唯一确定，恢复纯函数性。这就是下文动态规划解法的核心。

思路二：动态规划 —— 记录「如何过来的」状态

思路

去掉 visited 的关键在于回答一个问题：站在格子(i, j)时，有哪些方向是「回头路」需要禁止？

仔细分析，当前格子的来向只可能有三种情况：

1. 当前是从上方格子向下移动过来的：此时三个方向（左、右、下）都合法，因为上方的格子不会与左右冲突。
2. 当前是从左边格子向右移动过来的：此时可以继续向右或向下，但不可以向左（否则立刻回到上一个格子）。
3. 当前是从右边格子向左移动过来的：此时可以继续向左或向下，但不可以向右（否则立刻回到上一个格子）。

因此，只需要在状态中多记录一个维度d——「我是从哪个方向来到当前格子的」，就能唯一确定哪些方向被禁止，从而完全去掉visited，恢复记忆化（动态规划）的可行性。

状态定义与转移

定义dp(i, j, d)表示「从格子(i, j)出发，走到最后一行，能访问的最多格子数」，其中方向状态d约定如下：

转移方程为：

dp(i, j, d) = 1 + max( dp(i+1, j, 0), # 向下，新方向 d = 0，永远允许 dp(i, j+1, 1) 若 d != -1, # 向右，新方向 d = 1，若从右边来则禁止 dp(i, j-1, -1) 若 d != 1 # 向左，新方向 d = -1，若从左边来则禁止 )

终止条件与暴力解法一致：j越界返回-inf；i >= m返回0（走出最后一行后不再贡献格子数，相当于路径在最后一行自然结束）；matrix[i][j] == 1（墙）返回-inf。

起始状态：第 0 行的每个空格都可以作为起点，且起点没有来向限制，因此取dp(0, j, 0)的最大值。若结果仍为-inf，说明不存在可行路径，返回0。

代码

代码支持：Python3

class Solution: def solve(self, matrix): m, n = len(matrix), len(matrix[0]) @lru_cache(None) def dp(i, j, d): if j < 0 or j >= n: return float('-inf') if i >= m: return 0 if matrix[i][j] == 1: return float('-inf') ans = 1 + max( dp(i+1, j, 0), # 向下 float('-inf') if d == -1 else dp(i, j+1, 1), # 向右（从右边来则禁止） float('-inf') if d == 1 else dp(i, j-1, -1) # 向左（从左边来则禁止） ) return ans ans = max([dp(0, j, 0) for j in range(n)]) return 0 if ans == float('-inf') else ans

为什么现在可以记忆化了？

加入方向状态d后，(i, j, d)三元组唯一确定了当前格子的「可达方向约束」，函数不再依赖或修改任何外部变量，变成了严格的纯函数：

• 相同参数必然得到相同返回值；
• 因此可以被@lru_cache(None)安全缓存，重复子问题只计算一次。

这正是本仓库 动态规划专题 中「记忆化」章节的核心思想：参数确定、返回值确定的数学函数，才能用哈希表缓存中间结果。重叠子问题在这里大量存在——例如从不同路径到达同一个(i, j, d)状态时，后续的最优路径完全一致，无需重复搜索。

复杂度分析

• 时间复杂度：$O(m*n)$ —— 状态总数为 $m * n * 3$（三种方向），每个状态的状态转移为 $O(1)$ 常数操作。
• 空间复杂度：$O(mn)$ —— 递归深度最坏 $O(mn)$，lru_cache缓存规模为 $O(mn3)$，两者同阶。

相比暴力解法的 $O(2^{m*n})$，动态规划将复杂度从指数级降低到了线性级，在n * m ≤ 200,000的约束下可以高效通过。

正确性验证：用示例走一遍

以题目示例的矩阵为例：

matrix = [ [0, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0] ]

• 起点枚举第 0 行的 4 个空格，dp(0, 0, 0)代表从左上角出发。
• 在(0, 0)，方向d = 0，左、右、下都合法；但向下(1, 0)是墙返回-inf，因此只能向右推进。
• 路径沿第 0 行走到(0, 3)后向下进入(1, 3)（d = 0），此时可以向左或向下。
• 在第 1 行向左走到(1, 1)（途中d依次变为-1，禁止回头向右），再向下到(2, 1)，最终在第 2 行向右走到(2, 3)。

整个过程恰好访问 10 个格子，与题目给出的10一致。由于(1, 0)是墙，第 0 列无法连通，不存在经过全部 12 个格子的路径，所以10即为最优解。

边界情况与易错点

1. 检查顺序：必须先做j越界判断再做matrix[i][j]访问，避免越界读取；i >= m返回0放在墙判断之前，保证走出矩阵的虚拟步不贡献长度。
2. 全墙或不可达矩阵：若任何起点都到不了最后一行，ans恒为-inf，必须显式返回0。
3. 单行矩阵：n = 1时，第 0 行即最后一行，任意空格作为起点直接返回1（存在墙则可能为0），上述代码天然正确处理。
4. 方向状态与禁止回退的对应关系：d = -1禁止向右、d = 1禁止向左，二者方向定义容易写反，建议结合「禁止回到上一个格子」的语义验证。

方法对比与总结

这道题的价值在于它揭示了一个普适的 DP 设计技巧：当「路径历史」导致状态无法唯一确定时，与其记录整条路径（visited），不如找出影响未来的「最小历史信息」并将其并入状态。本题中，未来的可达方向只由「来向」这一个信息决定，因此一个d维度就足够替代整个visited集合，从而把不可记忆化的问题变成标准的记忆化递归。

该解法在代码结构上与本仓库中其他使用@lru_cache(None)的经典记忆化题解（如 Consecutive Wins）一脉相承；背后的纯函数、重叠子问题、无后效性等理论基础，可进一步研读本仓库的 动态规划专题，配合本题食用效果更佳。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode