蓝桥杯的算法提高题里“最大值路径”估计是很多人的老朋友。题目描述很简单一个n行m列的矩阵从左上角走到右下角每次只能向右或向下问路径上经过的数字之和最大是多少。我第一次看到这题时觉得没什么难度随手写了个深搜交上去结果超时这才老老实实去研究递归、记忆化搜索和动态规划的关系。今天就把这个完整的思考过程拆开讲清楚从暴力递归一步步优化到滚动数组版动态规划顺带解决路径还原和细节坑点。适合正在刷蓝桥杯、或者刚接触动态规划想搞懂“递归和DP到底啥关系”的同学也能帮你把“最大值路径”这类网格DP模板彻底吃透。1. 题目理解与思路框架1.1 题目到底在求什么先明确题目细节。输入一个n行m列的整数矩阵每个格子里有一个整数可能是正数、负数或者0从左上角出发只能向右或者向下移动最终到达右下角。要求找出一条路径使得路径经过的所有格子上的数字之和最大输出这个最大值。举个例子一个3行3列的矩阵1 2 3 4 5 6 7 8 9从左上角到右下角显然贴着行走再贴着列走1→2→3→6→9或者先下后右1→4→7→8→9都行两条路径的和分别是21和29所以最大值是29。如果矩阵里出现负数问题就没那么直观了比如某个格子是-100你可能会为了避开它绕路但绕路也可能损失更多。所以本质上这是个“在约束条件下做选择”的优化问题可选择的路径数量非常大。为什么说路径数量大n行m列的矩阵从左上到右下一共需要走(n-1)步向下、(m-1)步向右总共步数是固定的nm-2路径的差异只是决定哪几步向下。因此路径总数是组合数C(nm-2, n-1)。当n和m都等于15时这个数已经超过4千万当n20、m20时C(38,19)大约是3.5亿。暴力枚举每一条路径再比较总和完全不可行。所以题目考察的核心就是如何避免指数级枚举利用最优子结构快速得到答案。这也是蓝桥杯“算法提高”这个标签下很典型的一类题——不考偏难怪就考你对基础算法的理解深度。1.2 为什么递归和动态规划是天生一对初学者最容易想到的做法是递归。递归的好处是思路直接站在某个格子上要么从上面过来要么从左边过来那我只要知道“从起点到上面那个格子的最大路径和”和“从起点到左边那个格子的最大路径和”取大的那个再加上当前格子的值就是“从起点到当前格子的最大路径和”。这个逻辑可以一直往前推直到回到起点。这其实就是动态规划的核心思想把大问题拆成小问题小问题的解组合成大问题的解。但递归如果不做任何优化会存在大量重复计算。比如计算右下角格子时需要上面和左边的结果计算上面那个格子时又需要它的上面和左边……这个过程会反复计算同一个格子很多次。递归负责“自顶向下拆解”动态规划负责“自底向上填表”而记忆化搜索则站在中间用缓存把递归里重复的计算消掉。理解这个递进关系比单纯背模板重要得多。下面我先把最原始的递归写出来看看它为什么慢然后再一步步优化。如果你已经能直接写出动态规划也可以顺着看很多细节坑是只有实际提交以后才会碰到的。2. 递归写法先跑通再说2.1 递归函数怎么设计递归函数最核心的是定义dfs(x, y)表示从起点(0,0)走到(x,y)的最大路径和。既然只能向右和向下那么到达(x,y)的上一步只能是(x-1,y)或者(x,y-1)也就是从上面来或者从左边来。于是状态转移方程就出来了dfs(x, y) max(dfs(x-1, y), dfs(x, y-1)) a[x][y]递归出口当x0且y0时最大路径和就是a[0][0]本身不需要往前找。如果x或y小于0说明越界了返回一个特别小的负数即可。用C实现最朴素的版本如下#include bits/stdc.h using namespace std; int n, m; int a[105][105]; const int NEG -1e9; int dfs(int x, int y) { if (x 0 || y 0) return NEG; if (x 0 y 0) return a[0][0]; return max(dfs(x - 1, y), dfs(x, y - 1)) a[x][y]; } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } cout dfs(n - 1, m - 1) endl; return 0; }这个代码逻辑完全正确小数据下能跑出答案。但你千万别拿它提交因为n、m稍微大一点就会超时。我当初就是不信邪拿10×10的矩阵试了一下瞬间出结果以为没问题换15×15的矩阵就开始卡顿到了20×20基本等不出结果了。这是典型的指数爆炸。2.2 递归到底慢在哪我们可以画一下递归调用树。dfs(2,2)会调用dfs(1,2)和dfs(2,1)这两个又分别会调用dfs(0,2)、dfs(1,1)、dfs(1,1)、dfs(2,0)。注意dfs(1,1)被计算了两次。再往下重复的更多。这个调用树的规模是近似O(2^(nm))的因为每个状态会分裂成两个子状态不做任何缓存的话计算量是路径数量的指数级别。更直观地说递归代码的执行过程像一棵不断分叉的树每个叶子节点对应一个起点状态。树的节点数远远大于矩阵格数。可实际上dfs(x,y)的结果只和坐标x,y有关最多n×m种不同的参数组合。也就是说理论上只要把每个格子的结果存起来复杂度应该是O(n×m)才对。递归之所以慢就是因为没有“记性”同一组参数每次都要从头算一遍。这就是优化方向。常见的两个办法记忆化搜索保留递归的“自顶向下”结构但把算过的结果存进数组下次直接取。纯动态规划改变计算顺序从起点开始一层层填表每个格子只算一次也不会重复。两条路本质相同但很多蓝桥杯教程会直接给你动态规划代码导致你忽略了它们之间的联系。我建议你先看懂记忆化再去看递推这样以后再遇到“记忆化搜索能过但递推写不出来”的题心里就不慌了。3. 记忆化搜索递归加个缓存就够了3.1 加一个数组复杂度立刻降下来记忆化搜索的做法很简单额外开一个memo数组初始化为-1或者某个不可能取到的值。每次进入dfs(x,y)先检查memo[x][y]是否算过算过就直接返回没算过就正常递归计算把结果存进memo再返回。代码改起来非常少#include bits/stdc.h using namespace std; int n, m; int a[105][105]; int memo[105][105]; const int NEG -1e9; int dfs(int x, int y) { if (x 0 || y 0) return NEG; if (x 0 y 0) return a[0][0]; if (memo[x][y] ! -1) return memo[x][y]; return memo[x][y] max(dfs(x - 1, y), dfs(x, y - 1)) a[x][y]; } int main() { cin n m; for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } memset(memo, -1, sizeof(memo)); cout dfs(n - 1, m - 1) endl; return 0; }这里有个小细节memset(memo, -1, sizeof(memo))把每个字节都设成-1所以整个int数组每个元素都是-1这是正确的。如果矩阵里可能出现-1那-1就不能作为“没算过”的标记了可以改成初始化为0再用一个vis数组标记。不过本题通常都是非负整数用-1没问题。为了稳妥我更推荐初始化为一个特殊大负数比如memo[x][y] NEG但NEG本身可能也是合法答案所以最好单独用一个vis[x][y]布尔数组。很多老手嫌麻烦直接用0当标记结果矩阵里有0时就出bug这个后面在常见问题里细说。3.2 记忆化搜索为什么快加了这一行缓存后每个坐标(x,y)最多只被真正计算一次。总的状态数是n×m个每个状态内部只做两次递归调用的查询和一次加法所以总时间复杂度是O(n×m)空间复杂度也是O(n×m)。这就是典型的空间换时间。你可以把记忆化搜索理解成“懒惰的动态规划”递归调用树还是那颗树但一旦某个节点算出了结果就把这个结果挂在树的节点上后续任何分支走到这个节点不再往下展开直接摘果子。这样每个节点最多被展开一次树的规模就被压缩成了网格本身。需要提醒的是递归深度问题依然存在。n、m如果到了几百几千递归层数可能等于路径长度nm而系统栈一般只有几MB脆弱的很。蓝桥杯训练系统里矩阵规模往往不大记忆化能过但如果遇到大矩阵递归本身也可能爆栈这时候还是得写递推版本。下一节我就改成纯动态规划顺便讲清楚为什么递推不会爆栈。4. 动态规划实现正向递推与细节4.1 DP状态定义与转移方程动态规划用递推的方式从起点开始逐个计算dp[i][j]表示从(0,0)走到(i,j)的最大路径和。转移方程和递归一模一样dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]但这里必须处理边界情况。当i0时dp[i-1][j]不存在只能从左边过来当j0时dp[i][j-1]不存在只能从上面过来当i0且j0时它是起点直接等于a[0][0]。如果不加处理数组越界会让你拿到一个莫名其妙的随机值结果全错。处理边界有三种常见写法第一种在循环里加判断像这样for (int i 0; i n; i) { for (int j 0; j m; j) { if (i 0 j 0) { dp[i][j] a[0][0]; } else { int best NEG; if (i 0) best max(best, dp[i-1][j]); if (j 0) best max(best, dp[i][j-1]); dp[i][j] best a[i][j]; } } }第二种先把第一行和第一列单独初始化。因为第一行的格子只能从左往右走所以dp[0][j] dp[0][j-1] a[0][j]第一列的格子只能从上往下走所以dp[i][0] dp[i-1][0] a[i][0]。然后再从(1,1)开始套标准转移方程。这种写法代码更短逻辑更清晰。第三种也是最推荐的做法把dp数组开大一圈用1-based下标同时把“虚拟边界”设成负无穷这样就不需要特判了。我平时刷题喜欢用这个因为不容易漏判。#include bits/stdc.h using namespace std; int a[105][105]; int dp[105][105]; int main() { int n, m; cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) dp[i][0] -1e9; for (int j 0; j m; j) dp[0][j] -1e9; dp[0][1] 0; // 关键让(1,1)可以从“虚拟起点”转移过来 for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]; } } cout dp[n][m] endl; return 0; }这个技巧很实用。把下标从1开始就可以把“向左越界”“向上越界”统一成“dp[0][j]和dp[i][0]都是负无穷”。但注意dp[0][1]必须初始化为0这样dp[1][1]才会等于max(dp[0][1], dp[1][0]) a[1][1] max(0, 负无穷) a[1][1] a[1][1]。如果忘了设dp[0][1]0起点的值就会被污染成负无穷加上a[1][1]。这个坑我踩过一次排查了很久才发现是初始化顺序的问题。4.2 完整二维DP代码综合上面的思路给你一个可以直接提交、风格偏向蓝桥杯环境的完整版本#include bits/stdc.h using namespace std; const int MAXN 105; const int NEG -1e9; int n, m; int a[MAXN][MAXN]; int dp[MAXN][MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } for (int i 0; i n; i) dp[i][0] NEG; for (int j 0; j m; j) dp[0][j] NEG; dp[0][1] 0; for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]; } } cout dp[n][m] endl; return 0; }如果你担心矩阵里的数字可能比-1e9还小可以把NEG改成-0x3f3f3f3f这是C里常用的“负无穷”写法表示一个很大的负数但相加时不会溢出到正数。这里用-1e9已经足够因为一般的矩阵元素范围不会超过万级别。4.3 滚动数组把空间压到O(m)蓝桥杯对内存的限制通常宽松但很多后续题目会卡空间或者你希望把代码写得更好看滚动数组是必学技能。观察转移方程dp[i][j]只依赖dp[i-1][j]上一行同列和dp[i][j-1]本行前一列。也就是说算当前行时我只需要保留上一行的数据更早的行完全没用。于是可以用一维数组dp[j]来滚动更新。当我在第i行从左到右计算时dp[j]在更新前存放的是上一行第j列的值正好代表dp[i-1][j]dp[j-1]在更新后存放的是当前行第j-1列的值正好代表dp[i][j-1]。所以更新公式变为for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 j 1) { dp[j] a[1][1]; } else { int best NEG; if (j 1) best max(best, dp[j-1]); if (i 1) best max(best, dp[j]); dp[j] best a[i][j]; } } }但这样特判太多。更优雅的做法是结合“虚拟边界”思想先给dp数组填上NEG然后令dp[1] 0从第一行开始循环注意每一行第一个元素的左侧不存在所以j从1开始dp[j-1]可能还是上一行的旧值等一下这里需要仔细分析。其实滚动数组加1-based下标最简单的写法如下vectorint dp(m 1, NEG); dp[1] 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 j 1) dp[j] a[i][j]; else dp[j] max(dp[j], dp[j-1]) a[i][j]; } } cout dp[m] endl;这里有个很微妙的点当i1且j1时如果直接执行max(dp[1], dp[0]) a[1][1]dp[1]初始为0dp[0]是NEG结果也是a[1][1]所以其实不需要特判。因为dp[1]在进入循环时被设成0了相当于虚拟起点。直接写vectorint dp(m 1, NEG); dp[1] 0; for (int i 1; i n; i) { for (int j 1; j m; j) { dp[j] max(dp[j], dp[j-1]) a[i][j]; } }验证一下。第一行第一列dp[1] max(0, NEG) a[1][1] a[1][1]正确。第一行第二列此时dp[2]还是上一行其实是初始NEGdp[1]已经被更新成a[1][1]所以dp[2] max(NEG, a[1][1]) a[1][2] a[1][1]a[1][2]这正是第一行从左到右累加正确。第二行第一列此时dp[1]是第一行的a[1][1]还没被本行覆盖因为j从1开始先更新j1dp[0]是NEG所以dp[1] a[1][1] a[2][1]这是从上往下的路径正确。第二行第二列dp[2]当前还是第一行第二列的“从左上累加到第一行第二列”的值dp[1]是第二行第一列的值取max再加a[2][2]完美。这个写法堪称优雅但初学者很容易晕。我强烈建议你亲手在纸上画一个3×3矩阵一步步模拟这个一维数组的变化。画完以后你对滚动数组的理解会超过很多人。5. 路径还原与扩展问题5.1 如何把最大路径本身输出出来有些题目不只要最大值还要求输出路径比如经过的格子坐标或者格子里的值。动态规划只能告诉你最大值是多少要想知道走哪条路得额外记录“决策”。一个简单的办法是开一个pre[i][j]数组记录dp[i][j]是从哪个方向转移过来的。比如pre[i][j]0表示从上方来即dp[i-1][j]更大pre[i][j]1表示从左方来即dp[i][j-1]更大。然后从终点倒推回起点把路径逆序存下来再正序输出。参考代码int pre[MAXN][MAXN]; // 0:从上, 1:从左 for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 j 1) { dp[i][j] a[i][j]; } else if (i 1) { dp[i][j] dp[i][j-1] a[i][j]; pre[i][j] 1; } else if (j 1) { dp[i][j] dp[i-1][j] a[i][j]; pre[i][j] 0; } else { if (dp[i-1][j] dp[i][j-1]) { dp[i][j] dp[i-1][j] a[i][j]; pre[i][j] 0; } else { dp[i][j] dp[i][j-1] a[i][j]; pre[i][j] 1; } } } } vectorpairint,int path; int i n, j m; while (i 1 j 1) { path.push_back({i, j}); if (i 1 j 1) break; if (pre[i][j] 0) i--; else j--; } reverse(path.begin(), path.end());注意当两个方向的值相等时我们选择任意一个都行这里我选了“优先从上边来”。这个不会影响最大值的正确性因为两个方向得到的结果一样大。如果你把pre数组想象成“路标”从终点一路沿着路标走就能回到起点写起来非常直观。另外如果你用的是记忆化搜索回溯路径也很方便。在dfs里当max(dfs(x-1,y), dfs(x,y-1))求得后判断哪边更大就往哪边递归打印。但要注意递归打印会先输出起点到终点的顺序和dp回溯正好相反需要处理好顺序。5.2 变形负权重、起点终点变体、求最小路径和“最大值路径”这个模型非常经典稍微改一改就是另一道题。第一种变形矩阵里可能出现负数。很多新手以为动态规划只能处理非负数其实完全不是。我们的dp转移是max操作天然支持负数只要初始化边界时用负无穷而不是用0。如果你初始化为0遇到全负数的矩阵结果可能变成0那就错了。判断一个dp模板是否正确最狠的测试就是全负数矩阵。第二种变形求最小路径和。把max改成min边界初始化从负无穷改成正无穷唯一要注意的是起点不能设置成正无穷。其他逻辑完全一致。这个变形在LeetCode上就叫“最小路径和”在蓝桥杯里也常有类似题目。会一道另一道秒懂。第三种变形起点或终点不固定比如可以从第一行任意位置出发或者要到达最后一行任意位置。这时候只需要把dp的初始化条件相应改掉比如第一行每个位置的dp值都等于对应a[0][j]因为可以从任意起点出发。思路仍然不变。第四种变形加入障碍物某些格子不能走。处理办法是把障碍物格子的dp值设为负无穷或者在转移时跳过。如果障碍物是终点那就直接在dp终点输出负无穷表示不可达。这些都属于同一套模型面试和竞赛都很爱考。6. 常见问题与排查技巧实录6.1 数组越界与初始化错误我见过太多人写的递归版本里没有处理x或y小于0的情况然后一调用就崩。还有人在dp前没有初始化dp[0][j]和dp[i][0]导致(1,1)以外的边界格子算出来是随机值。这个问题的典型特征是小矩阵能过矩阵一大结果就错因为随机值参与运算后会累积误差。排查建议先在n1或m1的极端情况下测试。比如1行3列的矩阵最大值只能是这一行所有数字相加因为没得选。如果你的代码在这种输入下都错那必然边界没处理好。把所有dp[i][0]和dp[0][j]显式初始化为一个足够小的负数比如-1e9而不是默认的0。如果用了滚动数组注意区分“上一行的值”和“本行的值”可以打印每一行更新前后的一维数组肉眼对比。6.2 记忆化搜索的标记冲突刚才提过用-1当“未计算”标记如果矩阵元素本身可能等于-1就会出问题。假设某个格子的最大路径和正好是-1你把它存进memo下次访问时发现memo[x][y]-1以为没算过又递归算一遍虽然结果最终不会错但复杂度回到指数级超时不可避免。更安全的方式是单独开一个vis[x][y]布尔数组记录是否算过或者把memo初始化为一个不可能达到的值例如-0x3f3f3f3f。我一般喜欢这样写int memo[105][105]; bool vis[105][105]; int dfs(int x, int y) { if (x 0 || y 0) return NEG; if (x 0 y 0) return a[0][0]; if (vis[x][y]) return memo[x][y]; vis[x][y] true; return memo[x][y] max(dfs(x-1,y), dfs(x,y-1)) a[x][y]; }这样无论矩阵里出现什么数字都不会影响“是否计算过”的判断。6.3 递归爆栈与超时如果nm比较大递归深一万层直接栈溢出。蓝桥杯系统里的“最大值路径”样例一般不会大到爆栈但你不能赌。碰到递归超时的情况先确认是不是没有记忆化。有些同学把记忆化写错了比如在递归返回前存了memo但调用的地方忘了查memo等于没优化。确认方法很简单在dfs第一行打印(x,y)看同一个坐标是否被打印多次。如果被打印多次说明缓存没生效。另外可以统计递归调用次数优化前和优化后对比一下小矩阵可能看不太明显但15×15以上次数差了十万八千里。如果确定记忆化没问题还是超时多半是输入输出太慢。蓝桥杯环境支持cin标准输入但建议加上ios::sync_with_stdio(false); cin.tie(0);对大量数据的题目提升明显。我写代码时已经习惯性带上避免因为I/O卡常。6.4 测试用例设计建议刷题和比赛里最怕代码能过样例但WA。这里分享一套自测用例组合1×1矩阵只有起点也是终点输出a[0][0]。1×n矩阵输出整行和。n×1矩阵输出整列和。2×2矩阵手工算一下验证基本转移。全负数矩阵验证边界初始化是否用的负无穷。矩阵中穿插几个很大的正数和很大的负数验证是否最大化正数、规避负数但要注意路径约束可能无法规避所有负数。把这些用例全部跑一遍基本能排除90%以上的逻辑错误。特别是全负数用例如果你用0初始化边界答案会错成“一个非负值”这会立刻暴露问题。6.5 在蓝桥杯环境下的提交技巧蓝桥杯的代码评测环境一般支持C11所以#include bits/stdc.h可以直接用能省很多include。但要注意万能头文件在某些严格编译器下可能编译慢比赛时一般无所谓。如果你不确定题目中矩阵的行列顺序先看样例输入。最大值路径题基本都是先n后m格子大小通常不超过100所以开105×105的数组绰绰有余。如果n和m最大到1000就不能开二维数组了必须用滚动数组。做题前先看数据范围能省很多内存相关的麻烦。我个人在实际操作中的体会是不要一开始就追求最优解先把暴力递归写出来哪怕超时它也能帮你验证后续DP算法是否正确。拿递归的结果当“标准答案”拿DP的结果去对比在本地生成随机小矩阵批量测试两边输出一致再提交。这个方法比盯着代码找bug高效得多。最后再分享一个小技巧。如果你用记忆化搜索或DP求出了最大值但题目要求输出多条路径中的某一条别慌后处理回溯就行。而如果你把dp的转移方向想反了比如我一开始习惯写“从终点往起点递归”那么dp数组就改成从右下角往左上角填转移方向是向上和向左公式变成dp[i][j] max(dp[i1][j], dp[i][j1]) a[i][j]思路一模一样。多练习这道“最大值路径”你就能把递归、记忆化、动态规划、滚动数组、路径回溯这几个最核心的技能一次性串起来。以后再遇到网格类DP基本就是换皮。
