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

迷雾森林

题目要求在只能向上或向右走的情况下，计算从起点到终点的方案数，且不能经过有树的格子。

思路分析

1. 状态表示：dp[i][j] 表示从 [m, 1] 走到 [i, j] 的方案数。
2. 状态转移：由于只能向上或向右，到达 [i, j] 的前一步可能是 [i, j-1]（左边）或 [i+1, j]（下边）。注意这里方向与常规不同，因为是从下往上推。
   • 如果是空地：dp[i][j] = dp[i][j-1] + dp[i+1][j]
   • 如果有树：dp[i][j] = 0
3. 初始化：全局数组默认为 0。起点 dp[m][1] 设为 1。
4. 填表顺序：从下往上，每行从左往右。
5. 注意事项：答案需要对 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 个点，求到达 [n, m] 的方案数。

思路分析

1. 坐标偏移：为了避免处理负数下标，将输入的所有坐标统一加 1，相当于棋盘整体平移。
2. 状态表示：dp[i][j] 表示从 [1, 1] 走到 [i, j] 的方案数。
3. 状态转移：只能向下或向右。dp[i][j] = dp[i][j-1] + dp[i-1][j]。
4. 障碍处理：马的控制点标记为不可达（值为 1），其他点为 0。遇到障碍跳过该格子的计算。
5. 数据类型：方案数可能很大，需用 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];

// 马的 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;
    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;
}