State Space Design and Geometric Mapping in Dynamic Programming

Core Logic and Mathematical Principles

The state space is the collection of all possible states, representing a complete discretization and abstraction of the phased characteristics of real-world problems. The essence of dynamic programming is to find the longest or shortest path on a directed acyclic graph (DAG) formed by the state space.

When considering states as grid points in a high-dimensional space, the transition equations represent the geometric vector mappings between these grid points:

Dimensions and Axes: The dimensions of the state array correspond to the number of control variables. For example, $f[i][j]$ represents a two-dimensional state space, where the horizontal and vertical axes represent "the first $i$ phases" and "the constraint $j$" respectively.
Geometric Topology of the DAG: Any valid state transition equation geometrically manifests as a directed edge moving from lower-dimensional/lower-index grid points to higher-dimensional/higher-index grid points. Due to the no-backtracking constraint, these directed edges never form cycles in space.
Spatial Step Size and Locality: The index changes in the transition equations (such as $i-1, j-v$) define the step size of movement within the state space grid. Efficient DP algorithms often exhibit good spatial locality, which is the geometric basis for rolling arrays to compress spatial dimensions.

State Design and Algorithm Derivation

Under the geometric mapping of the DAG, we need to translate complex boundaries and constraints into control at grid points on the axes. Taking the "path counting on a grid with obstacles" extended model as an example:

1. State Space Design

Let state $f[i][j]$ represent the number of valid path plans from the starting point $(1, 1)$ to the coordinate $(i, j)$ along the grid lines. If the current coordinate $(i, j)$ is an obstacle, then that grid point is invalid in the state space, and its value is forcibly set to zero.

2. Transition Equations and Geometric Mapping

Since each step can only move right or down, this means that the predecessor grid points of the target grid point $(i, j)$ can only be the left $(i, j-1)$ and the top $(i-1, j)$. This geometrically manifests as two directed edges converging at $(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. Boundaries and Topological Order

Boundary: The starting point $f[1][1] = 1$.
Topological Order: Scanning in a double-increasing order of row and column coordinates (from left to right, top to bottom). This order ensures that when computing $f[i][j]$, the geometric states to the left and above have already been fully computed and solidified.

C++ Standard Source Code (NOIP Style)

Below is the C++ source code for counting paths in a two-dimensional space based on DAG geometric mapping, including obstacle handling, strictly compatible with NOIP Linux (g++ -O2) environment.

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1005;
const int MOD = 1000000007; // Prevent overflow, modulo as required by the problem

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 represents empty space, 0 represents obstacle
        }
    }

    // Boundary condition initialization
    if (grid[1][1] == 1) {
        f[1][1] = 1;
    }

    // Strictly calculate the state space in topological order (double-increasing row and column loops)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) continue; // Skip the starting point

            if (grid[i][j] == 0) {
                f[i][j] = 0; // Important: The number of paths at obstacle points must be forcibly set to zero, do not overlook
                continue;
            }

            // State transition: relies on the geometric states above and to the left
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % MOD;
        }
    }

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

    return 0;
}

NOIP Practical Pitfall Guide

1. Ignoring Explicit Zeroing of Obstacle States

Phenomenon: When optimizing space using rolling arrays or iterating directly on the original array, if a state is updated to unreachable (e.g., encountering an obstacle or illegal state), forgetting to explicitly set it to 0 leads to old data from the previous stage mixing into subsequent transitions, resulting in inflated calculation results.
Avoidance Strategy: The branching structure must include a complete else { f[i][j] = 0; } logic to ensure that the weights of illegal grid points in the state space are zero.

2. Topological Order of State Space and Reversed Loop Order

Phenomenon: When designing transitions with spatial dependencies, the increment/decrement direction of loop variables is opposite to the direction of the DAG edges. For example, using the updated state from the same layer instead of the previous layer due to enumerating loops from small to large leads to using updated states from the same layer.
Avoidance Strategy: After writing the equation, visually check the state indices on the right side of the equal sign (like $i-1$ or $j-v$). If it depends on indices smaller than the current one and uses the same layer array, the loop must be in reverse order (from large to small); if it depends on indices smaller than the current one and uses different layers, the loop is in forward order.

Classic NOIP/Luogu Problems

1. Luogu P1002 [NOIP2002 Popular Group] River Crossing Soldier

Problem Description: There are points A and B on the chessboard surface. A soldier needs to move from point A to point B. There is also an opponent's knight on the chessboard, and the point where the knight is located and all points that the knight can jump to in one move are called the control points of the opponent's knight. The soldier can only move down or to the right, and the goal is to find the number of paths from A to B.
Essence and Solution Idea: Two-dimensional grid state space topological traversal with dynamic disabled points. The knight's control points geometrically cut off some vertices of the DAG.
State Design: $f[i][j]$ represents the number of paths for the soldier to reach coordinate $(i, j)$.
Core Idea: First preprocess the knight's control points and mark them. Then perform a double-loop increment to recursively compute; if the current position is a knight's control point, set $f[i][j] = 0$, otherwise set $f[i][j] = f[i-1][j] + f[i][j-1]$. Special attention should be paid to boundary cases, as $i-1$ and $j-1$ are involved, the entire coordinate can be shifted by 2 units to prevent out-of-bounds.

2. Luogu P1508 Likecloud - Eating Candy

Problem Description: In an $M \times N$ matrix, each grid point has a certain number of candies. Li Cloud starts from the middle of the last row of the matrix and can only move one step in the left-up, up, or right-up directions, aiming to find the maximum number of candies that can be collected when reaching the first row.
Essence and Solution Idea: Directed multi-source longest path problem on a grid, geometrically from bottom to top topological transitions.
State Design: $f[i][j]$ represents the maximum number of candies that can be obtained when reaching row $i$, column $j$.
Core Idea: The starting point is fixed at the midpoint of the last row. Since the movement is from bottom to top, the transition equation should consider the predecessor states in reverse: $f[i][j] = \max(f[i+1][j-1], f[i+1][j], f[i+1][j+1]) + A[i][j]$. When handling boundaries, the columns that exceed the matrix boundaries (such as $j < 1$ or $j > N$) should be initialized to negative infinity (-INF) to prevent transitions from non-existent geometric paths.