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

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

矩阵的最小路径和

题目解析

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

状态转移方程 我们根据最后一步来推导。要到达最后一个格子 dp[n][m]，只能从上方 dp[n - 1][m] 或者左方 dp[n][m - 1] 走过来。因此，dp[n][m] 的值就是这两个位置较小值加上当前格子的权值 a[n][m]。公式如下： dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]

初始化 填表时需要访问左边和上边的格子，所以边界情况需要特殊处理。第一行和第一列在计算时会访问到第 0 行和第 0 列，但这两行无意义，所以我们将第 0 行和第 0 列初始化为无穷大。由于状态转移取最小值，这样永远不会选到无效区域。 此外，需要将 dp[1][1] 初始化为 a[1][1]，因为起点的代价就是它本身。注意在填表循环中跳过 (1, 1) 格子，避免重复计算导致错误。

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

输出结果 dp[n][m]

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

    // 初始化
    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)（下边）。格子 (i, j) 的方案数等于这两个来源的方案数之和。

需要注意的是，本题只能走空地。如果遇到树（障碍），则不能通过。只有空地才用状态转移方程填表，森林格子保持默认初始值 0。 状态转移方程为： 若 a[i][j] == 0（空地）: dp[i][j] = dp[i][j - 1] + dp[i + 1][j] 若 a[i][j] == 1（障碍）: dp[i][j] = 0

初始化

• 填表时会访问左边和下边格子，dp 数组全局开辟默认为 0，无需额外 memset。
• 因为是求解方案数，后续格子方案数是从第一个格子累加而来，所以将 dp[m][1] 初始化为 1。注意填表时不重新覆盖这个起始点。

填表顺序 根据状态转移方程，需要访问左边和下边格子，所以填表顺序是从下往上填每一行，每行内从左往右。

输出结果 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() {
    // 处理输入
    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++) {
            // [m][1] 格子以及初始化，无需再次填
            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] 表示从 (1, 1) 格子走到 (i, j) 格子时，一共有多少种方案。

状态转移方程 题目规定卒只能向下或向右走。状态转移方程为： dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

需要注意，只有走到不是马的控制点时才能用状态转移方程填表。如果走到马的控制点，不做任何操作，让它保持初始值 0 即可。

初始化

• dp 数组将 dp[1][1] 置为 1，因为方案数需要从起点开始累加。
• a 数组用于标记马的控制点。思路是将马的 9 个控制点全部置为 1，其余点保持 0。后面填表时判断 a[i][j] 是否为 0，为 0 可填表，不为 0 则跳过。

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

输出结果 dp[n][m]

注意事项

1. 马所在的点也是马的控制点。
2. dp 数组要用 long long 类型，因为方案数可能达到阶乘级别，普通 int 会溢出。

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