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

迷雾森林

题目描述

题目解析

1. 状态表示 dp[i][j] 表示从 [m, 1] 格子走到 [i, j] 格子时，一共有多少种方案。
2. 状态转移方程 根据最后一步推导状态转移方程，因为题目规定只能向上或向右走，所以假设最后一个格子为 [i, j]，那么上一个格子可能是 [i, j - 1] 或者 [i + 1, j]，那么格子 [i, j] 的方案数就是 [i, j - 1] 格子方案数加上 [i + 1, 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

3. 初始化
   • 因为本题填表时会访问左边格子和下边格子，所以需要将 dp 数组第 0 列和第 0 行格子初始化为 0，因为 dp 数组在全局开辟，所以值默认为 0，不需要手动用 memset 初始化。
   • 因为本题是求解方案数，后续格子方案数就是从第一个格子累加而来，所以将 dp[m][1] 初始化为 1（注意：填表时不填 [m][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() {
    // 处理输入
    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] 格子开始填表。

1. 状态表示 dp[i][j] 表示从 [1, 1] 格子走到 [i, j] 格子时，一共有多少种方案。
2. 状态转移方程 根据最后一步推导状态转移方程，题目规定卒行走的规则只能向下、或者向右，所以状态转移方程： dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 但是需要注意只有走到不是马的控制点时才能用状态转移方程填表，如果走到马的控制点不做任何操作，让它保持初始值 0 即可。
3. 初始化 本题需要对 a、dp 数组分别初始化，dp 数组将 [1][1] 置为 1 即可，因为方案数问题的答案需要从第一个格子开始累加得到。 a 数组的处理思路是将马的 9 个控制点全部置为 1，其余点保持 0，在后面根据状态转移方程填表时需要判断 a 数组对应格子是否为 0，如果为 0 可以填表，不为 0 则直接 continue，不做任何操作。本题对 a 数组初始化我们借助方向向量实现。
4. 填表顺序 从左往右，从上往下
5. 输出结果 dp[n][m]

注意：

1. 马所在的点也是马的控制点。
2. dp 数组要用 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;
}