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

迷雾森林

题目描述 在一个 m x n 的网格中，有些格子有树（不能走），有些是空地。规定只能向上或向右走。求从左下角到右上角的方案数。答案需要对 2333 取模。

思路解析

1. 状态表示 dp[i][j] 表示从起点 (m, 1) 走到 (i, j) 的方案数。
2. 状态转移 根据行走规则，到达 (i, j) 的上一步可能是 (i, j-1)（右边来的）或者 (i+1, j)（下边来的）。 若当前格子是空地（值为 0），则累加两个来源的方案数；若是树（值为 1），则方案数为 0。 方程： if (a[i][j] == 0) dp[i][j] = (dp[i][j-1] + dp[i+1][j]) % MOD; else dp[i][j] = 0;
3. 初始化 全局数组默认初始化为 0。需要将起点 dp[m][1] 设为 1。
4. 填表顺序 因为依赖下方和左方的数据，所以需要从下往上遍历每一行，每行内从左往右。
5. 结果输出 答案为 dp[1][n]。

代码实现

#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;
}

过河卒

题目描述 棋盘上有马，卒从左下角出发，只能向右或向下走。马可以控制周围 8 个点（包括自身）。求卒到达右上角的方案数。

思路解析

1. 坐标偏移 题目要求从 (0, 0) 开始，但为了避开数组越界检查，我们将所有输入的坐标统一加 1，相当于整个棋盘平移，从 (1, 1) 开始填表。
2. 状态表示 dp[i][j] 表示从起点走到 (i, j) 的方案数。
3. 状态转移 卒只能从上方或左方过来。 dp[i][j] = dp[i][j-1] + dp[i-1][j] 前提是当前格子不是马的控制点。
4. 初始化 dp[1][1] 设为 1。 使用方向向量标记马的控制点，将这些点对应的 a 数组置为 1，表示不可达。
5. 注意事项 方案数可能很大，需使用 long long 类型存储。

代码实现

#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;
}