第一次在《信息学奥赛一本通》提高篇里看到第1314题“过河卒”的时候我其实有点不以为然卒子从A点走到B点每步只能向右或向下这不就是一道DFS模板题吗然后我就用递归把所有路径枚举了一遍跑样例稳稳通过心里还挺美。结果换一组n15、m15的数据一跑程序直接卡成幻灯片。那一刻我才意识到这道被称为“递推经典”的题真正的门槛不是走法而是你怎么从“枚举路径”切换到“统计路径”。这篇文章把我刷这道题的完整过程拆开来讲递推方程怎么一步步推出来、马的攻击范围有哪些易错细节、参考代码长什么样、常见WA原因有哪些最后再聊聊滚动数组优化和它能衍生出的同类题。无论你是刚开始学递推的新手还是刷一本通卡壳了想找思路的人都可以直接照着推一遍。1. 这道题为什么不能靠爆搜硬过1.1 先看清楚题目在说什么原题的描述很简短棋盘上有A、B两个点A点是卒的起点坐标是(0,0)B点是目标点坐标是(n,m)。卒行走的规则是只能向下或向右走一步。棋盘上的某个位置有一匹马马走的是“日”字。卒不能走到马所在的位置也不能走到马一步能跳到的8个位置。现在要算的是从A点到B点一共有多少条不同的路径。输入就四个整数n、m、马的x坐标、马的y坐标。n和m的范围通常不超过20。输出是一个整数表示路径条数。这个题面本身不难理解难的是你第一眼会用什么思路去做。我当时的直觉是这不是一个典型的迷宫题吗从起点出发每步尝试向下或向右遇到禁区就回头走到终点就ans。DFS写起来非常顺手代码也很短跑测试样例完全没问题。但问题恰恰出在这里。测试样例很小DFS能秒过容易让你误以为这个解法就是正解。等你真正提交或者换大一点的n、m去跑才会发现这个思路的时间复杂度是个无底洞。1.2 暴搜复杂度一分钟都等不出来的原因为什么DFS不行我们来算一笔账。卒从(0,0)走到(n,m)不考虑任何障碍它一共要走nm步其中必须包含n步向下和m步向右。路径总数直接就是组合数C(nm, n)。当nm20时C(40,20)约等于1.37×10^11。也就是说最坏情况下有1370亿条路径。DFS要一条条去枚举每一层递归还要做坐标判断和边界判断这个计算量别说一秒一分钟都不一定能跑完。而递推的做法就完全不一样。棋盘总共只有(n1)×(m1)个格子nm20时也就441个点。每个点只需要做一次加法总计算量是O(n×m)瞬间出结果。这就是这道题的核心教学意义同样一个问题站在“枚举”的角度和站在“统计”的角度复杂度天差地别。过河卒可以说是你接触的第一批“用递推代替搜索”的题目理解这个转变比记住任何一个公式都重要。2. 递推公式是推出来的不是背出来的2.1 路径来源只有两个方向从状态定义开始想明白为什么DFS不行之后就要换一个视角我不关心具体某条路径长什么样我只想知道“到某个格子一共有多少种走法”。设f[i][j]表示从起点(0,0)走到格子(i,j)的路径条数。那么关键问题来了f[i][j]怎么算因为卒只能向下走或者向右走所以反过来想它从哪个格子能一步走到(i,j)答案只有两个——从上面的格子(i-1,j)往下走到达或者从左边的格子(i,j-1)往右走到达。于是就有了最核心的转移方程f[i][j] f[i-1][j] f[i][j-1]这个方程成立的前提是到达(i-1,j)和(i,j-1)的路径数已经算好而且这两个格子本身是可达的。用竞赛的话来说就是这个问题具备无后效性一旦f[i][j]算出来后面所有的计算都只依赖这个结果不需要再关心之前是怎么走到这里的。这正是递推动态规划能成立的根本原因。2.2 障碍点和边界行公式之外的第三个隐藏条件上面的方程是最理想的情况但题目里有马有马的地方和它能跳到的地方都不能走。这个约束怎么处理很简单。对于任何一个格子如果它是马的禁区那么f[i][j]直接置为0。因为卒根本走不到这个格子自然也不可能有路径数。否则才使用上面的转移方程。边界条件也要单独想清楚。第0行上方的格子不存在第0列左边的格子也不存在。如果直接用f[i][j] f[i-1][j] f[i][j-1]当i0或者j0时会访问到无效坐标。这时候就需要特殊处理第0行的格子只能从左边过来第0列的格子只能从上面过来起点(0,0)的f值设为1。这里面有一个很容易被忽略的坑如果第0行上有一个点是禁区那么这个点右边的所有格子都到不了。因为第0行的格子只能从左往右走一旦必经之路被封死后面全是0。第0列同理。很多同学递推公式背得很熟却在这个小细节上栽跟头自己构造数据一测就露馅。2.3 一个4x4小棋盘的手动推演光讲理论不够直观我拿一个具体的例子手动推一遍。假设n3、m3也就是一个4×4的棋盘马在(2,0)的位置。先把棋盘标记图画出来H表示马X表示卒不能走的格子S是起点T是终点行/列0列1列2列3列0行SXoo1行ooXo2行Hooo3行ooXT第三步按行从上往下推f值初始f[0][0] 1。第0行(0,0)1(0,1)是禁区f0因为(0,1)已经是0它右边(0,2)、(0,3)只能从左边来所以全是0。第1行(1,0)只能从(0,0)下来f1(1,1)f(0,1)f(1,0)011(1,2)是禁区f0(1,3)f(0,3)f(1,2)0。第2行(2,0)是马所在点f0(2,1)f(1,1)f(2,0)1(2,2)f(1,2)f(2,1)011(2,3)f(1,3)f(2,2)011。第3行(3,0)f(2,0)0(3,1)f(2,1)f(3,0)1(3,2)是禁区f0(3,3)f(2,3)f(3,2)101。最终答案是1。你看整个推演过程没有任何“魔法”就是一行一行、一列一列地填表每一步都有明确依据。自己亲手推一遍之后你再去看代码就不是背代码而是知道每一行代码在做什么。3. 马的攻击范围三个让我翻车的细节3.1 “马所在的点”这五个字最容易漏题目原话是“马所在的点和马一步能跳到的点卒不能通过”。这句话信息量很大但很多人只记住了后半句。我第一次写的时候就是如此。我用一个二维bool数组标记禁区只把马的8个跳点标记成true完全忘了马自己站着的那个格子。结果呢跑样例居然也是对的因为样例里马的位置恰好不在关键路径上。直到我自己随手构造了一组数据让马正好横在必经之路上输出立刻不对劲。排查了半天才意识到问题。正确的做法是马的坐标(x,y)本身也要标记成禁区。换句话说要标记的点不是8个而是9个——马自己加上它能跳到的8个点。这种错误特别隐蔽因为样例数据往往不够“毒”不会专门卡你这种边界情况。3.2 日字跳法的8个偏移量和越界判断马的走法是“日”字也就是横向走1格、纵向走2格或者横向走2格、纵向走1格。以马所在位置(x,y)为中心8个跳点的坐标偏移如下方向x偏移y偏移11222132-141-25-1-26-2-17-218-12这里第二个坑就来了马如果靠近棋盘边缘有些跳点会在棋盘外面。比如马在(0,0)它的跳点里有(-1,2)、(-2,1)这种坐标根本不存在于棋盘上。如果你不加判断直接标记blocked[nx][ny]true轻则数组越界重则程序直接崩溃。解决办法有两种。第一种是每次计算跳点坐标后判断一下是否在合法范围内即nx 0 nx n ny 0 ny m只有在范围内才标记。第二种是干脆把棋盘数组开大一圈比如开到25×25然后把所有坐标整体平移让越界的跳点落在数组的无效区域里不影响后续计算。这两种方案在后面的代码里我都会给出。3.3 坐标整体平移省掉边界判断的写法说到平移这里有一个非常实用的小技巧很多老竞赛选手写DP时都喜欢用。具体做法是把所有坐标整体加1。原来棋盘的范围是0到n、0到m平移后变成1到n1、1到m1。起点从(0,0)变成(1,1)马的坐标也跟着加1所有跳点坐标也加1。这样做的好处是什么第0行和第0列变成了全0的“虚拟边界”你在递推时不需要再判i0、j0了。对于起点可以设f[0][1]1想象成在起点左边多了一个虚拟格子那里有一条路径起点通过它获得初值。两层循环直接从i1和j1开始跑边界条件天然满足。用这种方式写二维递推代码会简洁不少。尤其配合滚动数组使用效果更好。我在第四章给出的是最直观的“从0开始条件判断”版本第五章的滚动数组版本会采用坐标平移方便你们对比两种写法的差异。4. 参考代码、对拍验证和常见WA原因4.1 二维DP完整代码先给出最经典的二维DP写法思路清晰适合作为学习模板。#include iostream using namespace std; long long f[25][25]; // 路径数注意用long long bool blocked[25][25]; // 禁区标记 int main() { int n, m, x, y; cin n m x y; // 偏移数组第一个(0,0)代表马自己所在的位置 int dx[] {0, 1, 1, 2, 2, -1, -1, -2, -2}; int dy[] {0, 2, -2, 1, -1, 2, -2, 1, -1}; for (int k 0; k 9; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx n ny 0 ny m) { blocked[nx][ny] true; } } f[0][0] 1; // 起点初始化为1 for (int i 0; i n; i) { for (int j 0; j m; j) { if (blocked[i][j]) { f[i][j] 0; } else { if (i 0) f[i][j] f[i - 1][j]; if (j 0) f[i][j] f[i][j - 1]; } } } cout f[n][m] endl; return 0; }这里有几个细节值得强调。第一f数组为什么用long long因为nm20时没有障碍的路径数是C(40,20)大约是1378亿早就超出了int的21亿上限。如果你用int样例可能侥幸通过数据一大必然WA。第二f[0][0]1初始化放在标记禁区之后循环到(0,0)时如果它恰好是禁区会在循环里被重新赋值为0逻辑正确。4.2 用DFS对拍验证小数据代码写完之后怎么确认它正确光靠题目给的样例远远不够。我的习惯是写一个暴力DFS程序专门用来对拍小数据。暴力DFS的核心代码很简单long long dfs(int i, int j) { if (i n || j m) return 0; if (blocked[i][j]) return 0; if (i n j m) return 1; return dfs(i 1, j) dfs(i, j 1); }这个函数不干别的就是把所有可能的路径全部枚举一遍统计总数。由于它不做任何优化只适合n、m都很小的情况比如不超过8。但正因为它的逻辑简单粗暴几乎不可能写错所以可以用来验证DP代码的正确性。操作流程是这样的手写或者写个小脚本生成几十组随机小数据每组数据的n、m都在5以内马的坐标随机生成。然后把每组数据分别交给DFS程序和DP程序跑用脚本对比输出。只要有一组输出不一致就说明DP代码有问题需要回到2.2小节的推演逻辑去排查。这个方法非常实用。很多同学写完代码只测样例样例过了就提交WA了才回来调。但样例覆盖不了所有分支尤其是禁区挡路、马控制起点这种极端情况。对拍能在几分钟内帮你找出绝大多数隐藏bug建议从这道题开始养成习惯。4.3 WA到怀疑人生的几个现场我把刷这道题时遇到过的、以及身边朋友踩过的坑统一列出来方便你对照排查。这些原因覆盖了绝大多数提交错误。错误现象根本原因正确做法大数据输出负数或明显偏大用了int路径数超过int上限改用long long部分样例对、部分样例错只标记了8个跳点漏了马所在点把马本身也标记为禁区程序运行异常或数组越界标记跳点时没有判断棋盘边界每次标记前检查nx、ny是否在范围内输入顺序弄反把n、m当成马的坐标或把x、y当成B点坐标熟读题面输入是B的坐标n、m然后才是马的坐标x、y起点恰好被马控制但输出不为0初始化f[0][0]1后没有检查起点是否在禁区循环遍历时会覆盖为0确认循环覆盖了起点最后一个情况是我特别想强调的。如果马所在位置或者马的跳点恰好覆盖了起点(0,0)那么从起点出发的那一步就走不出去理论上答案就是0。很多人在初始化f[0][0]1之后直接开始递推如果代码里没有在循环内把禁区格子重新置0这个1就会被错误地传递下去。我在4.1的代码里把禁区判断放在循环内部就是为了覆盖这个场景。你写自己的代码时也要注意这一点。5. 滚动数组优化和过河卒的同类变式5.1 一维滚动数组空间省下来思路不省二维DP的空间是O(n×m)n、m只有20的时候完全无所谓但如果你以后遇到棋盘尺寸更大的同类题或者想练习一下空间优化的思路滚动数组是绕不开的。核心想法是这样的递推f[i][j]只用到了f[i-1][j]和f[i][j-1]也就是当前行的左边一格和上一行的同一列。至于更早的行算完之后就再也用不到了。那我们完全可以只开一维数组用一行数据滚动更新。下面是滚动数组版本的完整代码使用了坐标整体平移的技巧#include iostream using namespace std; long long f[25]; bool blocked[25][25]; int main() { int n, m, x, y; cin n m x y; // 所有坐标整体右移一格留出虚拟边界 n; m; x; y; int dx[] {0, 1, 1, 2, 2, -1, -1, -2, -2}; int dy[] {0, 2, -2, 1, -1, 2, -2, 1, -1}; for (int k 0; k 9; k) { int nx x dx[k]; int ny y dy[k]; if (nx 1 nx n ny 1 ny m) { blocked[nx][ny] true; } } f[1] 1; // 虚拟起点 for (int i 1; i n; i) { for (int j 1; j m; j) { if (blocked[i][j]) { f[j] 0; } else { f[j] f[j] f[j - 1]; } } } cout f[m] endl; return 0; }很多人第一次看到f[j] f[j] f[j-1]会懵右边两个f[j]到底哪个是上一行的值哪个是当前行的值关键在于循环顺序。外层循环从i1到n内层循环从j1到m。当你在处理第i行第j列时右边的f[j]还是上一行遗留的值也就是f[i-1][j]而右边的f[j-1]因为j从小到大更新已经在本次循环里被覆盖过了正好是f[i][j-1]。所以这一句的本质就是f[i][j] f[i-1][j] f[i][j-1]只是借同一个数组的空间罢了。空间从二维降到一维从O(n×m)变成O(m)时间仍然是O(n×m)。如果以后遇到m特别大但n较小的场景这个优化就很值。5.2 数据再大时的高精度方向假设这道题的n、m从20变成100甚至1000会发生什么路径数会指数级增长long long也撑不住。此时你需要的是高精度加法。竞赛中常见的高精度方案是把每个格子的路径数存成一个大数用一个数组或者字符串表示。做加法的时候按位相加、处理进位。这时候转移方程本身完全不变变的只是“f[i][j] f[i-1][j] f[i][j-1]”中的加法从普通整数加法变成了大数加法。给你一个思路参考可以用一个结构体或者vector 来表示大数每一位存一个0到9的数字加法时先逐位相加再统一处理进位。也可以用Python写题解Python原生整数没有溢出问题n、m稍大一点也能跑但竞赛里常用的是C所以大数加法值得专门练一练。这道题的数据范围是20不需要高精度但它把“数据变大后怎么办”这个问题摆在了你面前。知道什么时候该用什么工具也是刷题积累的一部分。5.3 过河卒还能怎么变从这道题开始的延伸把过河卒理解透彻之后你会发现很多递推题都是它的变种换汤不换药。最常见的一种变形是棋盘上不止一匹马而是有多个障碍物。解法一模一样只是在标记禁区时循环处理每个障碍物即可。第二种变形卒的走法改了比如允许它向下、向右、向右下斜走。这时状态转移方程就要增加一个方向f[i][j] f[i-1][j] f[i][j-1] f[i-1][j-1]。方程跟着走法变但推导思路完全一致。第三种变形给棋盘加一个“禁入区域”比如某个矩形区域内的点都不能走。标记禁区时多套一层循环即可。还有一类题会反过来问给你一个路径数K求某条特定路径。这就涉及构造和字典序枚举了属于进阶方向。我个人认为刷题最忌讳的是背模板。你能背下f[i][j] f[i-1][j] f[i][j-1]但背不下为什么是这个方程。一旦题目的走法、障碍规则、棋盘形状发生变化背模板的人就会立刻卡住。这也是我写这篇文章、把整个推导过程掰开揉碎讲清楚的原因。刷完过河卒这道题之后我习惯性地把二维数组改成一维滚动数组再跑了一遍对拍脚本确认两种写法答案完全一致。如果你现在也卡在这一章我的建议是先把递推表手推顺手再动手写代码。过河卒最大的价值不是让你记住一个公式而是在你亲手把“搜索”改成“递推”的那个瞬间动态规划的入门才算真正完成。