1. 题目到底在说什么问题背景梳理1.1 swustoj 1132 的题目设定swustoj 1132 这道 Coin-collecting by robot很多刷过西南科技大学OJ的同学应该都不陌生。题目描述看起来很简单有一个 m 行 n 列的棋盘每个格子里要么有硬币值为1要么没有值为0。一个机器人从左上角出发每次只能向右或者向下移动一格最终要走到右下角。机器人路过有硬币的格子时会把硬币收走问它最多能收集到多少枚硬币。说白了这是一个求最大路径权值的问题。你要在只能右移和下移的限制下找出一条从起点到终点的路径使得路径上经过的所有格子中的硬币总数最大。这道题之所以经典是因为它几乎是动态规划入门阶段的“必修课”。它把DP里最核心的几个要素全占了状态怎么定义、转移方程怎么推、边界条件怎么处理、空间能不能优化。很多学校的OJ、教学平台和算法教材都会收录这道题或者它的变体用来检验学生对基础DP的掌握程度。1.2 为什么说它是DP入门的“黄金题目”先说一个直觉上的判断这道题看起来很“短”但它的信息密度非常高。你如果只是背代码那五分钟就能AC但如果你把它当成一个思维训练题去抠会发现里面藏了不少东西。它之所以被称为黄金题目有几点原因状态设计非常自然。棋盘上每个格子就是一个状态点不需要像背包问题那样去构造层数、体积等抽象维度。转移方向非常单一。机器人只能向右和下走这决定了状态之间没有环天然满足DP的无后效性要求。边界条件清晰。第一行、第一列的处理方式一目了然适合练习初始化技巧。后续扩展空间大。从二维数组到滚动数组、从单次收集到两次收集走两遍、从原地DP到路径还原都是经典变体。换句话说把这一道题吃透后面遇到“数字三角形”“最小路径和”“不同路径”等一系列题你会发现套路几乎是通用的。1.3 输入输出与数据范围约定这道题在swustoj上的输入格式我按平时做题的经验补充一下常见写法如果你在别的OJ上遇到同名题格式可能有小差异但大差不差。输入通常是第一行两个整数 m 和 n表示棋盘有 m 行 n 列。接下来 m 行每行 n 个整数每个整数是 0 或 11 表示该格放了一枚硬币。输出是一个整数表示机器人从左上角走到右下角能收集到的最大硬币数。数据范围方面原题没有特别夸张的约束常规情况下 m、n 在几十到几百这个量级所以即便是开一个二维数组也不会有内存压力。但这也恰恰给了我们一个练习滚动数组优化和内存敏感型打法的好机会。2. 核心思路拆解从“贪心陷阱”到“动态规划”2.1 为什么贪心不行我第一次做这题的时候脑子里第一个冒出来的想法是那还不简单每一步都优先走到有硬币的格子去不就行了也就是所谓“局部最优推导全局最优”的贪心策略。试一下就发现问题了。举个反例有一个 3×3 的棋盘1 1 0 0 1 0 1 0 1如果每一步都贪心地选右边和下边中硬币更多的那个方向走走的路径可能是 (1,1) → (1,2) → (2,2) → (3,2) → (3,3)收集到 1 1 1 0 1 4 枚。但实际上最优路径是 (1,1) → (1,2) → (2,2) → (2,3) → (3,3)或者走 (1,1) → (2,1) → (3,1) → (3,2) → (3,3)也能拿到 4 枚。这个例子里贪心没有明显吃亏但你只要把格子里的值调换一下比如1 9 0 0 1 0 1 0 1注意这里我们用9表示有很多硬币的格子贪心会选择先去拿9但为了拿到9可能绕过了后面更大收益的路径组合最终反而丢掉更多硬币。因为每一格的选择会连锁影响后续所有可选路径贪心只考虑了眼前这一步所以它在这里必然失效。理解这一点很重要当“当前选择”会改变“未来可选范围”时盲目贪心是不可靠的。而DP恰恰是处理这类“决策影响后续状态”问题的标准武器。2.2 状态定义dp[i][j] 到底代表什么动态规划的第一步就是定义状态。对于这道题最自然的状态是dp[i][j] 表示机器人从左上角 (1,1) 出发走到格子 (i,j) 时最多能收集到的硬币数。这里有个关键点这个“最多”是对“所有能从起点走到 (i,j) 的路径”取最大值而不是某一条固定路径的值。一旦这样定义问题就变成了求 dp[m][n]。为什么这个状态是合法的因为它满足两个重要性质最优子结构到 (i,j) 的最优路径其前缀路径也必然是从起点到 (i-1,j) 或 (i,j-1) 的最优路径。如果不是那么换一条前缀路径就能让总价值更大矛盾。无后效性走到 (i,j) 之后接下来只关心“当前状态值是多少”完全不关心它是怎么走过来的路径上具体经过了哪些格子对后面的决策没有任何影响。这两个性质一满足DP就跑不了了。2.3 状态转移方程的推导过程机器人走到 (i,j)它上一步只有两种可能从左边来也就是从 (i,j-1) 向右走一步从上面来也就是从 (i-1,j) 向下走一步。既然 dp[i][j-1] 已经表示到左边那格的最大硬币数dp[i-1][j] 已经表示到上面那格的最大硬币数那么到 (i,j) 的最大硬币数就应该是这两者中的最大值再加上当前格子 (i,j) 本身的硬币数。于是得到转移方程dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1])这个方程的直观含义就是我为了到达 (i,j)一定要先到它的左边或上边那我当然选择一条“到目前为止收集硬币更多”的路径过来。边界条件也很清晰第一行也就是 i1 时机器人只能一路向右走所以 dp[1][j] dp[1][j-1] grid[1][j]第一列也就是 j1 时机器人只能一路向下走所以 dp[i][1] dp[i-1][1] grid[i][1]起点 dp[1][1] grid[1][1]。如果不想单独写边界判断也可以把 dp 数组多开一圈让 dp[0][j] 和 dp[i][0] 都等于一个很小的数比如 -inf这样当循环访问第一行或第一列时max 那一项自然取到有效方向的值。不过这种做法要小心因为格子值非负把边界设成 0 在这个题里也是安全的这算是一个小技巧后面细说。3. 代码实现在线教学C/C 完整写法3.1 二维DP的标准实现理解了方程之后代码就非常直白了。以 C 为例标准写法大概长这样#include cstdio #include algorithm using namespace std; const int MAXN 105; int grid[MAXN][MAXN]; int dp[MAXN][MAXN]; int main() { int m, n; while (scanf(%d%d, m, n) ! EOF) { for (int i 1; i m; i) { for (int j 1; j n; j) { scanf(%d, grid[i][j]); } } dp[1][1] grid[1][1]; for (int j 2; j n; j) { dp[1][j] dp[1][j-1] grid[1][j]; } for (int i 2; i m; i) { dp[i][1] dp[i-1][1] grid[i][1]; } for (int i 2; i m; i) { for (int j 2; j n; j) { dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1]); } } printf(%d\n, dp[m][n]); } return 0; }这里我把第一行和第一列的初始化单独拎出来了这也是大多数教材推荐的方式逻辑清楚不容易出错。注意一个细节我把数组下标从 1 开始而不是从 0 开始。这样做的最大好处是第一行和第一列的边界条件写起来跟坐标语义完全对应不需要在转移时反复判断 i-1、j-1 是否越界代码读起来也省心。这是做题时的一个实用习惯不管在哪个OJ我都建议尽量用 1-based 的方式处理网格类题目。3.2 边界处理的三种写法实际做题时边界处理其实可以有好几种写法我根据自己的习惯都列一下。第一种是上面那种把第一行、第一列单独初始化然后从 (2,2) 开始双重循环。这种方法最直观也最适合初学者缺点是代码稍微多点。第二种是统一循环但把两边界的初始值当成特殊情况去判断for (int i 1; i m; i) { for (int j 1; j n; j) { if (i 1 j 1) { dp[i][j] grid[i][j]; } else if (i 1) { dp[i][j] dp[i][j-1] grid[i][j]; } else if (j 1) { dp[i][j] dp[i-1][j] grid[i][j]; } else { dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1]); } } }这种写法把逻辑集中在一个双重循环里很多同学喜欢这么写因为它看起来很“统一”。但我个人的建议是作为练习可以考场或竞赛环境里还是优先用第一种因为人脑一次处理的分支越少越不容易出错。第三种是“哨兵法”也就是把 dp 数组第 0 行和第 0 列全部初始化为 0然后统一用同样的转移方程。因为这个题硬币值都是 0 或 1 的非负数所以 dp[i][0] 和 dp[0][j] 设成 0 不会污染结果。这样写代码最短for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1]); } }不过哨兵法在负数权值或少见场景下会出问题这题里没问题但如果你拿这套模板去改其他题一定得确认边界值是否安全。3.3 滚动数组优化从 O(mn) 空间到 O(n)二维DP在数据范围小的时候完全够用但很多变体题会把 m、n 的范围拉到几千甚至几万这时候 m×n 的二维数组就不一定扛得住了。好在观察转移方程你会发现dp[i][j] 只依赖三个东西当前行左边的状态 dp[i][j-1]上一行同一列的状态 dp[i-1][j]当前格子本身的权值 grid[i][j]。也就是说一旦我们按行从上到下、从左到右推进就只需要保留“上一行”和“本行左侧”的短期信息没必要把整张表都存下来。于是可以用一个一维数组 dp[j] 来滚动存储。核心代码长这样:int dp[MAXN]; for (int i 1; i m; i) { for (int j 1; j n; j) { if (j 1) { dp[j] grid[i][j]; } else { dp[j] grid[i][j] max(dp[j], dp[j-1]); } } } printf(%d\n, dp[n]);这里需要解释一下为什么能这样写当循环到当前行第 j 列时dp[j] 里存的还是上一行第 j 列的值也就是 dp[i-1][j]而 dp[j-1] 由于在本行已经先被更新过了所以存的是当前行第 j-1 列的值也就是 dp[i][j-1]。两者一取 max正好对应二维版本的转移式。第一列单独处理是因为 dp[1] 在进入内循环前是上一行的 dp[1]直接用 dp[j] grid[i][j] 就相当于把从上而下的路径继续累积。这个滚动数组的思维在后面的“最长公共子序列LCS”“矩阵路径最小和”一类题里几乎是标配建议一定亲手敲一遍。4. 踩坑实录常见错误与排查技巧4.1 边界初始化错误是最常见的AC拦路虎我见过很多同学交这题WA最后发现都是边界写错了。最常见的有两种第一种是忘记处理第一行或第一列直接让 (1,2) 这种格子执行 max(dp[0][2], dp[1][1])而 dp[0][2] 是未初始化的随机数结果自然就飘了。这种错误在本地环境甚至可能“碰巧”跑出正确答案因为有些编译器的全局变量默认是0但如果数组是局部数组那完全是垃圾值平台上一测就露馅。第二种是把起点 dp[1][1] 忘了加 grid[1][1]。很多同学写了转移方程后默认 dp[1][1] 是0最后输出 dp[m][n] 少算了一枚。这一枚硬币的误差非常隐蔽尤其是当棋盘起点本来就有硬币时你会觉得结果跟预期差1但又找不到哪里错。我的排查建议很简单拿到数据流后先在纸上手动算一遍小样例再用代码输出完整的 dp 表一行行核对。比如 3×3 的全1棋盘正确结果是 5路径长度5格每格1枚。如果你输出的 dp[1][j] 不是 1、2、3而是 0、1、2那十有八九是起点初始化丢了。4.2 多组输入处理的坑swustoj 这类OJ很多题都支持多组测试数据输入不会给你一个“有几组样例”的提示而是让你一直读到文件末尾。如果忘了 while 循环只读一组就输出那可能连样例都过不了因为第一组后面的输入没被消费但程序已经结束了输出自然不对。标准处理方式就是while (scanf(%d%d, m, n) ! EOF) { // 处理一组数据 }用 C 的 cin 写那就是while (cin m n) { // ... }还有个容易被忽略的点因为是多组输入dp 数组和 grid 数组每次都需要重新覆盖否则上一组数据残留的值会影响下一组。如果你按行读入并直接计算连 grid 数组都不需要一行行滚动进 dp 即可这样反而天然避免了残留问题。4.3 输入格式中的空格、换行与行尾这种纯数字的输入通常不会有大坑scanf(%d) 会跳过所有空白字符。但也有几个小细节值得提醒某些题目输入数据里可能混有制表符或者多个空格scanf 都能处理不用担心。如果题目给的是字母矩阵比如用 . 和 C 表示空和有硬币那就不能用 %d 逐个读了。这类变体在 UVA 和 POJ 上更常见读法是用 getchar 或者 scanf(%s) 逐行读字符串再逐字符判断。如果你用 cin 配 ios::sync_with_stdio(false) 加速记得不要和 scanf 混用否则可能因为缓冲问题导致读入错乱。我在实际做题时碰到数字矩阵统一用 scanf快且稳碰到字符矩阵则优先 getchar 逐字符读因为 scanf 对单个字符的处理经常会把换行符读进去需要额外 getchar 吸收容易出bug。4.4 变体扩展从一次收集到两次收集、从最大值到路径还原这道题本身是基础但它延伸出来的几个变体非常值得继续练。第一个变体是“机器人要走两遍”也就是两次从左上角到右下角两次路径经过的格子不能重复计数求两次路径能收集到的最大硬币总数。这个问题的标准解法是把两次行走放在同一个DP里用四维状态 dp[x1][y1][x2][y2] 表示第一次走到 (x1,y1)、第二次走到 (x2,y2) 时的最大收益再利用 x1y1 x2y2 的步数关系降成三维也就是所谓的“双路径DP”或“方格取数”问题。第二个变体是“路径还原”。如果你光想知道最大硬币数还不够还想输出某条最优路径经过了哪些格子那就在做DP的同时用一个 pre[i][j] 数组记录每个格子是从左还是从上转移过来的最后从右下角倒推回左上角再逆序输出即可。原理跟最短路径问题里的前驱数组完全一样。第三个变体是“带权值地形的小型策略游戏”比如机器人移动一步会消耗一点能量某些格子是障碍物不能走。这类题本质就是带限制的最短路或DP理解了基础题改改转移条件就行。我个人觉得把基础题做完之后起码要把“路径还原”和“双路径DP”这两个变体自己实现一遍因为它们几乎覆盖了网格型DP的所有常用套路面试和竞赛里都特别爱考。5. 从一道OJ题到一类DP问题的总结心得5.1 拿到这类题的“条件反射”式流程刷多了之后我遇到这种棋盘移动类问题脑子里已经形成了一套固定流程先看移动限制。只能向右向下那就是 DAG有向无环图上的最短路问题直接往DP想如果能上下左右走那就要考虑是不是得用 BFS、Dijkstra 或带状态压缩的DP。再看来回次数。走一次是基础DP走两次变成双路DP走无穷次就退化成了“最大费用流”或者“最大权闭合路经”这一类更复杂的模型。接着考虑状态维度。二维网格对应两维状态如果涉及方向、剩余步数、已收集数量等额外信息就加维度。最后想优化。能不能滚动数组能不能降维能不能用单调队列优化转移这套流程看起来简单但它能帮你快速把新题归类到已知模板上避免每次拿到题都从零开始想。5.2 为什么我建议你手写而不是直接复制题解说句掏心窝子的话这道题网上题解一大把代码网上也到处都能搜到但如果你只是复制粘贴提交AC了那这道题对你的价值基本就归零了。我的建议是先自己在纸上把状态定义、转移方程写出来然后不参考任何代码自己敲一遍交上去WA了也不怕再根据错误输出回去对照方程找出是边界问题还是转移问题。这个过程比AC本身重要得多因为你在训练的是“从问题到代码”的建模能力而不是“从代码到答案”的复现能力。我记得当时我练这道题的时候第一遍交上去是WA因为我把下标写成了从0开始结果边界处理一团糟。后来我换回1-based重新捋了一遍初始化逻辑一次性AC。那次之后我见了网格DP题就条件反射式地用1-based 单独处理边界再也没有在这个坑里摔过第二次。5.3 最后分享一个提速小技巧如果你的棋盘规模比较大比如 m、n 都到了 1000 以上除了滚动数组还可以在 IO 上下功夫。把 scanf 换成 getchar 手写读整数性能提升非常明显。虽然日常OJ题用不上但碰到极限数据或者参加比赛时这就是拉开差距的地方。写一个简单的手写正整数读取函数inline int readInt() { int x 0; char c getchar(); while (c 0 || c 9) c getchar(); while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x; }配合滚动数组这道题即便 m、n 开到几万也能在很短时间内跑完内存占用还特别小O(n) 级别的空间就搞定了。回到我自己刷题的经验上来学术性的东西说多了容易飘落到地面上就是一句话dp[i][j] 的每一格都该是你亲手推过、亲手验证过的而不是题解上抄下来的。把 Coin-collecting by robot 这道题吃透后续那些挂着“机器人在网格里干各种事”的题目你再看它们基本就是在看同一个故事换了几件衣服而已。