DP 系列（番外）：图上的 DP——DAG 与拓扑序

本讲定位：主系列七讲的番外篇。专题五说过”树是最适合 DP 的结构”，本讲把舞台扩展到一般的有向图：只要图上没有环（即 DAG，有向无环图），DP 照样成立——拓扑序就是填表顺序。最长路、路径计数、约束分级、图上期望，全是同一个框架。这是 CSP-S 的高频题型，也是主系列七讲之外唯一成块的 DP 空白。

前置知识：专题一（记忆化搜索、“依赖决定顺序”——本讲是它的直系续篇）；图的邻接表存储与 BFS 队列。

标注 ⭐ 的小节为进阶内容。

1. 从”滑雪”说起：你早就做过图上 DP

回忆专题一的”滑雪”（P1434）：网格里每个格子有高度，只能往严格更低的相邻格滑，求最长滑道。当时我们写的是记忆化搜索：

$$ f[u] = 1 + \max_{v \text{ 是 } u \text{ 的更低邻居}} f[v] $$

现在换个眼光看：把每个格子当作结点、“可以滑过去”当作有向边，这就是一张图，而 $f$ 就是图上的 DP。它为什么能做？因为”往严格更低处滑”保证了沿着边走永远不可能绕回来——图上没有环。

无环是图上 DP 的生死线。 DP 的根基是”转移用到谁，谁就必须先算完”（专题一的原话）。如果图上有环 $a \to b \to c \to a$，那么 $f[a]$ 等 $f[c]$、$f[c]$ 等 $f[b]$、$f[b]$ 等 $f[a]$——互相等待，谁也算不了。所以：

有向无环图（DAG）上，求最长/最短路径、路径计数、按依赖递推——全部可以 DP。 有环的图求最短路，要换图论的专门算法（Dijkstra 等，图论专题的内容）；有环求最长路则没有高效算法，除非先把环消掉（题单第 5、6 题会碰到）。

序列是一条链，树是没有环的分叉——你会发现主系列的一切 DP，本来就都发生在特殊的 DAG 上。本讲只是把这层窗户纸捅破。

2. 拓扑排序：把图”拉直”

序列上我们按下标从小到大填表，树上按 DFS 后序填表，DAG 上按什么顺序？——拓扑序：把所有结点排成一排，使每条边都从前面指向后面。沿拓扑序从左到右填表，任何点被算到时，它依赖的点必然已算完。

求拓扑序的标准方法是 Kahn 算法：反复摘下”入度为 0”的点（没有任何前置依赖的点），摘掉它的同时削减它指向的点的入度：

queue<int> q;
for (int i = 1; i <= n; i++)
    if (deg[i] == 0) q.push(i);        // 所有入度 0 的点都是起跑线
while (!q.empty()) {
    int u = q.front(); q.pop();        // u 出队时，它依赖的点全部已出队
    // —— 在这里做 u 的 DP 转移 ——
    for (int v : g[u])
        if (--deg[v] == 0) q.push(v);  // v 的最后一个前置处理完，v 才入队
}

一个免费的副产品：出队的点数 $< n$，当且仅当图上有环（环里的点入度永远削不到 0）。这是最常用的判环方法，初赛概念题也考。

图上 DP 有两种写法，和专题一”记忆化搜索 vs 递推”一脉相承：

顺带说透一件事：树形 DP 的”DFS 后序”，本质就是树这张特殊 DAG 的拓扑序——专题五你已经在无意识地做拓扑排序了。