刷到 SWUSTOJ 1132 这道 Coin-collecting by robot 的时候我第一反应是这不就是算法教材里那个“机器人收集硬币”的经典动态规划例题吗题面确实不难一个机器人从左上角出发只能向右和向下走经过有硬币的格子就捡起来问走到右下角最多能收多少枚。但越是这种“看着眼熟”的经典 DP越容易在细节上翻车——我见过太多人思路完全正确代码 WA 到怀疑人生最后发现是边界初始化、行列读反或者多组数据没清空。这篇文章我就把这个机器人走格子的题目从题意、DP 推导、完整代码到调试经验完整拆一遍再顺手讲几个高频变体比如带障碍、带负数权值、甚至两个机器人同时收硬币。不管你是刚入门 DP 的新手还是卡在这道题上想找一份能直接“抄作业”的解法这篇都能派上用场。1. 题意还原这个机器人到底在什么地图上走1.1 题面在说什么题目给你一个 r 行 c 列的长方形格子地图行从上到下编号列从左到右编号。地图里的每个格子上要么有硬币记为 1要么没有记为 0。机器人从左上角也就是第 1 行第 1 列的格子出发每次移动只能选择向右走一格或者向下走一格不能向左、不能向上、不能斜着走。机器人经过一个格子时如果这个格子上有硬币就自动捡起来。最后机器人要走到右下角也就是第 r 行第 c 列的格子问它在整条路径上最多能收集到多少枚硬币。这个描述看起来很简单但有两个关键约束决定了整个题目的性质移动方向被死死限制在“向右”和“向下”也就是说机器人永远不会走回头路。从左上角到右下角无论中途怎么绕向下的步数一定是 r-1 次向右的步数一定是 c-1 次总步数是固定的 (r-1)(c-1)rc-2 步经过的格子数是 rc-1 个。目标不是“找到一条能到终点的路”而是在所有可行路径里挑一条“沿途硬币总数最大”的路径。暴力枚举所有路径的念头会马上冒出来但先别急着写 DFS往下看就知道为什么这条路走不通。1.2 输入输出格式与一个具体样例SWUSTOJ 这类 OJ 的题目输入格式通常很直接第一行是两个整数 r 和 c分别表示行数和列数。接下来 r 行每行 c 个整数每个整数是 0 或 1代表这个格子上有没有硬币。输出一行一个整数表示机器人从左上角走到右下角最多能收集到的硬币数。我随手构造一个 3 行 4 列的地图来当样例3 4 1 0 0 1 0 1 1 0 0 0 1 1这个样例的输出应该是5怎么得到的 5我们可以走这条路径(1,1) → (2,1) → (2,2) → (2,3) → (3,3) → (3,4)对应的方向序列是“下、右、右、下、右”。沿途经过的 6 个格子分别是 1、0、1、1、1、1加起来正好是 5。是不是所有路径里最多就只能拿 5 枚这个问题先记在心里后面我用 DP 表一步步算给你看。这里要提醒一句很多同学在读入地图时会把 r 和 c 弄反或者把一行 c 个数读成 c 行。我自己的习惯是拿到题目先写注释r 是行数对应外层循环c 是列数对应内层循环数组开成grid[105][105]下标从 1 开始方便处理边界。2. 为什么不直接暴力搜索也不建议贪心2.1 暴力 DFS 的组合爆炸既然路径是由 r-1 次“向下”和 c-1 次“向右”组成的那么路径总数就是组合数 C(rc-2, r-1)。当地图只有 10×10 时C(18,9)48620暴力还能勉强跑但一旦到 20×20C(38,19) 大约是 3.5×10^10这个数量级任何 OJ 都不可能让你通过。如果你用 DFS 一层层去枚举所有方向序列哪怕每次只做常数级操作也会直接跑飞。有同学会说那我用记忆化搜索把到达每个格子时的最优值记下来不就行了这想法其实已经摸到 DP 的门槛了记忆化搜索和动态规划本质上是同一种东西的两种写法但既然都能“记录子问题最优值”为什么不直接写成更简洁的 DP 递推呢所以暴力枚举不是不能做而是没有必要。2.2 贪心为什么在这里不成立还有一个很自然的思路是贪心每一步都往“当前能捡到硬币”的方向走如果右边有硬币就右走下面有硬币就下走。这种思路在部分随机数据里看起来很有道理但随便构造一个地图就能让它翻车。看这个 3×3 的地图1 0 0 0 1 1 1 1 1如果采用“右边和下边硬币数量一样多时就优先向右”的贪心规则机器人从 (1,1) 出发右边是 0下边是 0平局按规则向右走到 (1,2)右边是 0下边是 0平局继续向右到 (1,3)只能向下到 (2,3)再向下到 (3,3)。这条路径收集到的硬币是 100113 枚。但最优解明明可以做到 4 枚先向下到 (2,1)再向下到 (3,1)然后一路向右经过 (3,2)、(3,3)收集 101114 枚。或者走 (1,1)→(2,1)→(2,2)→(2,3)→(3,3)同样能收 4 枚。问题出在哪出在贪心只做“局部最优决策”它不会为了后面对第三行那一串硬币而牺牲眼前任何一个方向。机器人一旦在第一步选择了向右整个第三行就被永久错过了。路径类问题最常见的一个特征就是“当前选择决定未来可达区域”如果不做全局权衡几乎不可能拿到最优。2.3 从“最后一步从哪来”找到突破口暴力不行贪心也不行那正确的打开方式是什么回到问题本身。无论机器人走的是哪条路径它到达某个格子 (i,j) 之前上一步只可能是从正上方 (i-1,j) 下来的或者从正左方 (i,j-1) 过来的。这两个来源覆盖了所有可能性没有任何遗漏。于是关键结论出现了如果我已经知道“到达 (i-1,j) 时最多能收多少硬币”和“到达 (i,j-1) 时最多能收多少硬币”那么到达 (i,j) 的最优值必然是从这两个值里取一个较大的再叠加上 (i,j) 这个格子本身的硬币数。这个逻辑不需要关心机器人具体是怎么走到 (i-1,j) 或 (i,j-1) 的只需要知道它们的最优值是多少。这就是典型的“最优子结构”也是动态规划能够成立的根基。3. DP 状态设计与递推公式的完整推导3.1 状态究竟存什么很多初学者学 DP 最大的坎就是“状态不会定”。这道题的状态非常自然用 dp[i][j] 表示机器人从 (1,1) 出发走到格子 (i,j) 时最多能收集到的硬币数。为什么这个状态定义只需要两个维度因为移动方向被限制为向右和向下走到任意一个格子路径的“前半段”只有两种可能的来源方向而所有来源路径的收益都被 dp[i-1][j] 和 dp[i][j-1] 完整概括了。状态里不需要记录机器人从哪个方向来因为“取两个来源中更大者”这件事本身就隐含了决策过程。3.2 递推公式的推导过程设当前格子 (i,j) 的硬币数为 a[i][j]。那么dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]这个公式的每一步都值得掰开讲如果机器人是从上方 (i-1,j) 下来的那么到达 (i,j) 时收集的硬币总数 dp[i-1][j] a[i][j]如果机器人是从左方 (i,j-1) 过来的那么总数 dp[i][j-1] a[i][j]这两种情况取较大者就是最终答案。需要特别注意的是边界情况。第一行i1的格子没有上方只能从左边来所以 dp[1][j] dp[1][j-1] a[1][j]第一列j1的格子没有左方只能从上边来所以 dp[i][1] dp[i-1][1] a[i][1]起点 (1,1) 比较特殊它没有前驱格子所以 dp[1][1] a[1][1]。处理边界最省事的技巧是把 dp 数组多开一圈下标为 0 的行和列全部初始化成 0。这样当 i1 或 j1 时dp[0][j] 和 dp[i][0] 自然就是 0递推公式不需要特判就能统一工作。3.3 填表顺序和复杂度计算 dp[i][j] 依赖 dp[i-1][j]上一行和 dp[i][j-1]同一行左边所以填表顺序必须是从上到下逐行处理每一行内从左到右逐列处理。这样保证在计算任何一个格子之前它依赖的两个值都已经算好了。时间复杂度 O(r×c)空间复杂度 O(r×c)。如果地图是 100×100总计算量只有一万次轻松通过就算地图是 1000×1000一百万次也完全够。3.4 用手算把完整 DP 表过一遍还是用之前那个 3×4 的样例地图1 0 0 1 0 1 1 0 0 0 1 1我按行从左到右填表dp[1][1] 1dp[1][2] dp[1][1] 0 1dp[1][3] dp[1][2] 0 1dp[1][4] dp[1][3] 1 2dp[2][1] dp[1][1] 0 1dp[2][2] max(dp[1][2]1, dp[2][1]1) 1 2dp[2][3] max(dp[1][3]1, dp[2][2]2) 1 3dp[2][4] max(dp[1][4]2, dp[2][3]3) 0 3dp[3][1] dp[2][1] 0 1dp[3][2] max(dp[2][2]2, dp[3][1]1) 0 2dp[3][3] max(dp[2][3]3, dp[3][2]2) 1 4dp[3][4] max(dp[2][4]3, dp[3][3]4) 1 5。最终 dp 表长这样dp 值第1列第2列第3列第4列第1行1112第2行1233第3行1245右下角 dp[3][4]5和之前手动找的路径结果一致。这个手算过程强烈建议自己再推一遍DP 题最忌讳的就是“代码能过样例但说不清为什么”能徒手算出 DP 表才算真正理解了递推。4. 完整 AC 代码与调试实战经验4.1 最稳妥的二维数组写法下面是我最推荐在 OJ 上提交的版本逻辑清晰适合绝大多数情况#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 105; int dp[MAXN][MAXN]; int main() { int r, c; while (scanf(%d%d, r, c) 2) { memset(dp, 0, sizeof(dp)); for (int i 1; i r; i) { for (int j 1; j c; j) { scanf(%d, dp[i][j]); } } for (int i 1; i r; i) { for (int j 1; j c; j) { if (i 1 j 1) continue; dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } printf(%d\n, dp[r][c]); } return 0; }这个代码有一个小细节我直接把读入的硬币数存在 dp 数组里然后在同一个数组上做累加更新。因为 dp[0][] 和 dp[][0] 全部是 0第一行和第一列不需要单独处理递推公式自动生效。唯一要跳过的是起点 (1,1)因为它的值就是它本身不需要加任何前驱加了也不会变但跳过让逻辑更清晰也避免有人绕晕。4.2 追求空间优化就写滚动数组有些题目会把地图开到 1000×1000 甚至更大二维数组还是能扛住但如果你想去掉一个维度让空间变成 O(c)可以这样写#include cstdio #include algorithm using namespace std; int main() { int r, c; while (scanf(%d%d, r, c) 2) { int dp[105] {0}; for (int i 1; i r; i) { for (int j 1; j c; j) { int x; scanf(%d, x); if (i 1 j 1) { dp[j] x; continue; } dp[j] max(dp[j], dp[j-1]) x; } } printf(%d\n, dp[c]); } return 0; }这里滚动数组的精髓在于dp[j] 在被更新之前存的是上一行处理到第 j 列的结果也就是 dp[i-1][j]而 dp[j-1] 在当前行已经被更新过了存的是 dp[i][j-1]。所以max(dp[j], dp[j-1])正好等于max(dp[i-1][j], dp[i][j-1])。第一次看这个写法可能觉得有点绕但对照二维版本多看两遍就能理解这也是面试里常被问到的“滚动数组优化路径类 DP”的经典套路。4.3 我在 OJ 上踩过的几个坑代码不长但 WA 的原因千奇百怪列几个我亲测过的行列读反。题目先给 r 再给 c有人习惯性先写两层循环结果外层循环写成 c内层写成 r导致整个地图被转置输出自然不对。建议在地图读入前加个注释提醒自己。多组数据不清空数组。如果题目有多个测试用例上一组数据残留的值会污染下一组。用 memset 或定义在循环内部都能解决。滚动数组那个版本我直接在循环里定义 dp 数组每次自动清零更省心。数组开太小。地图最大值如果到 100数组开到 105 够用如果到 1000就要开 1005。下标从 1 开始意味着你实际上多用了第 0 行和第 0 列别忽略了。不处理 r1 或 c1 的退化情况。当只有一行时机器人只能一路向右答案是这一行所有格子的硬币和只有一列时同理。上面的二维版和滚动版都能自动处理这种边界但如果你手写了特判一定要测试这组数据。输出格式缺换行。OJ 对输出的空白字符比较宽容但统一在每行答案后加 \n 是良好习惯不要为了省一个字符丢失 AC。4.4 WA 之后的排查路径如果真的 WA 了我的建议是别急着看题解先自己做一个 3×3 的随机地图手算出 DP 表再拿代码跑一遍对比。也可以故意构造 r1、c1、全 0、全 1 这几种极端数据跑完就知道问题大概出在哪。如果实在对不上就在递推循环里加 printf 把 dp 表打出来逐格对比自己的手算过程这种调试方式比瞎改代码高效得多。5. 这道题之外的经典扩展与进阶思路5.1 要求输出具体路径怎么做有些题目会进一步要求输出机器人的完整路径。这时候只需要在递推过程中额外开一个 pre 数组记录每个格子到底是从上方来还是从左方来int pre[MAXN][MAXN]; // 在递推时记录 if (dp[i-1][j] dp[i][j-1]) { dp[i][j] dp[i-1][j] a[i][j]; pre[i][j] 0; // 0 表示从上方来 } else { dp[i][j] dp[i][j-1] a[i][j]; pre[i][j] 1; // 1 表示从左方来 }最后从 (r,c) 沿着 pre 数组一路回溯到 (1,1)把方向逆序存下来再反转就得到了路径。注意如果两个来源的 dp 值相等随便取一个都行不影响最优硬币总数。5.2 地图里有障碍物怎么处理如果把问题改成“某些格子机器人不能走”处理方式也很简单把障碍格子的硬币价值设为一个极小值比如 -0x3f3f3f3f并且在递推时跳过或直接让它的 dp 值保持为负无穷。但更稳定的写法是遇到障碍格子直接continue不让它参与后续递推。要注意起点和终点如果本身是障碍那答案直接就是“不可达”。5.3 格子带权值且可能是负数当格子上的数字不再是 0/1而可能是正数、负数甚至零时递推公式dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]依然成立但有一个大坑dp 数组的初始值不能再一律设成 0。如果一个格子真的不可达或者路径从来没开始过0 会错误地表示“一条空路径”导致负数权值的路径被忽略。正确做法是把 dp 初始化成负无穷比如 -0x3f3f3f3f再把 dp[1][1] 设成 a[1][1]。这也是为什么很多动态规划题里你都看到别人用memset(dp, 0xc0, sizeof(dp))或fill(dp[0], dp[0]N*N, -INF)道理就在这里。5.4 两个机器人同时收集硬币这一类扩展非常经典也经常作为进阶题出现比如“方格取数”或者“传纸条”。假设两个机器人同时从 (1,1) 出发都只能向右或向下走它们不能同时占用同一个格子或者可以但硬币只能计一次问最终两个机器人最多合计收多少硬币。面对这个问题二维 DP 就不够了。关键观察是两个机器人同时出发每一步都走相同数量的步数所以第一个机器人如果在 (i,j)第二个机器人在 (k,l)一定有 ij kl。设 dp[i][j][k] 表示第一个机器人在 (i,j)、第二个机器人在 (k,l) 时两者合计的最大硬币数其中 l ij-k。转移时每个机器人都有“从上方来”和“从左方来”两种选择因此一共 4 种转移dp[i][j][k] max(四种前驱) (如果 (i,j) 和 (k,l) 是同一个格子就只加一次否则加两次)复杂度大约是 O(r×c×(rc))在 r、c 不超过几十的范围内完全可跑。三维 DP 对初看起来有点吓人但它和二维 DP 的底层思想完全一致状态记录每一步的“最优历史”转移枚举“所有可能的最后一步来源”。学有余力的同学可以自己实现一遍。5.5 路径类 DP 的通用解题套路做多了这类题你会发现一个通用套路看到“只能向右向下”的网格路径题先用“最后一步从哪来”来定义状态再套dp[i][j] 前驱最优 当前格代价的公式然后根据题意决定 max 还是 min、初始化是 0 还是负无穷。这个套路不仅能解硬币收集、最小路径和、最大路径和还能解障碍路径方案数把 max 换成 sum、路径带固定步数等变种。拿“路径方案数”举例如果问从左上到右下有多少种走法递推就是dp[i][j] dp[i-1][j] dp[i][j-1]dp[1][1]1。这一下就能看出来动态规划的框架没变变的只是状态价值和转移运算。我自己做了几百道路径类 DP 之后最大的体会是状态定义决定了题目的难度上限。只要能准确定义出“一个格子代表什么”递推公式通常自己就跳出来了。遇到想不出状态的时候永远从“最后一步有哪些可能”开始想这一招在网格路径题里几乎百试百灵。最后再分享一个小技巧AC 之后不要急着切下一题把代码里改成滚动数组试试再改成输出路径再改成带障碍版本。一道题吃透三种变形比盲目刷十道类似的题收获大得多。SWUSTOJ 1132 这道 Coin-collecting by robot 作为入门 DP 题正好是练这个流程的绝佳素材。