路径类动态规划入门：最小路径和、迷雾森林与过河卒详解

迷雾森林

题目描述

思路解析

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

2. 状态转移方程 规定只能向上或向右走。假设当前格子为 [i, j]，上一个格子可能是 [i, j-1]（左）或者 [i+1, j]（下）。 但要注意，本题有障碍物（树），遇到树不能走。只有空地才能进行状态转移。

   if (a[i][j] == 0) dp[i][j] = dp[i][j - 1] + dp[i + 1][j];
   else dp[i][j] = 0;
   

   此外，答案需要对 2333 取模。

3. 初始化

   • 全局数组默认初始化为 0，无需额外 memset。
   • 起点 [m, 1] 的方案数为 1，即 dp[m][1] = 1。

4. 填表顺序 由于依赖左边和下边，需要从下往上填每一行，每行内从左往右。

5. 输出结果 dp[1][n]

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

过河卒

题目描述

思路解析

1. 坐标偏移 题目强制从 [0, 0] 开始，为了避开数组下标 0 带来的越界判断麻烦，我们将棋盘整体向下和向右平移一格，统一从 [1, 1] 开始填表。输入的马坐标和终点坐标也相应加 1。

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

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

4. 初始化

   • dp[1][1] = 1。
   • 使用方向向量标记马的 9 个控制点（包括马自身所在点），将这些点在辅助数组 a 中置为 1。

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

6. 注意事项

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