<style> .reveal .slides { text-align: left; font-size:28px; } </style> # DP Introduction to Competitive Programming 2/16 ---- ## Outline - Classic DP Problems - Largest Sum Contiguous Subarray - LCS vs LIS vs Edit distance - subset sum & bitset 優化 - 01背包 vs 無限背包 vs 有限背包 - 空間優化 - 滾動數組 --- ## 經典DP題目 ---- ## 最大連續區間和 問題敘述 : 第 $i$ 個賭局可以贏得 $a_i$ 塊錢，以正數與負數表示表示贏錢與輸錢 選任意一局開始，連續的賭局當中最多可以贏得多少錢 題目的意思等價於求一個序列中子區間的最大連續和 分析每個 $a_i$ 會發現只有兩種情況，一種是包含在答案的子序列中(必須是連續的)，另一種是它是新的連續子序列的開頭。 而其中不包含在答案的子序列中就不必討論，只討論包含在答案的子序列中。 ---- 可以把 $dp[i][j]$ 定義成表示第 $i$ 項在兩種情況當中前 $i$ 項的最大連續和 其中 $j$ 代表前頁的第幾種情況 若 $j=0$ 代表第 $i$ 項包含在答案的子序列中 若 $j=1$ 代表第 $i$ 項是新的連續子序列的開頭 則可以求出轉移式 $$ \begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + a[i] \\ dp[i][1] = a[i] \end{cases} $$ 初始化 $$ \begin{cases} dp[0][0] = 0 \\ dp[0][1] = a[0] \end{cases} $$ ---- 為何是 $$ \begin{cases} dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + a[i] \\ dp[i][1] = a[i] \end{cases} $$ 因為對於 $dp[i][0]$(這一項必取) 來說，它包含前幾項的最好，所以它會是 $dp[i-1][0]$(前一項也取) 或者是 $dp[i-1][1]$(前一項是第一項) 的 $max$ 加上他自己 而對於 $dp[i][1]$ 來說，他自己就是第一項，因此它的值 (對第 $i$ 項來說 $i$ 就是第一個) 會是 $a[i] + 0$ --- ## LCS vs LIS vs Edit distance LCS : 最長共同子字串 詳情見上次 [dp講義](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/5/6) LIS : 最長遞增子字串 詳情見上次 [dp講義](https://hackmd.io/@LeeShoWhaodian/HyjsE1soi#/5/9) Edit distance : 最短編輯距離 本日重點 * LCS to LIS * Edit distance * 三種 dp 進行比對 ---- 在那之前要先補充二分搜的 $LIS$ 作法  從 $1$ 到 $n$ 遍歷 $A$ 的每個元素，每次與 $X$(當前LIS) 裡的元素進行檢查， 若是比結尾元素大就加入，若沒有就使用 $lower\_bound$ 取代原本的位置。 ---- ### sample code 從 $1$ 到 $n$ 遍歷 $A$ 的每個元素，每次與當前 LIS 裡的元素進行檢查， 若是比結尾元素大就加入，若沒有就使用 $lower\_bound$ 取代原本的位置。 ```cpp= vector<int> getLIS(vector<int> a){ vector<int> lis; for(int i : a){ if(lis.empty() || lis.back() < i) lis.push_Back(i); else *lower_bound(lis.begin(), lis.end(), i) = i; } return lis; } ``` ---- ## LCS to LIS 為何需要轉換? * 求出 LCS 的時間、空間複雜度都是 $O(N^2)$ ，使用滾動陣列技巧，可將空間複雜度降至 $O(N)$ * 求出 LIS 的時間複雜度 $O(N^2)$ ，空間複雜度 $O(N)$ ，但其中 LIS 的時間複雜度可以使用二分搜 (lower_bound) 優化成 $O(N\log N)$ 怎麼轉換? * LIS 轉 LCS ：令原序列 A 排序後變成 B 。 A 和 B 的 LCS ，就是 A 的 LIS 。 * LCS 轉 LIS ：將序列 A 和 B 當中的相同字母配對通通找出來，表示成位置數對，以特殊規則(Counting sort)排序，然後找到 LIS ，就是 A 和 B 的 LCS 。 ---- LCS 轉 LIS 於是你會發現二維平面的 LCS 會變成二維平面的 LIS  ---- 二維平面的 LIS 聽起來複雜度並沒有比較好，因此 所有數對：第一維由小到大排序；當第一維平手，則第二維由大到小排序。 排序之後，原本數對們的 2D LIS ＝第二維的 1D LIS 於是就可以將LCS在經過一連串的預處理之後變成 $O(n \log n )$ 的時間複雜度。  ---- ## Edit distance ex : $string_1$ : horse $string_2$ : ros 所謂 Edit distance 就是 $string_1$ 最少要幾步才能變成 $string_2$ ，而其中每一步可以是 “新增”、“刪除” 或是 “取代”。所以第一個範例 horse 經過了 1. 用 r 取代 h 2. 把中間的 r 刪除 3. 把最後的 e 刪除 就可以得到 ros ，共花了 3 步 (3 就是答案)。 ---- 通常如果是需要去比對兩個字串的題目，我們會定義狀態為一個二維陣列 $dp[i][j]$ $dp[i][j]$ 為 $string_1$ 中前 $i$ 個字元的字串和 $string_2$ 中前 $j$ 個字元的字串的 Edit Distance 而我們知道子問題後，我們的答案就顯而易見是 $dp[len(string_1)][len(string_2)]$ 而很重要的初始化會發現，每個字串到空字串之間最快的路徑就是直接"消除"，因此會有以下初始化 : $$ \begin{cases} dp[i][0] = i \ , i \leq len(string_1)\\ dp[0][j] = j \ , j \leq len(string_2)\\ \end{cases} $$ ---- 然後我們只需要思考， $dp[i][j]$ 可以怎麼轉移。 分別有兩點 * 當 $string_1$ 第 $i$ 個字和 $string_2$ 第 $j$ 個字相同時，則 $dp[i][j] = dp[i-1][j-1]$ ，因為此時不需要做任何操作即相同。 * 當 $string_1$ 第 $i$ 個字和 $string_2$ 第 $j$ 個字不同時，則會有三個操作 1. 刪除 : 刪除第 $i$ 個字，此時 $dp[i][j]$ 為 $dp[i-1][j]+1$ (後面的 +1 代表刪除) 2. 新增 : 新增第 $i$ 個字，此時 $dp[i][j]$ 為 $dp[i][j-1]+1$ (後面的 +1 代表新增) 3. 取代 : 把 $string_1$ 的第 $i$ 個字變成 $string_2$ 的第 $j$ 個字，此時 $dp[i][j]$ 狀態方程為 $dp[i-1][j-1]+1$ (後面的 +1 代表取代)。 所以可以總結出狀態轉移方程為 $dp[i][j]= min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1$ ---- ## LCS vs LIS vs Edit distance || $\texttt{時間複雜度}$ | $\texttt{空間複雜度}$ | $\texttt{狀態轉移式}$ | |:-------------:| --------- | ----- | ------------- | | LIS | $n\log n$ | $n$ | $\texttt{max(dp[i],dp[j]+1)}$ | | LCS | $n^2$ | $length(str_1)$ | $\texttt{dp[i-1][j-1]+1}$ or $\texttt{max(dp[i][j-1], dp[i-1][j])}$ | | Edit distance | $n^2$ | $length(str_1)$ | $\texttt{min(dp[i][j-1]},\\ \texttt{dp[i-1][j]},\\ \texttt{dp[i-1][j-1])+1}$ | --- ## subset sum 給一個陣列 ex : {3, 34, 4, 12, 5, 2}, sum = 9 如果裡面的數字挑選幾個出來，相加等於 9 就代表符合這個問題。 ---- 首先會思考到，由於只能挑跟不挑，所以可以暴力枚舉每一個數字是否再答案裡面，然後再思考一下時間複雜度就會發現，需要的量級是指數級的，為 $O(2^n)$ 所以 $n$ 稍微大一點就很容易TLE 所以會需要使用到動態規劃，令 $dp[i][j]$ 表示 $arr$ 中前 $i$ 個元素的子集和等於 $j$ 的情況，則 若 $arr[i] > j$ ，則 $arr[i]$ 不在子集 $subset$ 中。 若 $arr[i] \le j$ , 則有以下兩種情況：一種情況是 $arr[i]$ 不在子集 $subset$ 中，則 $dp(i, j) = dp(i-1, j)$ 一種情況是 $arr[i]$ 在子集 $subset$ 中，則 $dp[i][j]= dp[i-1][j-arr[i]]$ 這樣就有了這個問題的子結構問題，因此，只需要確定初始情況即可 而初始情況即為對於 $i=0,1,2,...,n$ ,有 $dp[i][0]=True$ , 對於 $j=1,2,...,M$ , 有 $dp[0][j]=False$ ---- 然後你就會發現代碼會長這樣 ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(j<arr[i]) dp[i][j] = dp[i-1][j] else dp[i][j] = dp[i-1][j] | dp[i-1][j-S[i-1]] ``` 而倘若你需要知道 subset 是由那些 sub_element 組合成的，則可以把 DP 的真值表印出來，參考上次 LCS 的回朔法使用查詢。 [參考甲文](https://www.cnblogs.com/jclian91/p/9132663.html) ---- ## 0/1背包 bitset 優化 例題 : [zerojudge a416](https://zerojudge.tw/ShowProblem?problemid=b951) 題目敘述轉化 : 把一列大小為 $n$ 整數序列分成兩個子集且讓兩個子集的 sum 最接近 那這邊我們就可以用到 bitset 的思想，首先先介紹一下 bitset 的用法和為何使用 bitset : * 對於 bitset，它儲存的是二進制數位。 * bitset 就像一個 bool 類型的陣列一樣，但是有空間優化：bitset 中的一個元素只占 1 bit，相當於一個 char 所占空間的八分之一。 * bitset 中的每一個元素都可以被單獨存取，例如一個叫做 foo 的 bitset，foo[3] 存取了它的第四個元素，這點類似於陣列。 * bitset 有一個特性：整數類型和 bool 陣列都可以轉化為 bitset。 * bitset 的大小在編譯前就需要確定 (程式碼中使用常數宣告大小) 。 [更多具體用法以及魔法](https://www.cnblogs.com/RabbitHu/p/bitset.html) ---- 對於這道題，我們用 bitset 來替代 DP，bits[j] 的含義與 DP[j] 的含義相同。就是是否有這樣的一個子集的總和是 $j$ 假設現在有一個數組 {2,3,5,2,3,5} 很明顯可以看出它的解答是 $2+3+5=10$ 那對於我們的 bitset 數組會長這樣 ```cpp bitset<N> dp(1); dp {1} //代表0可以選 (有一個子集合是0) dp {101} //加入'2' 了，把原本所有1的bit左移兩個 現在代表 '2' 和 '0' 都可以有子集合 dp {101101} //加入'3'了，把原本所有1的bit左移三個 '0' '2' '3' '5' 都有子集合 dp {10110101101} //加入'5'了，把原本所有1的bit左移五個 //依此類推 ``` 到最後只要詢問 $sum/2$ 開始往左右邊遍歷就可以知道答案了。 --- ## 空間優化 ### 滾動DP 很直覺的優化方式之一 滾動數組的作用在於優化空間。因為DP題目是一個自底向上的擴展過程，我們常常需要用到的是線性的解，前面的解往往不用紀錄。所以用滾動數組優化是很有效的。利用滾動數組的話在N很大的情況下可以達到壓縮存儲的作用，通常可以直接壓掉一個維度的大小。 ex: dp[N][M] $\to$ dp[N] ---- - 再次拿遞迴數學式來舉例 - $f(n)=f(n-1)+f(n-2)$ - 可以看出計算每一項在計算時，只會用到$dp[n],dp[n-1],dp[n-2]$ - 因此原本需要開到$N$大的空間數組就不需要開，只需要開3個變數 - 只能用bottom-up計算，只需要三個變數交替使用$cur,pre,ppre$ ```cpp int cur,pre=1,ppre=0; for(int i=2;i<=n;i++) cur=pre+ppre,ppre=pre,pre=cur; ``` ---- ### 滾動DP結論 - 用來節省空間，常常可以節省一個維度 - 不是所有DP都可以滾動 - 用於bottom-up，單次計算 - 從轉移式中看計算每一項所需要用到的子狀態是否有跟著遞增(算到後面，前面的狀態就不會再被使用) ---- ## 直接實作最後一題 : 二階樓梯記數問題 一個$n\times n$方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。請問有幾種走法？ example :  第一步 分割問題 會發現對於任何一個方格來說，只可能「從上走來」或者「從左走來」，答案是兩者相加，也就是說可以從上方以及左方的方格步數推算出當前這格的步數。 ---- 設計轉移式 $dp[i][j]$代表走到當前 $i$, $j$ 格有幾種方法，因此$dp[i][j] = dp[i-1][j] + dp[i][j-1]$ 然後這時候就會發現，他的轉移式只需要用到$i$的前一項或者是$j$的前一項，那是否可以節省空間呢 答案是必然的，如果不需要儲存所有問題的答案，只想要得到其中一個特定問題的答案，那只需要一維陣列就夠了，也就是 O(N) 空間。 ```cpp for (int i=1; i<N; i++) for (int j=1; j<N; j++) f[j] += f[j-1]; ``` 就成功的作出了空間優化了 ---- ## bonus 關於最大連續子區間和 同時會發現到dp轉移式裡面只轉移 $i$ 以及 $i-1$ ，這可以使用 rolling 壓縮空間複雜度，因此會變成這樣。 ```cpp dp[i&1][0] = max(dp[(i-1)&1][0], dp[(i-1)&1][1]) + m; dp[i&1][1] = m; ``` 而時間複雜度會是$O(n)$ --- ## [練習 提問 題單](https://vjudge.net/contest/603968)