数据结构与算法 / 系统课时
DAG 和动态规划怎么结合
DAG 和动态规划怎么结合
DAG 没有环,因此节点可以按拓扑序排成明确的依赖先后。这让许多原本需要反复更新的路径问题变成一次线性推进:当前节点的 DP 状态确定后,只需把结果传给它的后继节点。
学习目标
- 能理解为什么拓扑序可以作为 DAG 动态规划的计算顺序
- 能用一次拓扑遍历解决最长路径、最优值或路径计数
- 能正确处理不可达节点、多入边与环检测
拓扑序为什么能支撑 DP
在普通图中,一个节点的最优值可能依赖尚未计算完成的前驱,因此直接按节点编号遍历并不可靠。DAG 的拓扑序保证每条边 u -> v 中,u 一定排在 v 前面。
于是可以定义 dp[v] 表示“到达 v 的最优值”。当处理 u 时,所有能够影响 dp[u] 的前驱都已经处理完成,再用 dp[u] 去更新后继即可。

这就是 DAG DP 的核心:拓扑排序负责给出合法计算顺序,动态规划负责定义状态以及多个前驱结果如何合并。
先确定状态与转移
以“从起点到各点的最大权值和”为例,可以定义 dp[v] 为从起点到 v 的最大路径权值。对于一条权重为 w 的边 u -> v,如果 u 可达,就尝试用 dp[u] + w 更新 dp[v]。
如果问题改成路径计数,状态仍可写成 dp[v],但含义变成“到达 v 的路径数”,转移则从取最大值改为累加。算法骨架没有变化,真正变化的是状态语义和合并规则。
用拓扑序计算最长路径
下面示例使用 Kahn 算法生成拓扑处理顺序,并在节点出队时推进最长路径。不可达节点保持负无穷,防止它们错误参与转移。
from collections import deque
def dag_longest_path(n, edges, start):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v, w in edges:
graph[u].append((v, w))
indegree[v] += 1
# 所有入度为 0 的节点都可以进入拓扑队列。
queue = deque(i for i in range(n) if indegree[i] == 0)
neg_inf = float('-inf')
dp = [neg_inf] * n
dp[start] = 0
processed = 0
while queue:
u = queue.popleft()
processed += 1
for v, w in graph[u]:
# 只有从起点可达的状态才能向后继传播。
if dp[u] != neg_inf:
dp[v] = max(dp[v], dp[u] + w)
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
# 未处理完全部节点意味着原图中存在环。
if processed != n:
raise ValueError('graph contains a cycle')
return dp
if __name__ == '__main__':
edges = [
(0, 1, 2),
(0, 2, 3),
(1, 3, 4),
(2, 3, 1),
(3, 4, 5),
]
dist = dag_longest_path(5, edges, 0)
print(dist[4])预期输出
11最优路径是 0 -> 1 -> 3 -> 4,权值和为 11。节点 3 有两个前驱,因此它会比较节点 1 和节点 2 传来的候选值,保留较大的结果后再继续向节点 4 推进。
复杂度和常见陷阱
拓扑排序与 DP 都只需处理每个节点和每条边一次,所以时间复杂度为 O(n + m),额外空间主要来自邻接表、入度数组和 DP 数组。
常见错误包括把 dp 全部初始化为 0,导致不可达节点看起来像是已经可达;在没有保证拓扑顺序时提前做状态转移;以及图中存在环却仍按 DAG 的方式计算。
当问题具有明确的单向依赖,而且依赖图无环时,可以优先检查是否能采用“拓扑序 + DP”。任务依赖收益、路径计数、最长链以及按先决条件累积最优值,都是这种组合最常见的落点。