路径类 DP 入门：3 道经典例题详解（最小路径和、迷雾森林、过河卒）

迷雾森林

这道题求的是从起点到终点的方案数，且只能向上或向右走，遇到树不能通行。

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

状态转移 根据移动规则，到达 (i, j) 的前一步可能是 (i, j-1) 或 (i+1, j)。如果当前格子是空地（值为 0），则累加前驱状态的方案数；如果是树（值为 1），则方案数为 0。

dp[i][j] = dp[i][j - 1] + dp[i + 1][j] （当 a[i][j] == 0 时）

边界与初始化 由于需要访问左边和下边格子，我们按从下往上、每行从左往右的顺序填表。dp 数组全局定义默认为 0，无需额外 memset。将起点 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) 出发，马控制周围 9 个点，求不经过马控制点的方案数。

坐标偏移技巧 题目强制从 (0, 0) 开始，为了处理数组越界方便，我们将所有输入的坐标统一加 1，相当于棋盘整体平移，从 (1, 1) 开始填表。

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

状态转移 卒只能向下或向右，方程为： dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

障碍物处理 利用方向向量标记马的控制点。如果某点是马的控制点（包括马本身），则保持 dp 值为 0，不参与累加。

数据类型 方案数增长极快，必须使用 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];

// 马的 8 个控制方向
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;
    // 坐标整体 +1，避免边界判断
    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;
}

这三道题涵盖了路径 DP 中最核心的几个考点：边界初始化、取模运算、坐标偏移防越界以及障碍物的特殊处理。掌握这些模式后，面对类似的网格 DP 问题就能快速找到切入点。