数据结构与算法 / 系统课时

DAG 和动态规划怎么结合

DAG 和动态规划怎么结合

DAG 没有环,因此节点可以按拓扑序排成明确的依赖先后。这让许多原本需要反复更新的路径问题变成一次线性推进:当前节点的 DP 状态确定后,只需把结果传给它的后继节点。

学习目标

  • 能理解为什么拓扑序可以作为 DAG 动态规划的计算顺序
  • 能用一次拓扑遍历解决最长路径、最优值或路径计数
  • 能正确处理不可达节点、多入边与环检测

拓扑序为什么能支撑 DP

在普通图中,一个节点的最优值可能依赖尚未计算完成的前驱,因此直接按节点编号遍历并不可靠。DAG 的拓扑序保证每条边 u -> v 中,u 一定排在 v 前面。

于是可以定义 dp[v] 表示“到达 v 的最优值”。当处理 u 时,所有能够影响 dp[u] 的前驱都已经处理完成,再用 dp[u] 去更新后继即可。

DAG 拓扑序推进动态规划

这就是 DAG DP 的核心:拓扑排序负责给出合法计算顺序,动态规划负责定义状态以及多个前驱结果如何合并。

先确定状态与转移

以“从起点到各点的最大权值和”为例,可以定义 dp[v] 为从起点到 v 的最大路径权值。对于一条权重为 w 的边 u -> v,如果 u 可达,就尝试用 dp[u] + w 更新 dp[v]。

如果问题改成路径计数,状态仍可写成 dp[v],但含义变成“到达 v 的路径数”,转移则从取最大值改为累加。算法骨架没有变化,真正变化的是状态语义和合并规则。

用拓扑序计算最长路径

下面示例使用 Kahn 算法生成拓扑处理顺序,并在节点出队时推进最长路径。不可达节点保持负无穷,防止它们错误参与转移。

python
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])

预期输出

text
11

最优路径是 0 -> 1 -> 3 -> 4,权值和为 11。节点 3 有两个前驱,因此它会比较节点 1 和节点 2 传来的候选值,保留较大的结果后再继续向节点 4 推进。

复杂度和常见陷阱

拓扑排序与 DP 都只需处理每个节点和每条边一次,所以时间复杂度为 O(n + m),额外空间主要来自邻接表、入度数组和 DP 数组。

常见错误包括把 dp 全部初始化为 0,导致不可达节点看起来像是已经可达;在没有保证拓扑顺序时提前做状态转移;以及图中存在环却仍按 DAG 的方式计算。

当问题具有明确的单向依赖,而且依赖图无环时,可以优先检查是否能采用“拓扑序 + DP”。任务依赖收益、路径计数、最长链以及按先决条件累积最优值,都是这种组合最常见的落点。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

DAG 和动态规划怎么结合

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通