过河卒递推解法：从DFS枚举到动态规划路径计数

第一次在《信息学奥赛一本通》提高篇里看到第1314题“过河卒”的时候，我其实有点不以为然：卒子从A点走到B点，每步只能向右或向下，这不就是一道DFS模板题吗？然后我就用递归把所有路径枚举了一遍，跑样例稳稳通过，心里还挺美。结果换一组n=15、m=15的数据一跑，程序直接卡成幻灯片。那一刻我才意识到，这道被称为“递推经典”的题，真正的门槛不是走法，而是你怎么从“枚举路径”切换到“统计路径”。

这篇文章把我刷这道题的完整过程拆开来讲：递推方程怎么一步步推出来、马的攻击范围有哪些易错细节、参考代码长什么样、常见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)，不考虑任何障碍，它一共要走n+m步，其中必须包含n步向下和m步向右。路径总数直接就是组合数C(n+m, n)。

当n=m=20时，C(40,20)约等于1.37×10^11。也就是说，最坏情况下有1370亿条路径。DFS要一条条去枚举，每一层递归还要做坐标判断和边界判断，这个计算量别说一秒，一分钟都不一定能跑完。

而递推的做法就完全不一样。棋盘总共只有(n+1)×(m+1)个格子，n=m=20时也就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]，当i=0或者j=0时会访问到无效坐标。这时候就需要特殊处理：第0行的格子只能从左边过来，第0列的格子只能从上面过来，起点(0,0)的f值设为1。

这里面有一个很容易被忽略的坑：如果第0行上有一个点是禁区，那么这个点右边的所有格子都到不了。因为第0行的格子只能从左往右走，一旦必经之路被封死，后面全是0。第0列同理。很多同学递推公式背得很熟，却在这个小细节上栽跟头，自己构造数据一测就露馅。

2.3 一个4x4小棋盘的手动推演

光讲理论不够直观，我拿一个具体的例子手动推一遍。假设n=3、m=3，也就是一个4×4的棋盘，马在(2,0)的位置。

先把棋盘标记图画出来，H表示马，X表示卒不能走的格子，S是起点，T是终点：

第三步：按行从上往下推f值，初始f[0][0] = 1。

• 第0行：(0,0)=1；(0,1)是禁区，f=0；因为(0,1)已经是0，它右边(0,2)、(0,3)只能从左边来，所以全是0。
• 第1行：(1,0)只能从(0,0)下来，f=1；(1,1)=f(0,1)+f(1,0)=0+1=1；(1,2)是禁区，f=0；(1,3)=f(0,3)+f(1,2)=0。
• 第2行：(2,0)是马所在点，f=0；(2,1)=f(1,1)+f(2,0)=1；(2,2)=f(1,2)+f(2,1)=0+1=1；(2,3)=f(1,3)+f(2,2)=0+1=1。
• 第3行：(3,0)=f(2,0)=0；(3,1)=f(2,1)+f(3,0)=1；(3,2)是禁区，f=0；(3,3)=f(2,3)+f(3,2)=1+0=1。

最终答案是1。你看，整个推演过程没有任何“魔法”，就是一行一行、一列一列地填表，每一步都有明确依据。自己亲手推一遍之后，你再去看代码，就不是背代码，而是知道每一行代码在做什么。

3. 马的攻击范围：三个让我翻车的细节

3.1 “马所在的点”这五个字最容易漏

题目原话是：“马所在的点和马一步能跳到的点，卒不能通过”。这句话信息量很大，但很多人只记住了后半句。

我第一次写的时候就是如此。我用一个二维bool数组标记禁区，只把马的8个跳点标记成true，完全忘了马自己站着的那个格子。结果呢？跑样例居然也是对的，因为样例里马的位置恰好不在关键路径上。直到我自己随手构造了一组数据，让马正好横在必经之路上，输出立刻不对劲。

排查了半天才意识到问题。正确的做法是：马的坐标(x,y)本身也要标记成禁区。换句话说，要标记的点不是8个，而是9个——马自己加上它能跳到的8个点。这种错误特别隐蔽，因为样例数据往往不够“毒”，不会专门卡你这种边界情况。

3.2 日字跳法的8个偏移量和越界判断

马的走法是“日”字，也就是横向走1格、纵向走2格，或者横向走2格、纵向走1格。以马所在位置(x,y)为中心，8个跳点的坐标偏移如下：

这里第二个坑就来了：马如果靠近棋盘边缘，有些跳点会在棋盘外面。比如马在(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到n+1、1到m+1。起点从(0,0)变成(1,1)，马的坐标也跟着加1，所有跳点坐标也加1。

这样做的好处是什么？第0行和第0列变成了全0的“虚拟边界”，你在递推时不需要再判i>0、j>0了。对于起点，可以设f[0][1]=1，想象成在起点左边多了一个虚拟格子，那里有一条路径，起点通过它获得初值。两层循环直接从i=1和j=1开始跑，边界条件天然满足。

用这种方式写二维递推，代码会简洁不少。尤其配合滚动数组使用，效果更好。我在第四章给出的是最直观的“从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？因为n=m=20时，没有障碍的路径数是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到怀疑人生的几个现场

我把刷这道题时遇到过的、以及身边朋友踩过的坑统一列出来，方便你对照排查。这些原因覆盖了绝大多数提交错误。

最后一个情况是我特别想强调的。如果马所在位置或者马的跳点恰好覆盖了起点(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]到底哪个是上一行的值，哪个是当前行的值？关键在于循环顺序。

外层循环从i=1到n，内层循环从j=1到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]，但背不下为什么是这个方程。一旦题目的走法、障碍规则、棋盘形状发生变化，背模板的人就会立刻卡住。这也是我写这篇文章、把整个推导过程掰开揉碎讲清楚的原因。

刷完过河卒这道题之后，我习惯性地把二维数组改成一维滚动数组，再跑了一遍对拍脚本，确认两种写法答案完全一致。如果你现在也卡在这一章，我的建议是先把递推表手推顺手，再动手写代码。过河卒最大的价值，不是让你记住一个公式，而是在你亲手把“搜索”改成“递推”的那个瞬间，动态规划的入门才算真正完成。