动态规划路径类 DP 入门：3 道经典例题详解

迷雾森林

这道题是在网格中求方案数，且存在障碍物（树）。

状态定义 dp[i][j] 表示从 (m, 1) 格子走到 (i, j) 格子的方案总数。

状态转移 题目规定只能向上或向右走。假设当前格子为 (i, j)，则上一个格子可能是 (i, j-1) 或者 (i+1, j)。因此： dp[i][j] = dp[i][j - 1] + dp[i + 1][j]

需要注意的是，如果当前位置是树（障碍），则无法通过，方案数为 0。只有空地才能进行状态转移。

边界与初始化 由于填表时会访问左边和下边格子，全局定义的 dp 数组默认初始化为 0，符合要求。我们需要将起点 dp[m][1] 初始化为 1，表示从起点出发有一种方案。注意在填表时跳过起点，避免重复计算。

填表顺序 根据依赖关系，需要从下往上填每一行，每行内从左往右。

注意事项 答案需要对 2333 取模。

代码实现

#include <iostream>
#include <stdio.h>
using namespace std;

const int N = 3010;
const int MOD = 2333;
int m, n;
int a[N][N], dp[N][N];

int main() {
    // 处理输入
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    // 初始化起点
    dp[m][1] = 1;

    // 按序填表：从下往上，从左往右
    for (int i = m; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            // 起点已初始化，跳过
            if (i == m && j == 1) continue;
            
            // 如果是空地，累加方案数并取模
            if (a[i][j] == 0) {
                dp[i][j] = (dp[i][j - 1] + dp[i + 1][j]) % MOD;
            }
        }
    }

    // 输出结果
    cout << dp[1][n];
    return 0;
}

过河卒

这是一道经典的棋盘路径问题，卒子不能经过马的控制点。

坐标偏移 题目强制从 (0, 0) 开始，为了处理方便并避免负索引，我们将输入的 B 点坐标和马的坐标统一加 1，相当于将整个棋盘平移，从 (1, 1) 开始填表。

状态定义 dp[i][j] 表示从 (1, 1) 走到 (i, j) 的方案数。

状态转移 卒子只能向下或向右走： dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

同样，如果当前位置是马的控制点，则方案数为 0，不参与转移。

边界与初始化 dp 数组将 dp[1][1] 置为 1。对于马的控制点，我们借助方向向量将马周围 9 个点（包括马本身）标记为不可通行。

数据类型 方案数可能非常大，达到阶乘级别，务必使用 long long 类型存储 dp 数组。

代码实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 25;
int n, m, c, d;
int a[N][N];
LL dp[N][N];

// 马走日字的方向向量
int dx[8] = {2, 2, 1, 1, -1, -1, -2, -2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};

int main() {
    // 处理输入
    cin >> n >> m >> c >> d;
    n++, m++, c++, d++; // 坐标整体偏移

    // 初始化起点
    dp[1][1] = 1;

    // 标记马的控制点
    for (int i = 0; i < 8; i++) {
        a[c + dx[i]][d + dy[i]] = 1;
    }
    a[c][d] = 1; // 马所在的点也不能走

    // 按序填表：从左往右，从上往下
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            
            // 只有不是控制点时才进行转移
            if (a[i][j] == 0) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
    }

    // 输出结果
    cout << dp[n][m] << endl;
    return 0;
}