动态规划中的状态空间设计与几何映射

核心逻辑与数学原理

状态空间（State Space）是所有可能状态的集合，是对现实问题阶段性特征的完全离散化抽象。动态规划的实质，就是在状态空间构成的有向无环图（DAG）上寻找最长路或最短路。

若将状态视为高维空间中的格点，转移方程则是这些格点之间的几何向量映射：

1. 维数与坐标轴：状态数组的维度对应了控制变量的个数。例如，$f[i][j]$ 是二维状态空间，横纵坐标轴分别代表“前 $i$ 个阶段”和“限制条件 $j$”。
2. DAG 的几何拓扑：任何一个合法的状态转移方程，在几何上都表现为从低维/低标号格点向高维/高标号格点的单向有向边。由于无后效性约束，这些有向边在空间中绝不形成环路。
3. 空间步长与局部性：转移方程中的标号变化（如 $i-1, j-v$）定义了在状态空间网格中的移动步长。高效的 DP 算法往往具有良好的空间局部性（Spatial Locality），这也是滚动数组能够压缩空间维度的几何依据。

状态设计与算法推导

在 DAG 的几何映射下，我们需要将复杂边界和限制条件转化为坐标轴上的格点控制。以“带障碍物的棋盘路径统计”扩展模型为例：

1. 状态空间设计

设状态 $f[i][j]$ 表示从起点 $(1, 1)$ 沿网格线移动到坐标 $(i, j)$ 的合法路径方案数。若当前坐标 $(i, j)$ 为障碍物，则该格点在状态空间中不合法，值强行归零。

2. 转移方程与几何映射

由于每一步只能向右或向下移动，这意味着目标格点 $(i, j)$ 的前驱格点只能是左侧的 $(i, j-1)$ 和上方的 $(i-1, j)$。这在几何上表现为两条汇聚到 $(i, j)$ 的有向边：

$$f[i][j] = \begin{cases} 0 & \text{if } \text{grid}[i][j] \text{ is obstacle} \\ f[i-1][j] + f[i][j-1] & \text{otherwise} \end{cases}$$

3. 边界与拓扑序

• 边界：起点 $f[1][1] = 1$。
• 拓扑序：按照行列坐标双重递增的顺序（从左到右，从上到下）进行扫描。这种序保证了在计算 $f[i][j]$ 时，其几何左方和上方的状态值已经完全计算完毕并固化。

C++ 标准源码（NOIP风格）

以下为基于 DAG 几何映射的二维路径计数源码，包含障碍物处理，严格兼容 NOIP Linux (g++ -O2) 环境。

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1005;
const int MOD = 1000000007; // 防爆 int，按题目要求取模

int grid[MAXN][MAXN];
int f[MAXN][MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j]; // 1 表示空地，0 表示障碍
        }
    }

    // 边界条件初始化
    if (grid[1][1] == 1) {
        f[1][1] = 1;
    }

    // 严格按拓扑序（行列双重循环递增）计算状态空间
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) continue; // 跳过起点

            if (grid[i][j] == 0) {
                f[i][j] = 0; // 踩坑点：障碍物处方案数必须强制清零，切勿遗漏
                continue;
            }

            // 状态转移：依赖于几何上方和左方的格点
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % MOD;
        }
    }

    cout << f[n][m] << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 忽略障碍物状态的显式清零

• 现象：在使用滚动数组优化空间或直接在原数组上迭代时，若某阶段状态更新为不可达（如遇到障碍或不合法状态），忘记显式将其赋值为 0。导致上一阶段遗留的旧数据直接混入后续转移，引发计算结果偏大。
• 规避手段：在分支结构中，必须包含完善的 else { f[i][j] = 0; } 逻辑，确保不合法格点在状态空间中的权值为零。

2. 状态空间拓扑序与循环顺序逆反

• 现象：在设计具有空间依赖的转移时，循环变量的递增/递减方向与 DAG 的边向相反。例如，本该使用未更新的上一层状态，却因为从小到大枚举循环，导致使用了同层已被更新的状态。
• 规避手段：写完方程后，肉眼检查等号右边的状态下标（如 $i-1$ 或 $j-v$）。若依赖比当前小的下标，且使用的是同一层数组，循环必须倒序（从大到小）；若依赖比当前小的下标且使用不同的层，循环正序。

经典 NOIP/洛谷 真题

1. 洛谷 P1002 [NOIP2002 普及组] 过河卒

• 题意描述：棋盘表面上有 A 点和 B 点。有一个卒要从 A 点走到 B 点。棋盘上还有一个对方的马，马所在的点以及所有马一步能跳到的点都称为对方马的控制点。卒只能向下或向右走，求卒从 A 点走到 B 点的路径条数。
• 问题本质与解题思路：带有动态禁用点的二维网格状态空间拓扑遍历。马的控制点在几何上直接切断了 DAG 的部分顶点。
• 状态设计：$f[i][j]$ 表示卒走到坐标 $(i, j)$ 的路径数。
• 核心思路：首先预处理出马的控制点并打上标记。接着进行二维双重循环递增递推，如果当前位置是马的控制点，则令 $f[i][j] = 0$，否则 $f[i][j] = f[i-1][j] + f[i][j-1]$。需要特别注意边界情况，由于涉及 $i-1$ 和 $j-1$，可将整体坐标平移 2 个单位防止越界。

2. 洛谷 P1508 Likecloud-吃糖果

• 题意描述：在一个 $M \times N$ 的矩阵中，每个格点都有一定数量的糖果。李克劳德从矩阵最后一行的正中间出发，每次只能往左上、正上、右上三个方向走一步，求走到第一行所能收集到的最大糖果数。
• 问题本质与解题思路：网格图上的有向多源最长路问题，几何上是从底向上的拓扑转移。
• 状态设计：$f[i][j]$ 表示走到第 $i$ 行第 $j$ 列时能获得的最大糖果数。
• 核心思路：起点固定在最后一行的中点。由于是从下往上走，转移方程应该逆向考虑其前驱状态：$f[i][j] = \max(f[i+1][j-1], f[i+1][j], f[i+1][j+1]) + A[i][j]$。边界处理时，超出矩阵边界的列（如 $j < 1$ 或 $j > N$）对应的状态值应初始化为负无穷（-INF），以防止从不存在的几何路径转移过来。