深入理解记忆化搜索与拓扑排序的完美结合

核心逻辑与数学原理

对于许多复杂或隐蔽的状态空间，状态之间的依赖关系并不像线性循环那样直观。如果强行编写嵌套循环，极易因难以确定计算顺序而导致使用未固化的状态。

记忆化搜索（Memoization）与拓扑排序（Topological Sort）在哲学上是完全等价的：

1. 拓扑序的本质：若状态 $A$ 的计算依赖于状态 $B$，则在状态图（DAG）中必有一条有向边 $B \to A$。拓扑排序的目的是建立一个全序序列，使得所有边的起点都排在终点之前。
2. 递归形式的拓扑排序（DFS）：记忆化搜索通过动态规划的逆向视角（从目标状态出发，递归询问前驱状态），利用深度优先搜索（DFS）的系统栈隐式完成状态图的拓扑排序。当一个状态的所有后继/前驱状态都访问完毕、即将弹栈时，该状态的全局最优解就已经固化。
3. 消除冗余的核心算子：记忆化搜索通过引入一个与状态空间完全同构的记忆化数组 f（通常初始化为未访问标记，如 -1）。在递归分支中，一旦发现 f[state] 已经被计算过，则立即 $O(1)$ 返回。这在几何上相当于直接剪掉了 DAG 中所有重复访问的子图，将搜索的指数级复杂度硬性拽回图的阶数与边数之和：$O(|V| + |E|)$。

状态设计与算法推导

以经典图论模型“滑雪”（DAG 最长路）为例，推导记忆化搜索的执行过程：

1. 状态设计

设状态 $f[i][j]$ 表示从网格坐标 $(i, j)$ 出发所能滑行的最大区域长度（即以该格点为起点的最长路径边数 $+ 1$）。

2. 转移方程与递归形式

由于只能向地势低的方向滑行，定义 $(nx, ny)$ 为 $(i, j)$ 的四周邻居且满足 $h[nx][ny] < h[i][j]$。转移方程表现为典型的后继最大值松弛：

$$f[i][j] = 1 + \max_{(nx, ny) \in \text{valid\_neighbors}(i, j)} \{ f[nx][ny] \}$$

若四周没有比当前点更低的地势，则该格点为 DAG 的入度为 0 的源点（逆向看作终点）， $f[i][j] = 1$。

3. 记忆化逻辑

定义搜索函数 int dfs(int x, int y)：

• 命中缓存：若 f[x][y] != 0（假设初始化为 0），说明该节点在之前的拓扑遍历中已被固化，直接返回 f[x][y]。
• 未命中计算：遍历四个方向，条件成立则递归调用 dfs(nx, ny)，用返回值更新当前节点。
• 回溯固化：所有分支遍历结束，将最终计算结果写入 f[x][y] 并返回。

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

以下为基于记忆化搜索的区域最长下降路径实现，严格通过 Linux g++ -O2 编译规范。

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

using namespace std;

const int MAXN = 105;
int h[MAXN][MAXN];
int f[MAXN][MAXN]; // 记忆化数组，0 表示未访问过
int n, m;

// 向量方向数组
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dfs(int x, int y) {
    // 致命踩坑点：若已经计算过，必须直接返回，否则记忆化失效退化为纯暴力搜索
    if (f[x][y] != 0) {
        return f[x][y];
    }

    f[x][y] = 1; // 初始化：自身至少算一个长度

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 边界检查与严格下滑条件
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
            if (h[nx][ny] < h[x][y]) {
                f[x][y] = max(f[x][y], dfs(nx, ny) + 1); // 隐式拓扑序转移
            }
        }
    }

    return f[x][y]; // 此时该节点在 DAG 中的最长路已完全固化
}

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

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> h[i][j];
            f[i][j] = 0; // 0 初始化表示所有状态未求值
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            ans = max(ans, dfs(i, j)); // 多源 DFS 寻找全局最长路
        }
    }

    cout << ans << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 记忆化数组未赋予正确的“未访问”标记值

• 现象：合法的 DP 状态取值可能包含 0（例如方案数为 0，或最大收益为 0）。如果将记忆化数组初始化为 0，并在代码中写 if (f[state] != 0) return f[state];，程序会误认为那些真正的“合法零状态”是没有被计算过的，从而引发海量的重复搜索，导致 TLE（时间超限）。
• 规避手段：若状态值可能为 0，记忆化数组必须初始化为 -1。在搜索开头统一使用 if (f[state] != -1) return f[state]; 进行判重。

2. 状态转移图中存在隐蔽环路导致系统栈溢出

• 现象：记忆化搜索依赖于状态空间是 DAG。如果状态设计不当，导致转移存在环路（例如状态 $A$ 依赖 $B$，$B$ 又依赖 $A$），无条件递归会进入死循环，瞬间报出 Runtime Error (Segmentation Fault)，即考场上致命的爆栈。
• 规避手段：必须严格检查转移条件是否具有单调性（如高度递减、时间递增、规模缩减）。若无单调性，必须增设 vis[state] 数组打上“正在访问”标记。一旦在递归分支中发现下一个状态的 vis 已经是 true，说明图中有环，必须立刻剪枝或重新设计状态。

经典 NOIP/洛谷 真题

1. 洛谷 P1434 [SHOI2002] 滑雪

• 题意描述：给定一个二维网格，每个格点有一个高度。一个人可以向上、下、左、右四个方向滑行，条件是下一格的高度必须严格小于当前格。求最长滑行轨道的长度。
• 问题本质与解题思路：基于网格图高度单调性的隐式拓扑序最长路问题。
• 状态设计：$f[i][j]$ 表示从 $(i,j)$ 开始滑行的最大长度。
• 核心思路：高度的严格单调递减保证了状态空间绝对不存在环路（无后效性）。直接对每个点进行 DFS，利用四方向向量尝试转移。若邻居高度低，则由 dfs(nx, ny) + 1 向当前状态贡献。由于使用了记忆化，每个格点仅会被完整计算一次。

2. 洛谷 P1464 Function

• 题意描述：给定一个三阶递推函数 $w(a, b, c)$ 的复杂分支定义。当 $a, b, c$ 满足各种大小关系时，函数会递归调用自身（例如 $w(a-1, b, c) + w(a-1, b-1, c) - w(a-1, b, c-1)$）。要求输入多组 $a, b, c$，快速输出函数值。
• 问题本质与解题思路：高维标量函数的重复子问题去重。普通的暴力递归由于分支繁多，时间复杂度呈指数级 $O(3^N)$ 爆炸。
• 状态设计：由于当 $a,b,c \le 0$ 或 $>20$ 时均有常数边界，实际有效的状态空间仅为 $25 \times 25 \times 25$ 的三维网格。设 $f[a][b][c]$ 存储对应计算值。
• 核心思路：先处理 $a,b,c$ 的边界特判（小于等于 0 返回 1，大于 20 转化为 20）。对于有效范围内的点，在递归计算前直接查询 f[a][b][c] 是否已有值。若有，直接截断返回。通过记忆化，将指数级暴搜强行压制为 $O(20^3)$ 的常数级查表。