20261007 190739 动态规划系统课程6

动态规划系统课程 · 第六讲：DAG DP ¶

这一讲我们把前面学过的 DP 再提升一个层次。

前面：

线性 DP：dp[i]
背包 DP：dp[j]
区间 DP：dp[l][r]
树形 DP：dp[u][...]

今天学习：

DAG 上的动态规划 ¶

DAG 是：

Directed Acyclic Graph，有向无环图。

这一讲真正要掌握的不是某一道题，而是一个非常重要的思想：

只要状态之间形成无环的依赖关系，就可以按照依赖顺序进行动态规划。

一、什么是有向图？¶

例如：

1 → 2

表示：

1 可以到达 2

如果：

1 → 2
2 → 3

那么：

1 → 2 → 3

二、什么是环？¶

如果：

1 → 2
2 → 3
3 → 1

就形成：

1 → 2
↑     ↓
└── 3

这叫：

有向环 ¶

而如果一个有向图：

不存在任何有向环

那么叫：

DAG ¶

三、为什么 DAG 可以做 DP？¶

这是本讲最重要的问题。

假设：

1 → 2 → 4
 \       ↑
  → 3 ───┘

如果我们定义：

$$
dp[u]
$$

表示：

从起点到节点 u 的最优答案。

那么计算：

dp[4]

之前必须先知道：

dp[2]
dp[3]

而计算：

dp[2]

之前又必须知道：

dp[1]

于是出现：

dp[1]
 ↓
dp[2]
 ↓
dp[4]

dp[1]
 ↓
dp[3]
 ↓
dp[4]

这就是一个依赖关系。

只要按照：

先计算依赖，再计算当前状态

就可以完成 DP。

四、拓扑排序 ¶

DAG 有一个非常重要的性质：

一定存在拓扑序。

所谓拓扑序，就是把所有节点排列成一个序列，使得：

如果 u → v，那么 u 一定出现在 v 前面。

例如：

一个拓扑序：

1 2 3 4

也可能是：

1 3 2 4

只要满足所有边的方向即可。

五、DAG DP 的基本套路 ¶

最典型的形式：

dp[start] = 初始值;

按照拓扑序：

    for (u 的所有出边 u -> v) {

        dp[v] = 根据 dp[u] 更新;
    }

例如求最长路：

$$
dp[v]
=
\max(dp[v],dp[u]+w)
$$

六、第一道经典题：DAG 最长路 ¶

我们来看最基础的问题。

题目 ¶

给定一个 DAG，每条边有一个权值。

求：

从节点 1 出发，到所有节点的最长路径长度。

例如：

       2
   1 ───→ 2
   │       \
  3│        \4
   ↓         ↓
   3 ──5──→ 4

边：

1 → 2，权值 2
1 → 3，权值 3
2 → 4，权值 4
3 → 4，权值 5

那么：

1 → 2 → 4

长度：

$$
2+4=6
$$

而：

1 → 3 → 4

长度：

$$
3+5=8
$$

所以到 4 的最长路是：

$$
8
$$

七、状态定义 ¶

定义：

$$
dp[v]
$$

表示：

从起点 1 到节点 v 的最长路径长度。

初始：

$$
dp[1]=0
$$

其他节点：

dp[v] = -∞

因为一开始还没有到达它们。

八、状态转移 ¶

如果存在边：

$$
u\rightarrow v
$$

权值为：

$$
w
$$

那么：

如果能够到达 u，就可以通过这条边到达 v。

所以：

$$
dp[v]
=
\max(dp[v],dp[u]+w)
$$

这就是 DAG 最长路的核心转移。

九、为什么必须按照拓扑序？¶

假设：

u → v

那么：

dp[v]

依赖：

dp[u]

所以：

u
↓
v

必须先处理 u。

拓扑排序刚好保证：

所有前驱节点都在当前节点之前。

十、完整 C++ 代码 ¶

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    long long w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> graph(n + 1);

    vector<int> indegree(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;

        cin >> u >> v >> w;

        graph[u].push_back({v, w});

        indegree[v]++;
    }

    // 拓扑排序
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo;

    while (!q.empty()) {

        int u = q.front();
        q.pop();

        topo.push_back(u);

        for (auto e : graph[u]) {

            indegree[e.to]--;

            if (indegree[e.to] == 0) {
                q.push(e.to);
            }
        }
    }

    // DP
    const long long NEG_INF = -(1LL << 60);

    vector<long long> dp(
        n + 1,
        NEG_INF
    );

    dp[1] = 0;

    for (int u : topo) {

        if (dp[u] == NEG_INF)
            continue;

        for (auto e : graph[u]) {

            int v = e.to;

            dp[v] = max(
                dp[v],
                dp[u] + e.w
            );
        }
    }

    for (int i = 1; i <= n; i++) {

        if (dp[i] == NEG_INF)
            cout << "INF";
        else
            cout << dp[i];

        cout << '\n';
    }

    return 0;
}

十一、拓扑排序到底做了什么？¶

这段代码：

while (!q.empty()) {

    int u = q.front();
    q.pop();

    topo.push_back(u);

    for (auto e : graph[u]) {

        indegree[e.to]--;

        if (indegree[e.to] == 0) {
            q.push(e.to);
        }
    }
}

做的是：

不断寻找当前没有前驱的节点。

例如：

开始：

indegree:
1 = 0
2 = 1
3 = 1
4 = 2

所以先处理：

删除 1 的出边以后：

2 = 0
3 = 0

于是：

2、3

进入队列。

最后：

入队。

得到拓扑序：

1 2 3 4

十二、第二道经典题：DAG 路径计数 ¶

刚才求的是：

最长路径。

现在改成：

从起点 1 到终点 n，一共有多少条不同路径？

十三、状态设计 ¶

定义：

$$
dp[v]
$$

表示：

从 1 到 v 的路径数量。

初始：

$$
dp[1]=1
$$

为什么不是：

$$
dp[1]=0
$$

因为：

从 1 到 1 有一条“空路径”。

这是计数 DP 中非常重要的初始化思想。

十四、状态转移 ¶

假设：

u → v

那么从 1 到 u 的每一条路径，都可以通过这条边变成：

1 → ... → u → v

因此：

$$
dp[v]+=dp[u]
$$

这就是 DAG 路径计数。

十五、例子 ¶

      2
    ↗   ↘
1 →       → 4
    ↘   ↗
      3

从 1 到 4：

1 → 2 → 4
1 → 3 → 4

一共：

$$
2
$$

条。

十六、完整 C++ 实现 ¶

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n + 1);

    vector<int> indegree(n + 1, 0);

    for (int i = 0; i < m; i++) {

        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);

        indegree[v]++;
    }

    // 拓扑排序
    queue<int> q;

    for (int i = 1; i <= n; i++) {

        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo;

    while (!q.empty()) {

        int u = q.front();
        q.pop();

        topo.push_back(u);

        for (int v : graph[u]) {

            indegree[v]--;

            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // DP
    vector<long long> dp(n + 1, 0);

    dp[1] = 1;

    for (int u : topo) {

        for (int v : graph[u]) {

            dp[v] += dp[u];

            if (dp[v] >= MOD) {
                dp[v] -= MOD;
            }
        }
    }

    cout << dp[n] << '\n';

    return 0;
}

十七、为什么这里用 `+`？¶

这是一个非常重要的 DP 思维。

如果两个不同的状态都能够转移到 v：

u → v
w → v

那么：

从 u 来的方案
+
从 w 来的方案

都是不同方案。

因此：

$$
dp[v]=dp[v]+dp[u]
$$

也就是：

dp[v] += dp[u];

十八、第三道经典题：DAG 最长路——关键路径 ¶

现在来看一个非常重要的实际模型：

一个项目由多个任务组成，有些任务必须在另一些任务完成后才能开始。

例如：

任务 A
  ↓
任务 B
  ↓
任务 D

或者：

任务 A ─→ B ─→ D
       ↘
         C ─→ D

这本质上就是一个 DAG。

十九、关键路径思想 ¶

假设每条边表示一个任务，边权表示任务耗时。

我们希望：

整个项目最早什么时候可以完成？

实际上就是：

求 DAG 上的最长路径 ¶

因为一个任务链上的所有任务必须依次完成。

如果存在：

A → B → C

耗时：

3 + 5 + 7

那么这条链至少需要：

$$
15
$$

个时间单位。

如果存在另一条链：

A → D → C

需要：

$$
4+8=12
$$

那么整个项目需要：

$$
\max(15,12)=15
$$

二十、DAG DP 的一个重要变化 ¶

到这里可以发现：

DAG DP 本身不是一种固定的“题型”。

它更像是一种：

DP 计算框架 ¶

只要有：

状态
↓
状态之间的有向依赖
↓
不存在环

就可以：

拓扑排序
↓
按照拓扑序 DP

二十一、DAG DP 和树形 DP 的关系 ¶

现在把两个知识点放在一起。

树形 DP ¶

从根到叶子：

1 → 2 → 4
 \→ 3

本质上也是一个 DAG。

DAG DP ¶

1 → 2 → 5
 \→ 3 → 5
  \→ 4 ─┘

只不过：

一个节点可能有多个前驱。

树中通常：

一个节点只有一个父亲。

DAG 更一般。

二十二、树形 DP和DAG DP最大的区别 ¶

树：

        1
      / | \
     2  3  4

每个节点通常只有一个父亲。

所以我们可以：

dfs(u, father)

自然地计算。

而 DAG：

1 → 3
2 → 3

节点 3 有两个前驱。

因此通常需要：

拓扑排序

来保证：

1、2
 ↓
3

在计算 3 时，所有前驱都已经完成。

二十三、DFS 能不能做 DAG DP？¶

当然可以。

这是一个非常值得掌握的问题。

例如求从 u 出发的最长路径：

$$
dp[u]
=
\max_{u\rightarrow v}
(w(u,v)+dp[v])
$$

可以使用记忆化 DFS：

long long dfs(int u) {

    if (vis[u])
        return dp[u];

    vis[u] = true;

    for (auto e : graph[u]) {

        dp[u] = max(
            dp[u],
            e.w + dfs(e.to)
        );
    }

    return dp[u];
}

这就是：

记忆化搜索 + DAG DP ¶

二十四、两种 DAG DP 方法 ¶

因此 DAG DP 通常有两种实现。

方法一：拓扑排序 ¶

拓扑排序
↓
按照拓扑序
↓
DP

特点：

迭代
不需要递归
很适合竞赛

方法二：记忆化 DFS ¶

dfs(u)
↓
dfs(所有后继)
↓
计算 dp[u]

特点：

写法直观
状态转移容易理解
本质仍然是 DP

二十五、两种方法的核心区别 ¶

例如：

拓扑排序：

1
↓
2、3
↓
4

记忆化 DFS：

dfs(1)
 ├── dfs(2)
 │     └── dfs(4)
 │
 └── dfs(3)
       └── dfs(4)

注意：

dfs(4)

第二次不会重新计算，因为：

if (vis[u])
    return dp[u];

这就是“记忆化”。

二十六、一个非常重要的统一理解 ¶

现在我们已经学了：

线性 DP
区间 DP
树形 DP
DAG DP

其实可以统一理解成：

先建立状态之间的依赖关系，再按照依赖顺序计算。

例如线性 DP：

dp[1] → dp[2] → dp[3] → dp[4]

区间 DP：

短区间 → 长区间

树形 DP：

子节点 → 父节点

DAG DP：

前驱节点 → 后继节点

二十七、这是动态规划真正的本质 ¶

我们可以把动态规划理解成：

所以：

DP 并不是“背转移方程”。

真正需要培养的是：

建立状态 → 找依赖 → 确定计算顺序 → 转移 ¶

二十八、到目前为止的完整知识体系 ¶

动态规划
│
├── ① 线性 DP
│   ├── LIS
│   ├── LCS
│   └── 编辑距离
│
├── ② 背包 DP
│   ├── 01 背包
│   ├── 完全背包
│   ├── 多重背包
│   └── 分组背包
│
├── ③ 区间 DP
│   ├── 石子合并
│   ├── 最长回文子序列
│   └── 矩阵链乘法
│
├── ④ 树形 DP
│   ├── 最大独立集
│   ├── 没有上司的舞会
│   └── 树上最大路径
│
└── ⑤ DAG DP
    ├── DAG 最长路
    ├── DAG 路径计数
    └── 关键路径

二十九、本讲必须掌握的三个公式 ¶

DAG 最长路 ¶

$$
\boxed{
dp[v]=\max(dp[v],dp[u]+w)
}
$$

DAG 路径计数 ¶

$$
\boxed{
dp[v]+=dp[u]
}
$$

DAG 最短路 ¶

如果以后把问题改成最短路：

$$
\boxed{
dp[v]=\min(dp[v],dp[u]+w)
}
$$

所以你会发现：

最长、最短、计数，本质上只是 DP 运算不同。

三十、课后训练 ¶

建议按以下顺序训练。

Level 1 ¶

DAG 最长路
DAG 最短路
DAG 路径数量

Level 2 ¶

DAG 最大权路径
DAG 路径方案数 + 模
关键路径

Level 3 ¶

DAG 上最长路径并恢复具体路径
DAG 上路径数量并恢复一条方案
多起点 DAG DP
DAG 上状态带多个维度的 DP

下一讲：状态压缩 DP ¶

接下来进入 DP 中非常经典、也非常容易让学生“突然开窍”的一类：

第七讲：状态压缩 DP ¶

我们会从一个非常经典的问题开始：

旅行商问题 TSP

例如有：

城市 1
城市 2
城市 3
城市 4
...
城市 n

要求从某个城市出发：

每个城市恰好访问一次，最后回到起点，求最小总距离。

普通的：

dp[i]

显然不够。

因为我们不仅需要知道：

当前在哪里

还必须知道：

哪些城市已经访问过。

于是产生一个非常重要的状态：

$$
\boxed{dp[S][i]}
$$

其中：

S：一个二进制集合，表示已经访问过哪些节点
i：当前位于哪个节点

这将正式进入：

Bitmask + DP ¶

也是中学生信息学竞赛中非常重要的一块内容。