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

迷雾森林

本题要求在只能向上或向右走的前提下，计算从起点到终点的方案数。遇到树（障碍）不能通行。

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

状态转移 根据移动规则，到达 [i, j] 的前一步可能是 [i, j-1]（左）或 [i+1, j]（下）。注意这里的坐标系方向，题目描述是从下往上走。 若当前格子是空地（值为 0），则 dp[i][j] = dp[i][j-1] + dp[i+1][j]；若是树（值为 1），则方案数为 0。 需注意答案需要对 2333 取模。

初始化 全局数组默认初始化为 0。将起点 dp[m][1] 设为 1。

填表顺序 因为依赖下方和左方的数据，所以需要从下往上遍历每一行，每行内从左往右。

#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] 表示从起点走到 [i, j] 的方案数。

状态转移 dp[i][j] = dp[i][j-1] + dp[i-1][j]。 前提是当前格子不是马的控制点。如果是马的控制点，保持初始值 0 即可。

初始化 dp[1][1] 设为 1。使用方向向量标记马的 9 个控制点（包括马本身）在辅助数组 a 中为 1。

注意事项 方案数可能很大，需使用 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;
}