企业官网建设流程全解析

蓝桥杯的算法提高题里，“最大值路径”估计是很多人的老朋友。题目描述很简单：一个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)步向右，总共步数是固定的n+m-2，路径的差异只是决定哪几步向下。因此路径总数是组合数C(n+m-2, n-1)。当n和m都等于15时，这个数已经超过4千万；当n=20、m=20时，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]

递归出口：当x==0且y==0时，最大路径和就是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^(n+m))的，因为每个状态会分裂成两个子状态，不做任何缓存的话，计算量是路径数量的指数级别。

更直观地说，递归代码的执行过程像一棵不断分叉的树，每个叶子节点对应一个起点状态。树的节点数远远大于矩阵格数。可实际上，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如果到了几百几千，递归层数可能等于路径长度n+m，而系统栈一般只有几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]

但这里必须处理边界情况。当i=0时，dp[i-1][j]不存在，只能从左边过来；当j=0时，dp[i][j-1]不存在，只能从上面过来；当i=0且j=0时，它是起点，直接等于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下标最简单的写法如下：

vector<int> 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;

这里有个很微妙的点：当i==1且j==1时，如果直接执行max(dp[1], dp[0]) + a[1][1]，dp[1]初始为0，dp[0]是NEG，结果也是a[1][1]，所以其实不需要特判。因为dp[1]在进入循环时被设成0了，相当于虚拟起点。直接写：

vector<int> 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]还是上一行（其实是初始NEG），dp[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开始，先更新j=1），dp[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; } } } } vector<pair<int,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)以外的边界格子算出来是随机值。这个问题的典型特征是：小矩阵能过，矩阵一大结果就错，因为随机值参与运算后会累积误差。

排查建议：

• 先在n=1或m=1的极端情况下测试。比如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 递归爆栈与超时

如果n+m比较大，递归深一万层，直接栈溢出。蓝桥杯系统里的“最大值路径”样例一般不会大到爆栈，但你不能赌。碰到递归超时的情况，先确认是不是没有记忆化。有些同学把记忆化写错了，比如在递归返回前存了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 在蓝桥杯环境下的提交技巧

蓝桥杯的代码评测环境一般支持C++11，所以#include <bits/stdc++.h>可以直接用，能省很多include。但要注意，万能头文件在某些严格编译器下可能编译慢，比赛时一般无所谓。

如果你不确定题目中矩阵的行列顺序，先看样例输入。最大值路径题基本都是先n后m，格子大小通常不超过100，所以开105×105的数组绰绰有余。如果n和m最大到1000，就不能开二维数组了，必须用滚动数组。做题前先看数据范围，能省很多内存相关的麻烦。

我个人在实际操作中的体会是：不要一开始就追求最优解，先把暴力递归写出来，哪怕超时，它也能帮你验证后续DP算法是否正确。拿递归的结果当“标准答案”，拿DP的结果去对比，在本地生成随机小矩阵，批量测试，两边输出一致再提交。这个方法比盯着代码找bug高效得多。

最后再分享一个小技巧。如果你用记忆化搜索或DP求出了最大值，但题目要求输出多条路径中的某一条，别慌，后处理回溯就行。而如果你把dp的转移方向想反了，比如我一开始习惯写“从终点往起点递归”，那么dp数组就改成从右下角往左上角填，转移方向是向上和向左，公式变成dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + a[i][j]，思路一模一样。多练习这道“最大值路径”，你就能把递归、记忆化、动态规划、滚动数组、路径回溯这几个最核心的技能一次性串起来。以后再遇到网格类DP，基本就是换皮。