題目描述: 給定一個有向無環圖(DAG),節點編號 0 到 n-1。找出所有從節點 0 到節點 n-1 的路徑。graph[i] 表示從節點 i 可以到達的所有節點。
解題思路:
時間複雜度:O(2^n * n) — 最壞情況下,DAG 中可能有指數級的路徑數,每條路徑長度最多為 n
空間複雜度:O(n) — 遞迴深度最多為 n(不計算答案所需空間)
1. Initialize result list and path = [0]
2. Call DFS from node 0
3. DFS(node):
a. If node == n-1: add copy of path to result, return
b. For each neighbor in graph[node]:
- Append neighbor to path
- DFS(neighbor)
- Remove last element from path (backtrack)
4. Return resultBFS 方法:使用佇列存儲 (當前路徑) 的方式進行 BFS。每次從佇列取出一條路徑,擴展最後一個節點的鄰居。缺點是需要存儲大量中間路徑,空間消耗較大。
動態規劃 / 記憶化搜尋:dp[node] 記錄從 node 到 n-1 的所有路徑。從終點往回推導。對於本題因為需要列舉所有路徑,記憶化的加速效果有限,但代碼結構上更清晰。