題目描述: 有 n 門課程和它們之間的先修關係。每門課有完成時間 time[i]。可以同時修多門課(只要先修條件滿足)。求完成所有課程需要的最短時間。
解題思路: 這是一個 DAG 上的最長路徑問題。使用拓撲排序 + 動態規劃。
這等價於求 DAG 上的關鍵路徑(Critical Path),即最長路徑。
時間複雜度:O(n + m) — 拓撲排序遍歷每個節點一次、每條邊一次,其中 m 為先修關係數量。
空間複雜度:O(n + m) — 鄰接表 O(m),入度陣列和 dp 陣列 O(n)。
1. Build adjacency list and in-degree array from relations.
2. Initialize dp[i] = 0 for all courses.
3. For each course i with in-degree 0: dp[i] = time[i], enqueue i.
4. While queue is not empty:
a. Dequeue course u.
b. For each successor v of u:
- dp[v] = max(dp[v], dp[u] + time[v]).
- Decrement in-degree of v. If 0, enqueue v.
5. Return max(dp[1..n]).DFS + 記憶化:從每個節點做 DFS,dp[u] = time[u] + max(dp[v] for all predecessors v)。使用記憶化避免重複計算。時間複雜度相同 O(n + m),但遞迴深度可能造成堆疊溢位。
反向拓撲排序:反轉所有邊的方向,從出度為 0 的節點開始做拓撲排序。dp[u] 表示從 u 出發到結束的最長路徑。最後取 dp 的最大值。本質相同,只是遍歷方向不同。