刷 OJ 刷到 SWUST OJ 1132 这道 Coin-collecting by robot 的时候第一眼我以为是道模拟题结果仔细一读才发现是个典型的网格型动态规划。这类题在 ACM 入门阶段非常常见但恰恰是这种“看起来简单”的题目最容易把状态设计、边界处理、滚动数组优化这些基本功暴露出来。我见过太多人一眼看出 DP 思路结果代码提交后却在第一行、第一列上反复卡壳。这篇文章就把这道题的完整拆解写下来从题目建模、推导转移方程、写代码到踩坑排查都过一遍最后再聊聊它和实际业务里路径规划问题的映射关系。先把这个问题的核心价值说清楚这道题不是让你背一个 DP 模板而是让你理解“如何把一个路径选择问题转化成子问题叠加”。理解了它后面遇到双机器人取硬币、带障碍物的取硬币、以及各种棋盘类 DP 都会轻松很多。不管你是刚接触算法的学生还是想复习动态规划的从业者这篇都值得往下读。1. 题目还原与建模思路1.1 我理解的题面设定SWUST OJ 1132 的原题描述通常长这样给定一个 n 行 m 列的棋盘每个格子里放有一定数量的硬币也可能是空格子一个机器人从左上角出发每次只能向右或者向下移动一格最终要到达右下角。机器人经过某个格子时会把该格子的硬币全部捡起来问最多能收集到多少枚硬币。不同的 OJ 版本在输入输出格式上会有些差异有的直接给一个 n、m 然后读入矩阵有的会给若干硬币坐标但核心模型是一致的在网格上找一条从起点到终点的路径路径方向被限定为右、下两个方向目标是最大化路径上权值之和。我建议拿到题先确认三件事输入是矩阵还是坐标列表、起点终点的硬币是否计入、数据范围大到什么程度。这三件事直接决定你的代码怎么组织也决定你是否需要滚动数组。1.2 约束条件与复杂度目标这类题目的数据范围一般不会太大常见的是 n 和 m 在 500 到 1000 之间单格硬币数量在 0 到 100 之间。这种范围下O(n × m) 的算法是完全够用的。不过有些变体题会把矩阵压到 1000 × 1000 以上或者硬币数量给得很大这时候就要留个心眼累计值可能超过 int 范围代码里最好直接用 long long别在最后提交时因为一个溢出 WA 得莫名其妙。时间复杂度上标准解法是 O(n × m) 的动态规划空间复杂度可以做到 O(min(n, m))。如果题目给了二维数组大小限制或者你在牛客、力扣这类平台上做题时提交前有个内存限制提示这个优化就非常关键。1.3 为什么这道题值得研究说句实话单看算法本身这题放在 ACM 比赛里连签到题都算不上但它背后的“网格 DAG 动态规划”却是非常通用的基础模型。机器人只能向右、向下移动意味着整个网格天然是一个有向无环图DAG不存在回头路不存在循环依赖于是动态规划可以直接按照行列顺序推进。如果你能把这道题吃透等于掌握了网格路径类 DP 的底层逻辑状态怎么定义、转移怎么写、边界怎么处理、空间怎么压缩。接下来遇到的许多“看起来很唬人”的题目本质上都是在这个骨架上加了其他限制条件而已。2. 动态规划推导为什么状态这样定义2.1 贪心策略为什么不行看到“最多收集硬币”许多人的第一反应是贪心每一步都选择右边和下边两个格子里硬币更多的那个方向走。这个思路听上去很合理但局部最优并不等于全局最优特别是在棋盘类路径问题上当前一步选择较大的值可能把后面的高收益区域全部错过。举个简单反例3 3 1 10 10 10 10 1 1 1 1从左上角 (1,1) 出发当前格自己是 1下一步右边是 10、下边也是 10看起来走哪里都行。但如果机器人在下边和右边之间选择了向下路径会变成 DDRR总收益是 1 10 1 1 1 14而如果第一步向右后续保持向右再向下总收益是 1 10 10 1 1 23。同样是从两个 10 里选一个选择的差异直接导致结果差了一大截。这就是贪心的致命问题它只看到眼前一格的价值看不到未来路径上的累计收益。而动态规划之所以能赢是因为它把“未来”也纳入到了子问题里。2.2 状态定义dp[i][j] 到底代表什么网格路径 DP 最自然的状态定义是dp[i][j] 表示机器人从左上角走到第 i 行第 j 列时能收集到的最大硬币数并且把当前格子的硬币已经算进去。这个“已经算进去”特别重要。很多人写 DP 时不注意这个细节最后答案总是差一个起点或者终点的值就是因为对状态含义的理解模糊。有了这个定义我们就知道答案应该输出 dp[n][m]也就是走到右下角且把右下角硬币也算上之后的最大值。2.3 转移方程的严格推导为什么转移方程是dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i][j]关键原因在于最后一步。任何一条从左上角到达 (i, j) 的路径它的最后一步只有两种可能要么从上方 (i - 1, j) 走下来要么从左方 (i, j - 1) 走过来。既然 dp[i - 1][j] 已经表示从起点走到上方格子的最优总收益dp[i][j - 1] 已经表示从起点走到左方格子的最优总收益那么到达当前格子的最优值必然是从这两个前驱状态里挑一个更大的再加上当前格子本身的硬币数量。这种“只看最后一步”的推导方式是 DP 问题里最核心的思考方法。很多人在做动态规划时习惯背状态转移方程却没有理解其背后的“最后一步”逻辑一旦题目稍作变化就束手无策。2.4 边界条件怎么初始化边界条件是网格 DP 翻车的重灾区。首先是起点。dp[1][1] 应该直接等于 grid[1][1]因为机器人一开始就站在这个格子上硬币已经被收走了。其次是第一行。第一行所有格子都只能从左边到达不存在从上方来的情况所以转移时不能取 max(dp[i - 1][j], dp[i][j - 1])而要单独处理dp[1][j] dp[1][j - 1] grid[1][j]第一列同理dp[i][1] dp[i - 1][1] grid[i][1]处理边界的方式通常有两种一种是在循环里加 if 判断另一种是先把第一行、第一列手动初始化然后从 i 2、j 2 开始双重循环。我个人更推荐后一种逻辑更清晰也不容易在循环里写出越界访问。3. 代码实现与空间优化3.1 最直接的二维 DP 写法先看一份最直观的 C 语言实现适合在 OJ 上直接提交#include stdio.h #define MAXN 1005 #define max(a, b) ((a) (b) ? (a) : (b)) int grid[MAXN][MAXN]; int dp[MAXN][MAXN]; int main() { int n, m; scanf(%d %d, n, m); for (int i 1; i n; i) { for (int j 1; j m; j) { scanf(%d, grid[i][j]); } } dp[1][1] grid[1][1]; for (int j 2; j m; j) { dp[1][j] dp[1][j - 1] grid[1][j]; } for (int i 2; i n; i) { dp[i][1] dp[i - 1][1] grid[i][1]; } for (int i 2; i n; i) { for (int j 2; j m; j) { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } printf(%d\n, dp[n][m]); return 0; }这份代码够清晰但开了两个二维数组。如果数据范围变成 1000 × 1000两个数组各占 1000 × 1000 × 4 字节也就是 4MB 左右两个加起来差不多 8MB某些内存限制比较严格的 OJ 上可能会出问题。这时候就要做空间优化。3.2 滚动数组把二维压成一维仔细观察转移方程会发现dp[i][j] 只依赖两个值同一行的左边一格 dp[i][j - 1]以及上一行的同一列 dp[i - 1][j]。也就是说计算当前行的时候上一行的数据仍然有用但更早的行已经完全用不到了。于是我们可以用一个一维数组 dp[j] 来滚动保存状态。循环到第 i 行时dp[j] 在被更新前保存的是 dp[i - 1][j]被更新后变成 dp[i][j]。这里是最容易绕晕的地方我建议拿张纸画一下在进入第 i 行循环之前dp 数组保存的是第 i - 1 行的完整结果。当你计算第 i 行第 j 列时dp[j] 还没被覆盖它还是上一行的值正好可以代表 dp[i - 1][j]。你左边那格 dp[j - 1] 已经在本次循环中被更新过了所以它代表 dp[i][j - 1]。代码长这样#include stdio.h #define MAXM 1005 #define max(a, b) ((a) (b) ? (a) : (b)) int grid[MAXM]; // 不需要存整个矩阵读一行处理一行 int dp[MAXM]; int main() { int n, m; scanf(%d %d, n, m); for (int i 1; i n; i) { for (int j 1; j m; j) { scanf(%d, grid[j]); if (i 1 j 1) { dp[j] grid[j]; } else if (i 1) { dp[j] dp[j - 1] grid[j]; } else if (j 1) { dp[j] dp[j] grid[j]; } else { dp[j] max(dp[j], dp[j - 1]) grid[j]; } } } printf(%d\n, dp[m]); return 0; }注意这里读取方式变了按行读入读到一个格子立刻更新对应位置的 dp。这样整个程序只需要一个一维 dp 数组和一个长度只有 m 的临时 grid 行数组空间开销从 O(n × m) 降到了 O(m)。如果你想让代码更通用一点也可以用两个一维数组 pre 和 cur 来表示上一行和当前行理解起来会比单数组滚动更直观但实际工程中能省一个数组就省一个我是习惯了直接单数组滚动。3.3 能原地修改可以但要看情况如果题目明确说输入矩阵之后不会再使用你可以直接在 grid 数组本身做 DP连 dp 数组都不用开。思路是把 grid[i][j] 原地更新为“从起点到当前格子的最大累计值”grid[1][1] grid[1][1]; for (int j 2; j m; j) grid[1][j] grid[1][j - 1]; for (int i 2; i n; i) grid[i][1] grid[i - 1][1]; for (int i 2; i n; i) for (int j 2; j m; j) grid[i][j] max(grid[i - 1][j], grid[i][j - 1]);这种写法在竞赛里特别省事但我建议只在原题允许的情况下用。有些题目后面还要拿原始矩阵做输出原地修改就会导致数据被破坏直接 WA。3.4 路径重建一个很值得练的延伸如果题目要求输出路径而不是只输出最大硬币数那么需要在 DP 的基础上额外记录每个格子是从哪里转移来的。具体做法是开一个 direction 数组或者直接用字符数组记录每个格子的前驱方向如果从上方来记录为 U 或者 0如果从左方来记录为 L 或者 1等到 dp 全部算完从 (n, m) 开始沿着 direction 一路回溯到 (1, 1)再把路径反转就得到完整的移动序列。路径重建在面试题里经常出现因为很多面试官不会满足于“求最大值”而是想考察你能否把推导出的最优方案还原出来。这道题正好做了铺垫。4. 常见问题与排查技巧实录4.1 第一行第一列初始化错了这是我见过最多人踩的坑。有些人图省事把 dp 数组全部初始化为 0然后从 i 1、j 1 开始双循环每个格子都统一用 max(dp[i - 1][j], dp[i][j - 1]) grid[i][j] 来计算。问题在于当 i 1、j 2 时dp[0][2] 是 0但机器人并不存在“从第 0 行走过来”这个动作。如果按统一公式算结果也不会差因为 dp[0][2] 0 小于 dp[1][1]于是 max 会取左边的值碰巧对了。但当你用一维滚动数组时dp[0] 这个位置可能残留上一行的值一旦处理不好边界就会出错。更标准的做法就是我在 3.1 节里那样先把第一行、第一列单独处理主循环从 2 开始。这样既清晰又安全。4.2 起点硬币到底算不算不同题目对起点和终点的处理并不一致。有的题目描述是“机器人到达终点后把终点硬币也收集”有的则把起点当作已经站在上面所以起点硬币直接计入。大部分题都是按计入处理但你自己写代码前最好确认一下。有一种快速确认方法找题目给的样例照着样例手算一遍路径看输出是否把 grid[1][1] 算进去了。如果输出是 0 而不是 grid[1][1]说明起点不算需要把 dp[1][1] 初始化为 0。4.3 是否越界与下标映射混乱很多 OJ 的棋盘是 1-based 下标也就是从第 1 行第 1 列开始编号。如果你读入时用 1-based循环也从 1 开始代码整体协调即可。但如果你把循环写成从 0 开始却忘了把输出下标改成 n - 1 和 m - 1就很容易出现多算一行、少算一列的诡异错误。我自己调试这类题目时的习惯是先给输入矩阵加一行一列“哨兵”也就是把 dp 数组多开一圈全部初始化为 0然后循环从 1 开始。这样 dp[i][j] 计算时dp[i - 1][j] 和 dp[i][j - 1] 在 i 1 或 j 1 时天然为 0不会越界。这种方法叫做“假边界”很多做图像处理的人也用类似技巧避免边缘判断。4.4 数据范围导致的类型溢出如果 n 和 m 都到了 1000每个格子硬币数量到了 100那么最大路径收益可能接近 1000 × 1000 × 100 10^8int 还能撑住。但如果硬币数量给到 10^9或者矩阵扩大到 2000 × 2000那累计值就可能超过 2 × 10^9int 直接就爆了。我在做题时有一个习惯只要看到权值和范围给出的上限超过 10000直接开 long long不要纠结。省下的那点内存相比排查溢出的时间成本完全不值一提。4.5 一段来自我自己的排查流程遇到提交 WA我会按这个顺序排查先打印 dp 矩阵看前两行、前两列是否符合手算预期。拿一个 3 × 3 的随机矩阵用暴力 DFS 枚举所有路径把结果和 DP 结果对比。检查输入是否有空格、换行导致读取不到数据特别是矩阵元素可能用逗号分隔时。最后再看是否有数组越界隐藏 bug比如定义数组大小为 MAXN 但读入的是 n1 行。这个流程大概花五分钟能解决 90% 的边界和初始化问题。5. 延伸进阶从这道题到更复杂的网格 DP5.1 两个机器人同时收集硬币这是这道题最经典的扩展版也是很多面试题库里的常客。两个机器人从左上角同时出发一个往右下角走另一个也往右下角走但它们不能重复收集同一格子的硬币问最多能收集多少。解法是用一个三维 DPdp[step][x1][x2] 表示两个机器人各自走了 step 步时分别在第 x1 行和第 x2 行的最大收益。由于步数相同它们所在列可以由步数和行数推算出来。转移时需要考虑四种情况两个都从上往下、两个都从左往右、一个上一个左等等。这种题本质上就是在“多一个人”的情况下如何同步更新状态。理解了单机器人版本的 dp 定义再去推双机器人版本就会顺很多。5.2 带障碍物和负权值的场景如果网格中有障碍物机器人不能经过通常把障碍格的 dp 值设为一个极小值比如 -1e18这样转移时 max 会自动避开它。要注意的是起点和终点如果是障碍物那么整个问题可以直接输出特定值别让代码在这里出现奇怪的结果。但一旦格子里的硬币数量出现负数简单的 DP 就不再适用了因为负数权值意味着路径可能会为了绕开它而多走很多步而多走的每步都可能增加总收益。在这种场景下问题就从一个 DAG 上的最长路径问题变成了需要更复杂理论支撑的问题。这块属于延伸思考遇到再研究也不迟。5.3 现实世界里的路径规划映射你可能会觉得这种网格收集硬币的问题只存在于 OJ 里跟现实世界没什么关系。其实不是它在很多场景里都有影子。比如仓储物流里的 AGV 搬运车路径规划。仓库地面可以抽象成网格每个格点上的“硬币”可能代表某种奖励权重比如通风好的区域、电量补给点、临时任务点。AGV 需要在不能掉头、不能斜穿的约束下找到一条从入库点到出库点收益最大或成本最小的路径这和机器人收集硬币是同一个数学结构。再比如游戏里的寻路设计某些格子会掉落奖励玩家被设计成只能单向移动这时 AI 选择路径的策略就和这道题一模一样。还有金融领域里的投资组合决策某种程度也可以抽象成“每一步选择不同方向以获得累积收益”的状态转移问题。这就是为什么我说这种基础 DP 值得认真刷而不只是背代码它背后的模型在各行各业里都会被反复包装成新问题出现。5.4 如果题目方向不止两种有些题目会把移动方向扩展到“右、下、左下、右下”四方向或者允许机器人斜着走。这种情况下状态定义通常不变但转移方程里的 max 项会变多复杂度也会相应上升。斜向移动往往意味着行列坐标同时变化这时候就要特别小心循环顺序确保在计算当前状态时所有依赖状态都已经被计算过。我个人的建议是先把基本模型彻底吃透再去做这些变形。模型熟悉之后变体的核心难点就不再是“怎么转移”而是“怎么处理依赖顺序”这些能力都是一步步练出来的。这道题刷完我最大的体会是动态规划最难的从来不是写代码而是把问题抽象成“状态 转移 边界”的过程。Coin-collecting by robot 提供了非常典型且干净的抽象场景一旦你想通了“最后一步怎么走”这个问题代码几乎是被方程推着写出来的。以后再遇到任何“求最大收益路径”的题目我都会先问自己几个问题状态里要保存哪些信息转移依赖于哪些前驱状态边界条件是什么想清楚这三件事再复杂的题也会变得有章可循。