DP 複習與練習 I

--- title: DP 複習與練習 I tags: Competitive Programming slideOptions: transition: fade spotlight: enabled: false --- <style> .reveal { font-size: 30px; } </style> <style> .yellow { color: yellow; } </style> # DP 複習與練習 I #### **Gino** --- ### 第一次講課是不是要自我介紹啊 ![](https://i.imgur.com/auhGU9w.png) ![](https://i.imgur.com/z5AGGrf.png) --- # [題單在此](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. **重複子問題**：同一個狀態可能會被用到很多次 ![](https://i.imgur.com/OIEJ63k.png) ---- $f(2)$ 被呼叫兩次，算過一次就紀錄起來，之後可以直接查，不需要重算 ![](https://i.imgur.com/H02Wi0U.png) DP 問題的本質是分治與遞迴，而 DP 的精髓在於算過的答案不要重算 - 紀錄子問題 (Memoization) ---- 2. **最佳子結構**：大問題的答案可以從小問題的答案推出「$f(4)$ 可以從 $f(3)$ 跟 $f(2)$ 推得」 ---- 3. **無後效性**：每個狀態的轉移來源不能相互依賴「要算 $f(a)$ 需要先算出 $f(b)$，但要算 $f(b)$ 需要先算出 $f(a)$ ...？」 ---- 3. **無後效性**：每個狀態的轉移來源不能相互依賴把每個狀態想像成節點，轉移關係想像成邊則合理的狀態定義必定會使所有狀態**形成一個 DAG** 而**可行的轉移順序**便是該圖的其中一種**拓樸排序** ![](https://i.imgur.com/FW0Tdwu.png) ---- ## 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$ 矛盾 ![](https://i.imgur.com/FGxFNiX.png) ---- 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$ ![](https://i.imgur.com/kr2MheH.png) ---- - 使用作法二，維護最大值的同時也維護**滿足該最大值的數量** - 詢問的時候除了回傳最大值也一併回傳**滿足該最大值的數量** - 如何維護交給大家練習 ---- 求最小字典序 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])$ ![](https://i.imgur.com/96ogSjT.png) ---- - $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$ 轉移 ![](https://i.imgur.com/bK9cuUC.png) 空間複雜度 $O(W)$ ---- 好還要更好！兩個陣列 $\Rightarrow$ 一個陣列 ---- ### 滾動陣列 II - 只開一個陣列 $dp$ - 新的狀態要覆蓋舊的狀態 - 確保每個新的狀態的轉移來源都不能被覆蓋到 ---- ### 滾動陣列 II - 只開一個陣列 $dp$ - 新的狀態要覆蓋舊的狀態 - 確保每個新的狀態的轉移來源都不能被覆蓋到 - DP 順序：從 $dp[W]$ 倒著做到 $dp[0]$ ![](https://i.imgur.com/KNVYgvR.png) ---- [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://i.imgur.com/YyHaDTq.png) ---- [有限背包](https://codeforces.com/group/3Xn3T5DO0a/contest/350019/problem/D) ![](https://i.imgur.com/jvWymWO.png) ---- - $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)$ ![](https://i.imgur.com/Oiy6ibp.png) 複雜度 $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** 直播製作下禮拜的簡報

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.