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

路径类 DP 是线性 DP 的一种，通常在一个 n × m 的矩阵中设定行走规则，研究从起点到终点的方案数、最小路径和或最大路径和等问题。入门阶段的《数字三角形》其实也属于这一范畴。

矩阵的最小路径和

题目要求计算从左上角走到右下角的最小路径和，每次只能向右或向下移动。

状态定义 dp[i][j] 表示从 [1, 1] 格子走到 [i, j] 格子时，所有方案下的最小路径和。

状态转移 考虑最后一步到达 [i, j] 的情况，只能从上方 [i-1, j] 或左方 [i, j-1] 过来。因此 dp[i][j] 的值取决于这两个位置的最小值加上当前格子的权值 a[i][j]。 转移方程为：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]

初始化与边界 由于填表时需要访问左边和上边的格子，为了避免数组越界，我们将第 0 行和第 0 列初始化为无穷大。这样在取最小值时，永远不会选中这些无效位置。同时，将 dp[1][1] 初始化为 a[1][1]，因为起点的代价就是它本身。注意在循环中跳过 [1, 1] 格子，防止被重复覆盖。

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

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510;
int n, m;
int a[N][N], dp[N][N];

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

    // 初始化：第 0 行和第 0 列设为无穷大
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[1][1] = a[1][1];

    // 依序填表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }

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

迷雾森林

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

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

状态转移 根据行走规则，到达 [i, j] 的上一步可能是 [i, j-1]（右边）或者 [i+1, j]（下边）。如果当前位置是空地（a[i][j] == 0），则方案数为两者之和；如果是树（a[i][j] == 1），则方案数为 0。 转移方程： 若 a[i][j] == 0: dp[i][j] = dp[i][j - 1] + dp[i + 1][j] 若 a[i][j] == 1: dp[i][j] = 0

初始化 全局数组默认初始化为 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] 出发，马在特定位置控制周围 9 个点，卒不能经过马的控制点。

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

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

状态转移 卒只能向下或向右走，所以 dp[i][j] = dp[i][j-1] + dp[i-1][j]。但前提是当前位置不是马的控制点。如果是控制点，保持初始值 0 即可。

初始化 dp 数组将 [1][1] 置为 1。对于马的控制点，借助方向向量将对应位置标记为 1（障碍），其余为 0。填表时判断障碍标记，若是障碍则跳过。

数据类型 方案数可能很大，需使用 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;
}