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

迷雾森林

题目描述

思路解析

1. 状态表示 dp[i][j] 表示从 [m, 1] 格子走到 [i, j] 格子时的方案数。

2. 状态转移方程 规定只能向上或向右走。若当前格子为空地（值为 0），则方案数为左侧和下侧格子方案数之和；若为树（值为 1），则不可达，方案数为 0。 dp[i][j] = dp[i][j - 1] + dp[i + 1][j] (当 a[i][j] == 0)

3. 初始化 由于数组全局定义默认为 0，无需额外清空。起点 dp[m][1] 设为 1，作为累加的基准。注意填表时跳过起点。

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

5. 输出结果 dp[1][n]

注意：答案需要对 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() {
    scanf("%d%d", &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;
            }
        }
    }

    printf("%d\n", dp[1][n]);
    return 0;
}

过河卒

题目描述

思路解析

本题强制从 [0, 0] 开始，为了方便处理数组越界，我们将输入的坐标统一加 1，相当于棋盘整体平移，从 [1, 1] 开始填表。

1. 状态表示 dp[i][j] 表示从 [1, 1] 走到 [i, j] 的方案数。

2. 状态转移方程 卒只能向下或向右移动： dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 仅当目标点不是马的控制点时才执行转移，否则保持 0。

3. 初始化 dp[1][1] 置为 1。使用方向向量标记马及其控制点（共 9 个点）为障碍，存入 a 数组。

4. 填表顺序 从左往右，从上往下。

5. 输出结果 dp[n][m]

注意：方案数可能很大，需使用 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++) {
        if (c + dx[i] >= 1 && c + dx[i] <= n && d + dy[i] >= 1 && d + dy[i] <= m)
            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;
}

这三道题涵盖了路径 DP 中最常见的三种情况：带权最短路、障碍计数以及特殊移动限制。掌握状态定义和转移方程的推导逻辑，比死记硬背代码更重要。在实际调试中，务必注意数组越界和数据溢出问题。