先交代一下背景。前阵子有朋友拿一道题来问我给定一个 m x n 矩阵每个格子上都有一个整数要你找一条长度恰好为 K 的路径使得路径上经过的所有格子数值之和最大移动时只能上下左右走。我当时第一反应是“这不就是搜索题嘛DFS 回溯扫一遍不就行了”。结果他把矩阵规模放到 50x50、K 拉到 20 以后我写的回溯代码跑了几分钟都出不来这才意识到这个“矩阵指定长度路径最大值”远没有第一眼看上去那么简单。这篇文章就把我踩坑、试错、再优化之后整理出的完整思路写下来包括问题边界怎么定义、暴力回溯怎么写、为什么大规模下不容易优化、允许重复访问时的动态规划版本以及工程落地时几个很容易被忽略的细节。如果你也在写类似的地图寻宝、网格奖励最大化、游戏路径规划或者只是刷题遇到过这类型应该都能用得上。1. 先把问题边界钉死长度、移动规则和重复访问很多题之所以做得混乱根本原因是题目条件没对齐。这个标题看起来简单实际上一旦开始写代码就会遇到三个分岔点每个都会直接改变解法选型。1.1 长度参数是格子数而不是步数第一个要确认的问题是“指定长度”到底指的是什么。常见有两种口径路径上经过的格子总数记为 K。移动的步数也就是相邻格子之间边的数量。如果经过 N 个格子那么移动步数是 N-1。很多题解会和稀泥直接写“长度 K”但题目里的小字往往才是关键。我用一个极端例子说明差异2x2 矩阵里四个格子全是 1如果要求路径长度为 3按“格子数”理解从任意角落出发走 3 个格子路径和是 3按“步数”理解走 3 步会经过 4 个格子路径和是 4。同一个 K结果不同代码当然也不同。所以拿到需求后第一件事就是从题目描述里确认“长度是格子数还是步数”。如果对方也说不清我建议统一按“格子数”实现因为它在 DFS 状态里更直观起点已经算第一个格子step 从 1 开始累加到 K 就收敛。后面我所有代码也都按“格子数”这个口径。1.2 允许重复访问的版本和禁止重复访问的版本这个分岔点比起上一条更致命。同样是“找路径最大值”如果允许重复经过同一个格子一条长路径完全可以绕来绕去刷分那就成了一道能用动态规划轻松解决的问题如果不允许重复经过同一个格子路径就变成“自回避路径”状态里必须记录整个访问历史问题难度立刻上升一个量级。我在实际项目里遇到过不止一次需求文档里写“找一条长度为 K 的路径”甲方自己都没想清楚能不能走回头路。最后问下来很多场景其实允许重复走只是当时没意识到会产生这种分支。所以拿到题目先反问自己一句这一步从 A 走到 B下一步能从 B 走回 A 吗如果允许重复用动态规划时间复杂度可以做到 O(KMN*4)工程上几乎无障碍。如果不允许重复最常规的思路是 DFS 回溯加剪枝但复杂度是指数级的后面我会详细算这笔账。1.3 输入规模决定了解法天花板还有一个隐藏条件矩阵到底多大。这直接决定你该选什么算法。我见过不少人在小矩阵上验证过回溯没问题就贸然上了大矩阵结果线上直接超时。我习惯先按规模分档矩阵规模目标 K推荐方案备注M,N 5K 10暴力 DFS保证正确代码最简单M,N 20K 15DFS 剪枝剪枝有效能跑出结果M,N 50K 25近似 / 启发式精确求解大概率不可行任意规模任意 K允许重复动态规划多项式时间搞定这里没有写“固定公式”因为实际耗时还取决于矩阵里数值分布。如果数值全是正数上界剪枝会很猛如果数值正负混杂剪枝效果就会差不少。总之先确认规模和约束再决定要不要上高级方案。2. 暴力回溯正确但粗暴的基线解法不管最终用多花哨的优化我都建议先写一份最小可用的暴力回溯。这不仅是零基础最容易理解的做法也是后面验证优化版是否正确的对照基准。2.1 回溯的递归框架与关键状态回溯的思路很简单枚举每个格子作为起点每次从当前位置向四个方向尝试走一步用 visited 数组记录哪些格子已经在当前路径里防止走重复走到步数等于 K 时更新全局最大值。这里的关键点是递归函数需要携带四个信息当前坐标 x, y。当前已经走了多少个格子也等于当前路径长度。当前累计路径和。已访问集合通常用二维布尔数组。我一开始犯过一个错误只记录坐标和当前和想用类似 DP 的方式合并状态。但题目一旦要求“不能重复访问”同样的坐标、同样的长度、不同的访问历史未来能走的路线是完全不同的。所以不能简单合并必须把访问历史纳入状态。一个最小可用版本如下def max_path_sum(grid, K): m, n len(grid), len(grid[0]) visited [[False] * n for _ in range(m)] best float(-inf) dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) def dfs(x, y, step, total): nonlocal best if step K: best max(best, total) return # 简单上界剪枝剩余格子全按最大格子值算也追不上当前 best max_cell max(max(row) for row in grid) if total max_cell * (K - step) best: return for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and not visited[nx][ny]: visited[nx][ny] True dfs(nx, ny, step 1, total grid[nx][ny]) visited[nx][ny] False for i in range(m): for j in range(n): visited[i][j] True dfs(i, j, 1, grid[i][j]) visited[i][j] False return best if best ! float(-inf) else None这段代码能正确跑通小矩阵。比如一个 3x3 的矩阵K5基本瞬间出结果。但它的性能表现在大矩阵上非常差原因在递归树太大了。2.2 基础剪枝边界、死路、上下界暴力回溯写出来之后下一步就是剪枝。剪枝的目的不是改变正确答案而是提前砍掉确定不可能超过当前最优解的分支。先说边界剪枝。坐标越界的格子直接跳过这是最基础的但很多人会把判断写错比如把行和列搞反。我建议统一用 0 nx m 和 0 ny n不要省括号省得后面调试半天。第二个是上界剪枝。当前累计和 total剩余还需要走 K-step 个格子即使后面每个格子都取矩阵里的最大值 max_cell理论上限也是 total max_cell * (K-step)。如果这个上限都已经小于等于当前 best那这个分支再怎么走也不可能创造新纪录可以直接 return。这个剪枝实现简单但在全正数矩阵里效果非常明显。因为它会让搜索越来越倾向于沿着高值格走一旦找到一条比较优的路径其他低分路径会在很浅的深度被砍掉。第三个是方向排序。在遍历四个方向之前先按邻居格子的数值从大到小排序。这样做的好处是让“看起来更有希望”的路径先被探索尽快刷新 best。best 越大后面的上界剪枝就越强。排序本身不改变正确性但能显著影响剪枝触发的时间。我自己实测过一个 10x10 矩阵、K14 的例子不加方向排序时递归状态数有上百万加上排序后有时候几十万就收敛了。如果你追求极致的剪枝效果甚至可以把邻居按“当前累计和邻居值”排序虽然多花一点排序时间但通常值得。2.3 小规模矩阵的实测表现为了确认基线代码没有写错我一般会先跑一组小数据用手工推演核对答案。比如下面这个 3x3 矩阵1 -2 3 4 5 -6 7 8 -9找 K5 的最大路径和。手工大概推一下最理想的是从右下角的 -9 附近绕到 7、8、5、4、1 这些高值格子但要考虑不能重复和连通性。用上面的回溯代码跑正确答案是从 (2,1) 的 8 出发走到 (2,0)7再到 (1,0)4再到 (0,0)1再到 (0,2)3总和 23或者从 8 出发到 5 到 4 到 7 到 1则看连通路径必须相邻。这类小规模测试的核心意义不是性能而是验证状态转移和 visited 逻辑。等小数据确认无误后再逐步把矩阵调大观察耗时。如果 K 涨到 20状态数往往会膨胀到千万甚至亿级这时候你就知道该上剪枝、换算法或者重新和需求方确认条件了。3. 复杂度真相指定长度路径为什么这么难优化很多人知道回溯慢但说不清它到底慢在哪。这里我把账算清楚避免你盲目相信“加几层剪枝就能解决一切”。3.1 最坏情况下的状态树有多大在不允许重复访问的情况下从某个起点出发第一步最多有 4 个选择之后每一步理论上还有 4 个方向但其中至少有一个方向是刚刚走过来的格子已经被访问所以大多数情况下最多 3 个新的选择。因此从单个起点出发粗略的状态数是 4 * 3^(K-1) 这个级别。再乘上所有起点数 M*N整体就是O(M * N * 3^K)这里省略了一些常数项但足够说明问题。取 K203^20 大约 34.8 亿这还只是粗略数量级。即使剪枝能砍掉大部分20 左右的长度依然会让纯回溯在几十乘几十的矩阵上吃紧。有个很容易误解的地方是K 小的时候比如 K15你可能会觉得 3^15 只有 1400 万配合剪枝完全能跑。但别忘了乘上 M*N。如果是 100x100 的矩阵那就是 14 亿的基数哪怕剪枝砍掉 90%也还有上亿次递归调用。所以“看起来固定 K 不是很大”和“实际能跑完”之间往往差着几个数量级。3.2 和经典 NP 难问题的关系如果你去翻算法理论会发现“在图中寻找一条长度至少为 K 的简单路径”是经典的 NP 难问题网格图并不比一般图简单多少。这也就是说除非 PNP否则不存在对所有规模都能在多项式时间内精确求解的算法。这一点很反直觉矩阵本身是规则网格移动方向也只有四个怎么还会难关键在于“不能重复访问”这个约束。有了它路径就带上了“记忆”不同历史路径即使终点相同也不能简单合并状态。一旦不能合并状态状态数量就会随着 K 指数爆炸。那有没有理论上的精确优化手段有比如针对“固定 K”的参数化算法使用颜色编码或代数技巧能把复杂度压到 2^K 乘以多项式级别。但这类算法实现复杂、常数大在工程上很少直接用。对绝大多数人来说知道“大致上什么规模能算、什么规模不能算”更重要。3.3 三条常见优化路线的性价比我梳理一下实际中可以考虑的三条路线按性价比从高到低排分支限界加剪枝适合中等规模代码改动小不改变正确性。核心是把上界估计做得更准比如预先计算每个格子周围若干步内的可达最大值代替简单的全局最大值。剪枝更强但计算上界本身也有成本。启发式近似适合大规模且对结果精度要求不高的场景。常见有贪心加局部搜索、模拟退火、遗传算法。它们不保证最优但能在有限时间内给一个不错的结果。随机化参数算法适合理论研究和 K 相对较小的特殊场景。实现复杂度高我没在实际项目里用过几次一般作为学术讨论。这里有个经验如果你的需求方只要求“尽量大”而不是“必须最大”那就直接上启发式不要跟 NP 难较劲。反之如果必须精确那就要在输入规模上做限制否则强行跑精确算法只会让大家一起等死。4. 允许重复访问的变体动态规划才是正解如果需求确认过路径可以重复访问那前面讨论的复杂度陷阱就都不存在了。这个问题可以从“搜索”直接降维成“动态规划”代码既短又稳。4.1 状态设计与转移方程因为每一步只关心当前在哪个格子以及已经走了多少格不再关心历史的访问集合所以状态可以定义为dp[k][i][j] 表示恰好经过 k 个格子、当前停在 (i, j) 的路径最大总和。初始状态很好理解k1 时路径只有一个格子dp[1][i][j] grid[i][j]。转移时当前在第 (i, j) 个格子那么路径的倒数第二格一定是它的上、下、左、右邻居之一。所以dp[k][i][j] max(dp[k-1][ni][nj] over neighbors (ni,nj)) grid[i][j]这个方程的重点在于“从邻居走到当前格”所以最后加的是 grid[i][j]而不是 grid[ni][nj]。很多人第一次写会把加的位置弄反。代码实现如下def max_path_sum_repeatable(grid, K): m, n len(grid), len(grid[0]) NEG float(-inf) prev [[NEG] * n for _ in range(m)] for i in range(m): for j in range(n): prev[i][j] grid[i][j] dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) for _ in range(2, K 1): cur [[NEG] * n for _ in range(m)] for i in range(m): for j in range(n): best_prev NEG for dx, dy in dirs: ni, nj i dx, j dy if 0 ni m and 0 nj n: best_prev max(best_prev, prev[ni][nj]) if best_prev ! NEG: cur[i][j] best_prev grid[i][j] prev cur return max(max(row) for row in prev)这段代码的时间复杂度是 O(KMN4)空间通过滚动数组压到了 O(MN)。就算矩阵是 1000x1000、K 是 100也能在很短时间内算完因为每一步都是固定四个邻居的简单循环。4.2 滚动数组和路径重构上面代码已经用了滚动数组prev 保存上一个 k 的答案cur 保存当前 k 的答案。如果你只需要最大值这样就够了。但有时候产品还想要“具体是哪条路径”。那就需要额外用一个 parent 数组记录每个状态是从哪个邻居转移来的。等 dp 算完后从最优终点倒推回去就能还原整条路径。路径重构有一个细节因为用的是滚动数组parent 信息最好按 k 分多层保存否则后面 k 会把前面的覆盖掉。我一般直接用三维数组 parents[k][i][j] 记录前驱坐标虽然内存大一点但换来的调试便利很值得。还要注意由于允许重复访问最优路径完全可能是一条来回刷高值格子的路线。比如某个格子值是 100周围全是负数那最优策略就是来回走这个格子。我们经常笑称这是“刷步数”但在需求允许的情况下这是完全合法的答案。4.3 数值溢出和负权值处理矩阵里的数值可能全是负数所以不能用 0 来初始化 dp。否则会得到一个错误结果0 比任何负数和都大。上面代码里我用 float(-inf) 初始化为负无穷保证每个状态都是从真实可达的前驱转移来的。如果你用的是 Java 或 C建议用一个足够小的负数常量比如 Integer.MIN_VALUE / 4避免溢出。Python 的 float(-inf) 用起来方便但在大型矩阵里可能会有精度问题如果你想完全用整数也可以用 None 表示不可达再单独判断。另外如果路径允许原地停留即下一步可以不走停在原格子那转移方程里需要把自身也作为邻居之一。不过这种题目变体相对少见实现时注意按题意多问一句就好。5. 工程落地时最容易被低估的细节算法思路讲完了但实际写代码和调优的过程中还有几个细节会让人卡住。这里单独拎出来说一说。5.1 已访问标记用布尔数组还是哈希集合DFS 里标记已访问有很多种写法。初学者喜欢用 Python 的 set 保存访问过的坐标比如 visited.add((x, y))。好处是代码直观坏处是每次递归都要创建并销毁大量元组频繁哈希性能损耗非常大。如果矩阵大小在几百乘几百以内我强烈建议直接用二维布尔数组访问和回溯都是 O(1)比 set 快好几倍。还有人会用“修改矩阵本身”的方式做标记比如把当前格子的值改成 None 或一个特殊值回溯时再恢复。这个思路在特定的全局搜索题目里很常见但用在这道题上要小心矩阵值本身可能有负数、零、或者恰好等于特殊值。如果格子值允许任意整数你就不能保证不会撞车。所以我最终的推荐是用二维布尔数组做 visited不要省这份空间。5.2 剪枝评估函数的调用顺序同样是上界剪枝评估函数放在递归开头还是放在遍历邻居时效果差别很大。我一般先判断“当前 total 加上乐观上界是否小于 best”再进入方向循环如果剪枝条件成立连邻居遍历都不做。方向排序的细节也值得说。排序时建议按“从当前格子能到达的邻居值”从大到小排而不是永远固定上下左右顺序。如果邻居里有负值优先走负值只会让 total 降得更快进而更容易触发上界剪枝反而不容易先找到好答案。我在实际调试时会给 DFS 加一个计数器统计状态进入次数。优化前后对比剪枝顺序调对了状态数可能下降到十分之一效果立竿见影。5.3 无法精确求解时的替代方案如果矩阵大、K 大、又不允许重复访问精确计算已经无望我通常走这几条路第一和需求方确认是否能把“路径”改成“子序列”。如果只要求选出一组连通但不必严格枚举的格子问题会简化很多。第二用近似方法。最省事的贪心是从每个可能的起点出发每步选择当前能走的邻居里值最大的格子直到走满 K 格取所有起点里的最大值。这个方案很容易陷入局部最优但作为基线参考很有用。再往上可以加随机重启、模拟退火对结果不满意就多跑几轮。第三给结果加一个上界评估让决策者知道答案离理论上限还有多远。虽然是近似解但至少心里有数。我自己遇到这类需求时一般会先在文档里写清楚“该问题在禁止重复访问的前提下是 NP 难的精确算法只能支持到一定规模”然后给出两条路线让需求方选要么缩小 K 和矩阵规模要么接受近似解。很多时候对方听完就理解了。最后再分享一个我自己的习惯拿到这类题先不急着写优化先用最小例子跑通暴力版得到正确结果后把它当成测试用例反复验证后续的剪枝版、动态规划版。剪枝写得越强越容易因为判断条件写错而把正确答案剪掉。我踩过不止一次这种坑所以现在每次修改完都会把暴力解和新解放在同一组随机数据上对比确认结果一致才敢继续往下调。这个问题看起来小但真到线上跑数据的那一刻你就知道前面这些工作有多重要。