牛客对应题目链接：[NOIP2002 普及组] 过河卒_牛客题霸_牛客网
一、分析题目
简单路径 dp 问题，相当于是有障碍物的路径类问题，标记⾛到障碍物上的⽅法数为 0 即可。
1、dp[i][j] 状态表示
从 [0, 0] 位置出发，到达 [i, j] 位置，一共有多少种方法。
2、状态转移方程
dp[i][j]：
- 0（如果走不到就为 0）
- dp[i-1][j] + dp[i][j-1]（因为卒只能向下或者向右走）
3、初始化
dp[0][0] = 1
（下面的代码是因为改变了映射关系，所以上面的含义可能会有一点变化，比如下面设定的 dp[0][1] = 1，是为了能通过递推关系得到 dp[1][1] = 1）
二、代码
//值得学习的代码 #include <iostream> using namespace std; int n, m, x, y; long long dp[25][25]; int main() { cin >> n >> m >> x >> y; // 方便后续下标的映射 x += 1; y += 1; dp[0][1] = 1; // 原始的棋盘是[0, n][0, m] // 我们的dp表是多一行、多一列的 for(int i = 1; i <= n + 1; i++) { for(int j = 1; j <= m + 1; j++) { // 马的控制点以及马本身的位置 if(i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x && j == y)) { dp[i][j] = 0; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } cout << dp[n + 1][m + 1] << endl; return 0; }
三、反思与改进
最近一做矩阵类型的题就总是先想到 bfs，不过这道题用 dp 来解，我确实是想不到。估计这道题我理解错含义了，因为我不管怎么罗列几个样例，结果都是 0，怎么也走不出原码的控制范围，后面总结的时候再仔细看题意，发现漏了一个条件（x1 != x，y1 != y）审题不仔细啊！多去看看跟路径相关的 dp 类型题。
