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)表示「此路不通」。不可访问点包括三类边界外的点j 0或j n已经访问过的点(i, j) in visited有障碍物的点matrix[i][j] 1这种解法本质上是暴力枚举所有可能的路径没有任何剪枝与复用。代码代码支持Python3class 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(i1, j), dp(i,j1), 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)不是纯函数。本仓库的 动态规划专题 明确指出可用于记忆化的递归函数必须满足两个条件递归函数不依赖外部变量递归函数不改变外部变量只有满足这两点函数才能保证「参数一定返回值也一定确定」从而可以安全地缓存记忆化。而我们的暴力解法中dp依赖并修改了外部变量visited同一个(i, j)在visited中已有其他格子的不同组合下返回值是不同的——这取决于「当前是从哪条路径走过来的」。因此dp(i, j)的结果不唯一直接对其做lru_cache会导致错误地复用一个路径上下文下的结果。这本质上违反了动态规划的「无后效性」要求子问题的解一旦确定就不再受后续决策影响见 无后效性详解。那么如何解决有两种方向把 visited 序列化进函数参数状态空间变为 $O(2^{m*n})$ 量级空间必然爆炸不可行。想办法去掉 visited让状态只由坐标 少量附加信息唯一确定恢复纯函数性。这就是下文动态规划解法的核心。思路二动态规划 —— 记录「如何过来的」状态思路去掉 visited 的关键在于回答一个问题站在格子(i, j)时有哪些方向是「回头路」需要禁止仔细分析当前格子的来向只可能有三种情况当前是从上方格子向下移动过来的此时三个方向左、右、下都合法因为上方的格子不会与左右冲突。当前是从左边格子向右移动过来的此时可以继续向右或向下但不可以向左否则立刻回到上一个格子。当前是从右边格子向左移动过来的此时可以继续向左或向下但不可以向右否则立刻回到上一个格子。因此只需要在状态中多记录一个维度d——「我是从哪个方向来到当前格子的」就能唯一确定哪些方向被禁止从而完全去掉visited恢复记忆化动态规划的可行性。状态定义与转移定义dp(i, j, d)表示「从格子(i, j)出发走到最后一行能访问的最多格子数」其中方向状态d约定如下d含义0从上方格子向下而来或作为第 0 行的起始状态-1从右边格子向左而来禁止再向右1从左边格子向右而来禁止再向左转移方程为dp(i, j, d) 1 max( dp(i1, j, 0), # 向下新方向 d 0永远允许 dp(i, j1, 1) 若 d ! -1, # 向右新方向 d 1若从右边来则禁止 dp(i, j-1, -1) 若 d ! 1 # 向左新方向 d -1若从左边来则禁止 )终止条件与暴力解法一致j越界返回-infi m返回0走出最后一行后不再贡献格子数相当于路径在最后一行自然结束matrix[i][j] 1墙返回-inf。起始状态第 0 行的每个空格都可以作为起点且起点没有来向限制因此取dp(0, j, 0)的最大值。若结果仍为-inf说明不存在可行路径返回0。代码代码支持Python3class 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(i1, j, 0), # 向下 float(-inf) if d -1 else dp(i, j1, 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即为最优解。边界情况与易错点检查顺序必须先做j越界判断再做matrix[i][j]访问避免越界读取i m返回0放在墙判断之前保证走出矩阵的虚拟步不贡献长度。全墙或不可达矩阵若任何起点都到不了最后一行ans恒为-inf必须显式返回0。单行矩阵n 1时第 0 行即最后一行任意空格作为起点直接返回1存在墙则可能为0上述代码天然正确处理。方向状态与禁止回退的对应关系d -1禁止向右、d 1禁止向左二者方向定义容易写反建议结合「禁止回到上一个格子」的语义验证。方法对比与总结方法核心思想时间复杂度空间复杂度结论暴力 DFSvisited集合防重复访问枚举全部路径$O(2^{m*n})$$O(m*n)$超时TLE记录来向的 DP状态(i, j, d)表达回退约束去掉visited恢复纯函数后记忆化$O(m*n)$$O(m*n)$可 AC这道题的价值在于它揭示了一个普适的 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
leetcode 题解：Longest Matrix Path Length —— 从暴力 DFS 到去除 visited 的状态记忆化动态规划
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)表示「此路不通」。不可访问点包括三类边界外的点j 0或j n已经访问过的点(i, j) in visited有障碍物的点matrix[i][j] 1这种解法本质上是暴力枚举所有可能的路径没有任何剪枝与复用。代码代码支持Python3class 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(i1, j), dp(i,j1), 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)不是纯函数。本仓库的 动态规划专题 明确指出可用于记忆化的递归函数必须满足两个条件递归函数不依赖外部变量递归函数不改变外部变量只有满足这两点函数才能保证「参数一定返回值也一定确定」从而可以安全地缓存记忆化。而我们的暴力解法中dp依赖并修改了外部变量visited同一个(i, j)在visited中已有其他格子的不同组合下返回值是不同的——这取决于「当前是从哪条路径走过来的」。因此dp(i, j)的结果不唯一直接对其做lru_cache会导致错误地复用一个路径上下文下的结果。这本质上违反了动态规划的「无后效性」要求子问题的解一旦确定就不再受后续决策影响见 无后效性详解。那么如何解决有两种方向把 visited 序列化进函数参数状态空间变为 $O(2^{m*n})$ 量级空间必然爆炸不可行。想办法去掉 visited让状态只由坐标 少量附加信息唯一确定恢复纯函数性。这就是下文动态规划解法的核心。思路二动态规划 —— 记录「如何过来的」状态思路去掉 visited 的关键在于回答一个问题站在格子(i, j)时有哪些方向是「回头路」需要禁止仔细分析当前格子的来向只可能有三种情况当前是从上方格子向下移动过来的此时三个方向左、右、下都合法因为上方的格子不会与左右冲突。当前是从左边格子向右移动过来的此时可以继续向右或向下但不可以向左否则立刻回到上一个格子。当前是从右边格子向左移动过来的此时可以继续向左或向下但不可以向右否则立刻回到上一个格子。因此只需要在状态中多记录一个维度d——「我是从哪个方向来到当前格子的」就能唯一确定哪些方向被禁止从而完全去掉visited恢复记忆化动态规划的可行性。状态定义与转移定义dp(i, j, d)表示「从格子(i, j)出发走到最后一行能访问的最多格子数」其中方向状态d约定如下d含义0从上方格子向下而来或作为第 0 行的起始状态-1从右边格子向左而来禁止再向右1从左边格子向右而来禁止再向左转移方程为dp(i, j, d) 1 max( dp(i1, j, 0), # 向下新方向 d 0永远允许 dp(i, j1, 1) 若 d ! -1, # 向右新方向 d 1若从右边来则禁止 dp(i, j-1, -1) 若 d ! 1 # 向左新方向 d -1若从左边来则禁止 )终止条件与暴力解法一致j越界返回-infi m返回0走出最后一行后不再贡献格子数相当于路径在最后一行自然结束matrix[i][j] 1墙返回-inf。起始状态第 0 行的每个空格都可以作为起点且起点没有来向限制因此取dp(0, j, 0)的最大值。若结果仍为-inf说明不存在可行路径返回0。代码代码支持Python3class 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(i1, j, 0), # 向下 float(-inf) if d -1 else dp(i, j1, 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即为最优解。边界情况与易错点检查顺序必须先做j越界判断再做matrix[i][j]访问避免越界读取i m返回0放在墙判断之前保证走出矩阵的虚拟步不贡献长度。全墙或不可达矩阵若任何起点都到不了最后一行ans恒为-inf必须显式返回0。单行矩阵n 1时第 0 行即最后一行任意空格作为起点直接返回1存在墙则可能为0上述代码天然正确处理。方向状态与禁止回退的对应关系d -1禁止向右、d 1禁止向左二者方向定义容易写反建议结合「禁止回到上一个格子」的语义验证。方法对比与总结方法核心思想时间复杂度空间复杂度结论暴力 DFSvisited集合防重复访问枚举全部路径$O(2^{m*n})$$O(m*n)$超时TLE记录来向的 DP状态(i, j, d)表达回退约束去掉visited恢复纯函数后记忆化$O(m*n)$$O(m*n)$可 AC这道题的价值在于它揭示了一个普适的 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
