<style> .reveal { font-size: 30px; } </style> <style> .yellow { color: yellow; } </style> # DP 複習與練習 I #### **Gino** --- ### 第一次講課是不是要自我介紹啊   --- # [題單在此](https://hackmd.io/@penguin71630/DPproblem) --- ### 課前提醒 這堂課的定位是複習 主要會再講解一次 DP 的性質還有複習一些重要的經典題 難度約中偏易，然後我可能會飆車 如果上到一半發現有不懂的地方可以在 Discord 的閒聊專區或問題討論區發問 或是回去翻 [DP I](https://drive.google.com/file/d/1BT5_HotYej62klPdfrgjrUkqViJTl-3k/view?usp=sharing) 跟 [DP II 的簡報](https://drive.google.com/file/d/1fVCA6AJ65Z7ZQUQzEfs7JbkAjJRKAnVP/view?usp=sharing) --- ### 再讓我囉嗦一下 然後因為臨時調課 這堂課的簡報是今天爆肝生出來的 內容可能不是很多還請見諒（**#每日關心Foxyy的簡報進度**） 預計一個小時就會講完，剩下兩個小時讓大家刷題 + 提問 + 在 dc 哈拉 很放鬆的一堂課 OwO --- ### 再讓我囉嗦一下下下下下 DP 練習還有一堂課 下次上課會從題單裡面挑一些有趣的題目（我勉強會寫的）來講解 然後如果三生有幸我能夠學會那些 DP 優化的話也會講解 ###### 四邊形優化好難qwq --- # 目錄 - 什麼是 DP - DP 經典題 - 暖身：二維路徑 DP - LIS - 二分搜優化 - 資結優化 - 求 LIS 數量 - 求最小字典序 LIS - 背包問題 - 0/1 背包 - 滾動陣列 - 無限背包 - 有限背包 - 練習時間 --- # DP 是啥 ---- ### 舉個栗子 有 $N$ 階的樓梯，從第 $1$ 階開始，每次可以走 $1$ 階或走 $2$ 階，請問剛好走到第 $N$ 階有多少種方法？ ---- ### 舉個栗子 有 $N$ 階的樓梯，從第 $0$ 階開始，每次可以走 $1$ 階或走 $2$ 階，請問剛好走到第 $N$ 階有多少種方法？ - 定義 $dp[i]$ 為剛好走到第 $i$ 階的方法數 - $dp[0] = 1, dp[1] = 1$ - $dp[i] = dp[i-1] + dp[i-2] \quad \forall i \geq 2$ - 答案就是 $dp[N]$ ---- - $dp[i]$：**狀態** - $dp[0] = 1, dp[1] = 1$：**初始狀態** - $dp[i] = dp[i-1] + dp[i-2]$：**狀態轉移式** ---- ## DP 的性質 ---- 1. **重複子問題**：同一個狀態可能會被用到很多次  ---- $f(2)$ 被呼叫兩次，算過一次就紀錄起來，之後可以直接查，不需要重算  DP 問題的本質是分治與遞迴，而 DP 的精髓在於算過的答案不要重算 - 紀錄子問題 (Memoization) ---- 2. **最佳子結構**：大問題的答案可以從小問題的答案推出 「$f(4)$ 可以從 $f(3)$ 跟 $f(2)$ 推得」 ---- 3. **無後效性**：每個狀態的轉移來源不能相互依賴 「要算 $f(a)$ 需要先算出 $f(b)$，但要算 $f(b)$ 需要先算出 $f(a)$ ...？」 ---- 3. **無後效性**：每個狀態的轉移來源不能相互依賴 把每個狀態想像成節點，轉移關係想像成邊 則合理的狀態定義必定會使所有狀態**形成一個 DAG** 而**可行的轉移順序**便是該圖的其中一種**拓樸排序**  ---- ## DP 的步驟 1. **觀察問題，定義好狀態** - 可以先不管複雜度，但要考慮好所有情況 - 題目列出的條件都可能可以拿來當狀態的參數 2. **推出轉移式** - 好好考慮該如何切成小問題 - 切出來的小問題必須包含所有可能情況，同時又必須互相獨立 - 發現很難轉移 $\Rightarrow$ 修改狀態定義 3. **找到一個合理的轉移順序** - 費式數列：從 $f(0)$ 推到 $f(N)$ - 區間 DP：從小區間推到大區間 - 位元 DP：從小集合推到大集合（或是從 $0$ 到 $2^N$） 4. **優化狀態／轉移過程** ---- ## 實作方式 - Top down ```cpp= int f[100]; int F(int x) { if (x <= 1) return f[x] = 1; return f[x] = F(x-1) + F(x-2); } ``` - Bottom up ```cpp= int f[100]; f[0] = f[1] = 1; for (int i = 2; i < 100; i++) { f[i] = f[i-1] + f[i-2]; } ``` ---- - Top down - 使用時機 - 有用到的狀態很稀疏時 - 轉移確定無後效性，但合理的轉移順序很難找時 - [旅行推銷員問題](https://cses.fi/problemset/task/1690) - Bottom up - 優點：狀態稠密時，常數較小 - 優點：好套優化 - 常見 DP 優化都是把要考慮的轉移來源開個資結處理（前綴和陣列／線段樹／BIT／李超線段樹），或是利用狀態的單調性二分搜、均攤優化（單調隊列／四邊形優化） ---- Bottom up 又可以分兩種 - pull：把答案從子問題「拉上來」 ```cpp f[i] = f[i-1] + f[i-2]; ``` - push：把子問題答案主動「推」到大問題 ```cpp f[i+2] += f[i]; f[i+1] += f[i]; ``` 視實作方便度決定，大部分都是用 pull，少數題目用 push 比較好寫[例如這題](https://codeforces.com/group/3Xn3T5DO0a/contest/362327/problem/D)（KMP+DP） --- # 經典題目 I — 二維路徑DP 暖身一下 ---- [2018北市賽 幸運表格](https://tioj.ck.tp.edu.tw/problems/2182) $n \times m$ 的地圖，每格上面有權重 求從某個格子開始往右／往下移動直到超出邊界，經過的格子權重和最大是多少？ ---- 如果題目是從左上角走到右下角的答案 - $dp[i][j] =$ 走到 $(i, j)$ 的最大權重和 - $dp[i][j] = max($從上面走來$,$ 從左邊走來$)$ - $dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + w[i][j]$ - 答案 $dp[n][m]$ ---- 考慮原題的移動方式，修改一下轉移 - $dp[i][j] = max($從上面走來$,$ 從左邊走來$,$ 從這格開始$)$ - $dp[i][j] = max(dp[i-1][j], dp[i][j-1], 0) + w[i][j]$ - 答案 $max(dp[n][1\sim m], dp[1\sim n][m])$ --- # 經典題目 II — LIS ---- 經典到不能再經典 - 長度 $N$ 的序列 $a$，輸出 $a$ 當中最長非嚴格遞增子序列的 1. 長度 2. 個數 3. 最小字典序的 LIS - [subtask 1](https://neoj.sprout.tw/problem/253/): $N \leq 5000$ - [subtask 2](https://neoj.sprout.tw/problem/254/): $N \leq 10^5$ . ###### P.S. 行尾不要輸出多餘空白 ---- 先求長度 - $dp[i] \equiv$ 結尾位置為 $i$ 的 LIS 長度。 - $dp[i] = max_{j < i \land a[j] \leq a[i]} \{ dp[j] \} + 1$ - 答案是：$max_{1 \leq i \leq N} \{ dp[i] \}$ 轉移直接用迴圈的話複雜度 $O(N^2)$ ---- ### $O(N \log N)$ 作法一 設 $t[len]$ 為所有 $dp[i] = len$ 中最小的 $A[i]$ | $A[i]$ | 4 | 2 | 6 | 5 | 1 | 7 | 3 | 9 | | ------- | --- | --- | --- | --- | --- | --- | --- | --- | | $dp[i]$ | 1 | 1 | 2 | 2 | 1 | 3 | 2 | 4 | | $len$ | 1 | 2 | 3 | 4 | | -------- | --- | --- | --- | --- | | $t[len]$ | 1 | 3 | 7 | 9 | ---- - 有了 $t$ 要怎麼算 $dp[i]$？ ---- - 有了 $t$ 要怎麼算 $dp[i]$？ - 從所有 $\leq A[i]$ 的 $t[len]$ 中，找出最大的 $len$。 - $dp[i] = maxlen + 1$ ---- - 有了 $t$ 要怎麼算 $dp[i]$？ - 從所有 $\leq A[i]$ 的 $t[len]$ 中，找出最大的 $len$。 - $dp[i] = maxlen + 1$ - 如果所有 $t[len]$ 都 $> A[i]$，那就代表前面不能接任何數字 - $\Rightarrow$ $dp[i] = 1$ ---- Claim：$t[len]$ 會單調遞增 Proof：反證法 - 設存在 $j < i$ 使得 $t[j] > t[i]$ - 觀察下圖，會發現 $t[j]$ 不滿足定義 $\Rightarrow$ 矛盾  ---- Claim：$t[len]$ 會單調遞增 找 $maxlen$？ ---- Claim：$t[len]$ 會單調遞增 找 $maxlen$？ ## 二分搜！ ---- ### $O(N \log N)$ 作法二 觀察轉移式：$dp[i] = max_{j < i \land a[j] \leq a[i]} \{ dp[j] \} + 1$ 也就是說，可能的轉移點 $j$ 滿足： 1. $j < i$ 2. $A[j] \leq A[i]$ 所有的 $j$ 當中最大的 $dp[j]$ 就是轉移點。 ---- 可以用一個區間查詢的資料結構維護**區間 $dp$ 值最大值**。 查詢 $dp[i]$ 的最佳轉移點可以用 $query(1, i-1)$ 解決。 ---- 可以用一個區間查詢的資料結構維護**區間 $dp$ 值最大值**。 查詢 $dp[i]$ 的最佳轉移點可以用 $query(1, i-1)$ 解決。 但還有一個條件：$A[j] \leq A[i]$？ ---- 可以用一個區間查詢的資料結構維護**區間 $dp$ 值最大值**。 查詢 $dp[i]$ 的最佳轉移點可以用 $query(1, i-1)$ 解決。 但還有一個條件：$A[j] \leq A[i]$？ ## DP 順序：從 $A[i]$ 越小的開始做！ ---- 可以用一個區間查詢的資料結構維護**區間 $dp$ 值最大值**。 查詢 $dp[i]$ 的最佳轉移點可以用 $query(1, i-1)$ 解決。 但還有一個條件：$A[j] \leq A[i]$？ ## DP 順序：從 $A[i]$ 越小的開始做！ 這樣可以保證 $query(1, i-1)$ 得到的答案必定滿足 $A[j] \leq A[i]$ ---- 資結可以使用線段樹 但其實這題條件很特別，可以用 BIT - 詢問區間只有前綴 - 單點修改時只會把 $0$ 改成 $dp[i]$（數字只會改大不會改小） ---- 求 LIS 個數？ ---- 求 LIS 個數？ $cnt[i]$ 表示**以 $i$ 結尾**的最長遞增子序列**數量** | $A[i]$ | 4 | 2 | 6 | 5 | 1 | 7 | 3 | 9 | | ------- | --- | --- | --- | --- | --- | --- | --- | --- | | $dp[i]$ | 1 | 1 | 2 | 2 | 1 | 3 | 2 | 4 | | $cnt[i]$| 1 | 1 | 2 | 2 | 1 | 4 | 2 | 4 | ---- 假設已經算出 $dp[i]$，考慮求 $cnt[i]$ 則 $cnt[i] = \sum cnt[j]$，$j$ 滿足： 1. $j < i$ 2. $A[j] \leq A[i]$ 3. $dp[j] = dp[i] - 1$  ---- - 使用作法二，維護最大值的同時也維護**滿足該最大值的數量** - 詢問的時候除了回傳最大值也一併回傳**滿足該最大值的數量** - 如何維護交給大家練習 ---- 求最小字典序 LIS？ ---- - 求最小字典序的作法 - Greedy 地由前面往後掃 - 能先拿就拿 - DP 回溯解的方向 - 由後往前回推 兩個方向不同，怎麼辦？ ---- - 求最小字典序的作法 - Greedy 地由前面往後掃 - 能先拿就拿 - DP 回溯解的方向 - 由後往前回推 兩個方向不同，怎麼辦？ ## 把原本的序列倒過來做 DP！ ---- - 求最小字典序的作法 - Greedy 地由<span class="yellow">後面往前掃</span> - 能先拿就拿 - DP 回溯解的方向 - 由後往前回推 ## 把原本的序列倒過來做 DP！ 原本求 LIS 改成求 LDS（最長遞減子序列） ---- ### 練習 - [裸題](https://neoj.sprout.tw/problem/254/) - [NEOJ 421](https://neoj.sprout.tw/problem/421/) - [TOI 初選 pC](https://tioj.ck.tp.edu.tw/problems/2195) --- # 經典題目 III — 背包問題 ---- 背包問題的變形： - 0/1 背包（最原始的） - 無限背包 - 有限背包 ---- [0/1 背包 I — 狀態的維度【考慮第 $i$ 個，總重量】](https://atcoder.jp/contests/dp/tasks/dp_d) $N$ 個物品有各自的重量 $w_i$ 和價值 $v_i$ 背包重量上限 $W$，求最大價值？ - $N \leq 100$ - $W \leq 10^5$ - $v_i \leq 10^9$ ---- - $dp[i][w]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總重 $w$ 的物品的最大總價值 ---- - $dp[i][w]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總重 $w$ 的物品的最大總價值 - $dp[i][w] = max($拿$i,$ 不拿$i)$ - $dp[i][w] = max(dp[i-1][w-w_i] + v_i, dp[i-1][w])$  ---- - $dp[i][w]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總重 $w$ 的物品的最大總價值 - $dp[i][w] = max($拿$i,$ 不拿$i)$ - $dp[i][w] = max(dp[i-1][w-w_i] + v_i, dp[i-1][w])$ - 答案會是 $max_{0 \leq w \leq W} \{dp[N][w]\}$ ---- - $dp[i][w]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總重 $w$ 的物品的最大總價值 - $dp[i][w] = max($拿$i,$ 不拿$i)$ - $dp[i][w] = max(dp[i-1][w-w_i] + v_i, dp[i-1][w])$ - 答案會是 $max_{0 \leq w \leq W} \{dp[N][w]\}$ - 初始狀態和實作細節交給大家練習 - $dp$ 表格大小開 $N \times W$ - 寬只到 $W$ 是因為超過 $W$ 根本不是合法狀態 時間跟空間複雜度 $O(NW)$ ---- 空間 $O(NW)$ 好像太緊了 ---- 觀察到每個狀態 $dp[i][w]$ 的轉移來源都只在上一列 除此之外其他狀態根本用不到 ---- ### 滾動陣列 I - 開兩個陣列 $dp0, dp1$ 交替使用 - 假設現在在 $dp1$，那麼就從 $dp0$ 轉移 - 假設現在在 $dp0$，那麼就從 $dp1$ 轉移  空間複雜度 $O(W)$ ---- 好還要更好！ 兩個陣列 $\Rightarrow$ 一個陣列 ---- ### 滾動陣列 II - 只開一個陣列 $dp$ - 新的狀態要覆蓋舊的狀態 - 確保每個新的狀態的轉移來源都不能被覆蓋到 ---- ### 滾動陣列 II - 只開一個陣列 $dp$ - 新的狀態要覆蓋舊的狀態 - 確保每個新的狀態的轉移來源都不能被覆蓋到 - DP 順序：從 $dp[W]$ 倒著做到 $dp[0]$  ---- [0/1 背包 II — 狀態的維度【考慮第 $i$ 個，總價值】](https://atcoder.jp/contests/dp/tasks/dp_e) $N$ 個物品有各自的重量 $w_i$ 和價值 $v_i$ 背包重量上限 $W$，求最大價值？ - $N \leq 100$ - $W \leq 10^9$ - $v_i \leq 10^3$ ---- - $dp[i][v]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總價值 $v$ 的物品的最小總重 ---- - $dp[i][v]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總價值 $v$ 的物品最小總重 - $dp[i][v] = min($拿$i,$ 不拿$i)$ - $dp[i][v] = min(dp[i-1][v-v_i] + w_i, dp[i-1][v])$ ---- - $dp[i][v]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總價值 $v$ 的物品最小總重 - $dp[i][v] = min($拿$i,$ 不拿$i)$ - $dp[i][v] = min(dp[i-1][v-v_i] + w_i, dp[i-1][v])$ - 假設所有東西總價值和 $sv = \sum_{i=1}^{N} v_i$。 - 取答案的方法： - 從 $dp[N][sv]$ 開始倒著掃到 $dp[N][0]$ - 只要掃到某個 $v$ 滿足 $dp[N][v] \leq W$，$v$ 就是答案 ---- - $dp[i][v]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總價值 $v$ 的物品最小總重 - $dp[i][v] = min($拿$i,$ 不拿$i)$ - $dp[i][v] = min(dp[i-1][v-v_i] + w_i, dp[i-1][v])$ - 假設所有東西總價值和 $sv = \sum_{i=1}^{N} v_i$。 - 取答案的方法： - 從 $dp[N][sv]$ 開始倒著掃到 $dp[N][0]$ - 只要掃到某個 $v$ 滿足 $dp[N][v] \leq W$，$v$ 就是答案 - $dp$ 表格大小開 $N \times sv$ 時間複雜度 $O(N \sum_{i=1}^{N} v_i)$ ---- 無限背包 $N$ 個物品有各自的重量 $w_i$ 和價值 $v_i$，且數量都有無限多個 背包重量上限 $W$，求最大價值？ - $N \leq 100$ - $W \leq 10^5$ - $v_i \leq 10^9$ ---- - $dp[i][w]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總重 $w$ 的物品的最大總價值 - $dp[i][w] = max(dp[i][w-w_i] + v_i, dp[i-1][w])$ 要多少有多少，所以拿了一個 $i$ 之後不必回到 $i-1$ 的狀態  ---- [有限背包](https://codeforces.com/group/3Xn3T5DO0a/contest/350019/problem/D)  ---- - $dp[i][w]$ 考慮到第 $i$ 個物品，且此時背包已經裝了總重 $w$ 的物品的最大總價值 - $dp[i][w] = max($拿$0$個$i,$拿$1$個$i,$拿$2$個$i, ...,$拿$c_i$個$i)$ - $dp[i][w] = max(\\dp[i-1][w],\\dp[i-1][w-w_i] + v_i,\\dp[i-1][w-2w_i] + 2v_i,\\...\\dp[i-1][w-c_i \cdot w_i] + c_i \cdot w_i)$  複雜度 $O(NW\cdot max(c_i))$ ---- - 把第 $i$ 個物品看成 $c_i$ 個獨立的物品 - 直接一起做 0/1 背包 ---- - 把第 $i$ 個物品看成 $c_i$ 個獨立的物品 - $N$ 個物品都這樣做，直接一起做 0/1 背包 複雜度 $O(NW\cdot max(c_i))$ 還是沒變 ---- ### 優化 - 把第 $i$ 個物品拆成 $1$ 個 $i$，$2$ 個 $i$，$4$ 個 $i$，... - 一直用 $2$ 的冪次拆直到不夠拆，餘下的 $i$ 綁在一起。 - $N$ 個物品都這樣拆，把它們一起做 0/1 背包 ---- ### 優化 - 把第 $i$ 個物品拆成 $1$ 個 $i$，$2$ 個 $i$，$4$ 個 $i$，... - 一直用 $2$ 的冪次拆直到不夠拆，餘下的 $i$ 綁在一起。 - $N$ 個物品都這樣拆，把它們一起做 0/1 背包 複雜度 $O(NW\cdot \log(max(c_i)))$ ---- ### 優化 - 把第 $i$ 個物品拆成 $1$ 個 $i$，$2$ 個 $i$，$4$ 個 $i$，... - 一直用 $2$ 的冪次拆直到不夠拆，餘下的 $i$ 綁在一起。 - $N$ 個物品都這樣拆，把它們一起做 0/1 背包 複雜度 $O(NW\cdot \log(max(c_i)))$ **拆的方法只要保證能湊出 $[0, c_i]$ 之間任意數量的物品** **接下來 DP 就會自動幫你算出最好的答案** ---- - 有限背包因為轉移點有時限（$\because$ 物品數量有限） - 所以可以套單調隊列優化 - 這裡不細講，忘記的可以回去看 [DP II 的簡報](https://drive.google.com/file/d/1fVCA6AJ65Z7ZQUQzEfs7JbkAjJRKAnVP/view?usp=sharing) ---- ### 練習 - [2021 附中校隊培訓模競 pE](https://tioj.ck.tp.edu.tw/problems/2222) - [NEOJ 159](https://neoj.sprout.tw/problem/159/) --- 提問時間與練習時間 :D 有人想唱歌或分享酷酷的科技可以開麥 OvO 或是看 **@Foxyy** 直播製作下禮拜的簡報