主题： Dynamic Programming (III).pptVIP

主題: Dynamic Programming (III) DP 的進階概念 DP 與 multi-stage graph 的關係 DAG shortest path problem multi-dimensional DP multi-recurrence DP 例題講解: A.10604, H.91.6 歷年題目 DAG shortest path problem 給定一個 directed acyclic graph (DAG)，每條 edge 都有 weight (可能為負數)，求從起點 s 到其他 vertex 的 shortest path 解題方法: DP 首先對給定的 DAG 進行 topological sort 使原圖得成為一個 multi-stage graph vertices 按照 stage 由小到大排好 edges 全部由小的 stage 指向大的 stage 解題方法 (cont.) 若 vertex u 有 edge 指向 vertex v，則 u 為 v 的 predecessor 從 s 出發到任一個 vertex v 的可能走法，必然會經過某個 v 的 predecessor v 的 distance 需要其 predecessors 的 distance 解題方法 (cont.) 要算出 v 的 distance，就要先算出每一個 predecessor u 的 distance，再加上 u 到 v 的 edge weight，然後從每個 predecessor 算出的總合距離中找出最小值 dist[v] = min {dist[u] + weight(u, v), ?} Boundary condition: dist[s] = 0 Example (bottom-up computation) DP 與 multi-stage graph 的關係 DP 的特徵在於先把子問題的解算出來，再集合起來算出原問題的解，這種關係可以被表示成一個 multi-stage graph (不見得只能用格子之間的關係來敘述) 把每一個子問題變成一個 vertex 當子問題 A 需要用到子問題 B 的解，則 vertex A 有 edge 指向 vertex B (edge 可加上適當的 weight) recurrence 描述每一個 vertex 和其 predecessors 的關係 (top-down) 計算時，由小到大一個一個 stage 完成 (bottom-up computation) Critical path problem 給定一個 DAG，每條 edge 都有 weight，在 graph 中找出一條最長的 path 沒有規定此 path 的起點 vertex Solution 將每一個 vertex 都設為起點 (distance 為 0)，然後每一個 vertex 去計算可以往前連的多遠，recurrence 如下:dist[v] = max {dist[u] + weight(u, v), 0} Critical path 也是一個 DP problem，其最佳解的長度即為所有 vertex 中，可以往前連到的最遠距離: max{dist(v)} for all v Example: LCS Longest increasing sequence 之前教的做法是用原來的 sequence 和 sorted sequence 做 LCS 現在可以把每一個數字當成一個 vertex，若第 i 個數字 ? 第 j 個數字 (i j)，則 i 到 j 有 edge 且 weight = 1，如此會直接形成一個 multi-stage graph，其最佳解可經由 critical path 得到 Recurrence: LIS length[i] = max {length[k]} + 1 雖然此 recurrence 一樣是 O(n2) 的時間，但 max 的部分還可以做的更快 從第一個 vertex (數字) 開始依序往後計算 用陣列 last 輔助算出每個 vertex i 的 length(i) 修正陣列 last 的內容 Last 陣列 Last[j]: 存放現在已知所有 length = j 的 paths 中，終點 vertices 中值最小的數字 計算 length(i) 要算 vertex i 的 length，可以用 i 的數字 ai 在 last 中進行 binary search (last 中的數字一定會呈現遞增順序) 當 binary search 使得 last[j] ? ai la