动态规划中的顺推与逆推机制详解

核心逻辑与数学原理

在确定了状态空间与 DAG 拓扑序后，实现状态转移有两种底层截然相反的动态规划驱动机制：顺推（人人为我，Pull 型）与逆推（我为人人，Push 型）。两者在数学本质上是对 DAG 边集的不同遍历视角。

顺推（人人为我 / Pull）：
- 核心数学形式：$f[i] = \text{opt}_{j \in prev(i)} \{ f[j] + w(j, i) \}$
- 逻辑视角：当前状态 $i$ 作为接受者。为了计算 $f[i]$，主动检索并拉取（Pull）所有能够到达 $i$ 的前驱状态 $j$ 的已知信息。
- 适用场景：前驱状态的边界极其明确、规则固定的问题。
逆推（我为人人 / Push）：
- 核心数学形式：对于当前已固化的状态 $j$，更新它所有能到达的后继状态 $i$：$f[i] = \text{opt}(f[i], f[j] + w(j, i))$
- 逻辑视角：当前状态 $j$ 作为贡献者。当 $f[j]$ 的值确定后，主动将其价值推送（Push）并贡献给所有以 $j$ 为起点的后继状态 $i$。
- 适用场景：当前状态所能带来的“后续影响”很容易枚举，但若反过来找“谁能转移到当前状态”却极其困难或复杂的场景（如刷表法、稀疏转移、博弈论状态变换）。

状态设计与算法推导

以经典的“数字三角形 / 变长跳跃路径最大收益”模型来拆解两种推导逻辑。假设在序列中，从位置 $i$ 可以跳跃到 $i+1$ 或 $i+2$，代价为 $w(i, \text{target})$。

1. 顺推（人人为我）设计

方程构建：要确定 $f[i]$，必须去看谁能一步跳到 $i$。显然是 $i-1$ 和 $i-2$。

$$f[i] = \max(f[i-1] + w(i-1, i), f[i-2] + w(i-2, i))$$

执行边界：必须保证循环到 $i$ 时，$f[i-1]$ 和 $f[i-2]$ 已经是死数据。

2. 逆推（我为人人）设计

方程构建：当前拿着已经算好的 $f[i]$，去刷它能一步到达的地方：

$$f[i+1] = \max(f[i+1], f[i] + w(i, i+1))$$

$$f[i+2] = \max(f[i+2], f[i] + w(i, i+2))$$

执行边界：开始时，除了起点 $f[1]$ 外，其余后继状态必须初始化为负无穷（-INF），由当前点向后源源不断地输送有效能量。

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

以下源码在同一拓扑图（一维多步非固定跳跃模型）下，分别给出“顺推”与“逆推”的完整实现，对比其底层逻辑。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 10005;
const int INF = 0x3f3f3f3f;

int w[MAXN]; // 节点自身的价值
int f_pull[MAXN]; // 顺推数组
int f_push[MAXN]; // 逆推数组

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

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }

    // ==================== 1. 顺推写法 (人人为我) ====================
    // 必须严密控制前驱合法性
    f_pull[1] = w[1];
    f_pull[2] = w[1] + w[2]; 
    for (int i = 3; i <= n; ++i) {
        // 主动拉取前驱 i-1 和 i-2 的状态信息
        f_pull[i] = max(f_pull[i - 1], f_pull[i - 2]) + w[i];
    }

    // ==================== 2. 逆推写法 (我为人人 / 刷表法) ====================
    // 必须将未达状态初始化为极值，防止从不合法状态向后贡献
    for (int i = 1; i <= n; ++i) f_push[i] = -INF;

f_push[1] = w[1]; // 唯一合法的起点
    for (int i = 1; i < n; ++i) {
        if (f_push[i] == -INF) continue; // 致命踩坑点：跳过不可达的虚无状态

        // 用当前确定的状态，主动去刷新后继状态的值
        if (i + 1 <= n) f_push[i + 1] = max(f_push[i + 1], f_push[i] + w[i + 1]);
        if (i + 2 <= n) f_push[i + 2] = max(f_push[i + 2], f_push[i] + w[i + 2]);
    }

    cout << f_pull[n] << " " << f_push[n] << "\n";
    return 0;
}

NOIP 实战避坑指南

1. 逆推（我为人人）未剔除“不合法/不可达”前驱状态

现象：在逆推中，通常把除了起点外的所有 $f$ 数组项初始化为 -INF 或 INF。如果循环时没有写 if (f[i] == -INF) continue;，这个 -INF 就会加上某个边权 $w$，导致变成一个很大的负数，然后去更新后继状态 $f[i+1]$（若 $f[i+1]$ 也是 -INF，两者的 $max$ 会接受这个脏数据）。这在数学上等价于“允许从一个根本无法到达的幽灵状态跳跃到下一个状态”。
规避手段：逆推（刷表法）的循环内部，第一步必须做起点合法性检查。

2. 顺推（人人为我）边界状态越界强行读取

现象：顺推时由于需要回溯 $i-1, i-2$ 甚至更远的项。很多选手习惯一个 for (int i = 1; i <= n; ++i) 写到底，导致 $i=1$ 时读取了 $f[-1]$ 或 $f[0]$ 的随机内存数据，导致转移逻辑彻底崩溃。
规避手段：写顺推前，先把不符合通用方程的特殊低阶项（如 $i=1, i=2$）单独拉出来显式手工赋值，循环严格从能够完全满足前驱索引的起点（如 $i=3$）开始。

经典 NOIP/洛谷真题

1. 洛谷 P1004 [NOIP2000 提高组] 方格取数

题意描述：在一个 $N \times N$ 的商业网格中，有些格点放有一定数量的整数。两个人同时从左上角出发走到右下角，每次只能向下或向右走。走过的格点上的数会被取走变为 0。求两人取得的数之和的最大值。
问题本质与解题思路：多源双线并发状态步数同步顺推 DP。
状态设计：如果各自独立走，第二个人会受到第一个人决策的后效性污染（路径取走数变0）。因此必须让两个人同时同步走。设状态 $f[k][i][j]$ 表示两人同时走了 $k$ 步，第一个人在第 $i$ 行，第二个人在第 $j$ 行时的最大收益。
核心思路：使用顺推。当前状态 $(k, i, j)$ 只能由两人上一格分别“右右、右下、下右、下下”四个方向拉取数据。由于步数 $k$ 固定，各自的列坐标可由 $k-i$ 和 $k-j$ 完美算得。若 $i == j$，说明两人在几何上踩到了同一个格点，数据只能加一次。通过拉取上一时刻的 4 个前驱取最大值完成顺推。

2. 洛谷 P1063 [NOIP2006 提高组] 能量项链

题意描述：环形链上有 $N$ 颗能量珠，每颗珠子有头标记和尾标记，相邻珠子可以聚合，聚合时释放能量为 $head \times tail \times next\_tail$。聚合后两颗珠子变成一颗。求释放的总能量最大值。
问题本质与解题思路：区间动态规划。从大区间向小区间逆向剖析，但在实际计算中采用从小区间向大区间层层叠加的顺推逻辑。
状态设计：首先破环成链倍长序列。设 $f[l][r]$ 表示从第 $l$ 颗珠子合并到第 $r$ 颗珠子所能释放的最大能量。
核心思路：外层循环枚举区间长度 $len$ 从 2 到 $N$，中层循环枚举区间左端点 $l$。当前区间 $f[l][r]$ 依赖于它的子区间。内层枚举决策切分点 $k$（$l \le k < r$），通过拉取子区间状态进行状态转移：$f[l][r] = \max_{k} \{ f[l][k] + f[k+1][r] + head[l] \times tail[k] \times tail[r] \}$。这是典型的人人为我（Pull）架构，依赖于更短的子区间已经完全固化。