考点

拓扑排序、图论、递推 / 记忆化搜索。

思路分析

题目给定 n 个任务，每个任务有完成耗时和前置任务。完成所有任务的最短时间，就是从起点到终点的最长路径（因为耗时最长的链决定了整体完成时间）。

本题用 DAG 建图 + 记忆化 DFS 解决：

  1. 对每个任务，记录它的前序任务（即谁指向它）
  2. 用 DFS 从每个节点出发，递归计算到达该节点的最长路径
  3. 记忆化搜索避免重复计算

代码实现

1
2
3
4
5
6
7
8
9
static int dfs(int x) {
    if (f[x] != 0) return f[x];
    for (int i = 0; i < edge[x].size(); i++)
        f[x] = Math.max(f[x], dfs(edge[x].get(i)));
    f[x] += a[x];
    return f[x];
}

// 建图时注意: edge[y].add(x) 表示 y 是 x 的前序

小结

  • “完成所有任务的最短时间” 在 DAG 中 = 最长路径
  • 记忆化搜索是 DAG 上 DP 的常用实现方式
  • 建图时注意边的方向：前序指向后续