<style> .reveal .slides { text-align: left; font-size:35px } </style> # 動態規劃(Dynamic Programming) Introduction to Competitive Programming 2/8 ---- ## 搞懂這些 一秒變成通靈大師 * 核心概念及前言 * 認識DP * DP的時間複雜度&&轉移式 * DP實作範例 * DP優化 --- ## 前言及核心概念 ---- ## 前言-DP是啥? * 動態規劃。你當下問題的答案會隨著你解決小問題的時候時刻更新著大問題 * DP題通常難以被其他算法取代，且題型多種多樣。 * 為什麼會說DP是通靈則是因為一定程度的題目通常轉移式都不好求，很吃你的直覺。 * 遇到DP題的頻率大概為1題/場，但 **台灣站 3-5 題/場**，因此若是你DP很強可以拿去說嘴很久。 ---- ## 核心概念 --- DP的必知知識 * 分治 : 將大問題分解成小問題，計算出小問題的答案後再合併出大問題的解 * DP(動態規劃) : 分治法的延伸。當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解，以**空間換取時間**。 * 遇到問題-尋找問題分割方法-把大問題遞迴分割成更小的問題-設計計算過程-實作 ---- ### **[尋找問題分割方法]** 通常在dp裡面，總是可以找到當前狀態的前幾個狀態合併成為當前狀態，而特性如下。 1. 子問題與原問題的求解方式皆類似。 2. 子問題會一而再、再而三的出現。 3. 子問題以及原問題之間存在一定關係。 ---- ### **[把大問題遞迴分割成更小的問題]** 根據以上幾點，尋找到問題之間的關係後，即可分割成小問題去進行求解，求解過程主要是對小問題進行解答後，在根據小問題的答案進行下一步操作。 ---- ### **[設計計算過程]** 1. 確認每個問題需要哪些子問題來計算答案。 2. 確認總共有哪些問題。 3. 把問題一一對應到表格。 4. 決定問題的計算順序。 5. 確認初始值、計算範圍。 ---- ## 實作 分別有兩種方式 1. top-down : 程式碼中採用遞迴結構計算，從大問題往小問題遞迴(因此小問題先被解決)。這個實作方式的好處為只計算必要的問題，以及不必煩惱計算優先順序。 2. bottom-up : 先理出計算順序，然後由最小的問題開始計算。特色是程式碼通常只有幾個迴圈。這個實作方式的好處為執行效率略為優秀，且可以自由控制計算順序，也不必擔心stack overflow(遞迴過多層) ---- ## Top-Down v.s. Bottom-Up - 理論上兩者時間複雜度相同，但前者用遞迴實作通常常數較大 - 對於top-down，若一開始直接呼叫很大的狀態可能會stack overflow - bottom-up需要找出好的計算順序，對於有些DP不易找到 - top-down只會計算該次呼叫所需要用到的所有子狀態，而bottom-up一次記算完所有子狀態 - 對於狀態很疏鬆的DP，bottom-up可能會計算很多冗餘的狀態 ---- - 如果狀態緊密且容易找出計算順序就用bottom-up(常數小，沒有RE風險) - 反之才用top-down - 大多DP都是由小計算到大因此容易找順序，除了少數DP有很奇怪的轉移式 - 大多DP狀態都是滿的，通常是暴搜的記憶化搜索才會是疏鬆的狀態 --- ## 通靈的路上-認識DP 先看過兩題例題，為經典的記憶化搜索 ---- 例題Q1 單條鏈數學式求解 給你 $q$ 次詢問 每次給定數字$n$ 詢問 $n!$ 為多少 根據前面的步驟，會發現 $n!$ 跟 $n-1$ 的關係為 $(n-1)! * n$ 所以就可以分割為 $1,2,3,.......n-1,n$ 設計方法則為 每一層是前一層\*當前層數[ $(n-1)! * n$ ] 實作方法則在下面做出簡單的範例 ```cpp= void factorial(){ f[0] = 0;f[1] = 1; for (int i=2; i<=N; i++) f[i] = f[i-1] * i; } ``` ---- 分析例題一的時間複雜度以及空間複雜度 時間複雜度 : 總共 N 個問題，每個問題花費 O(1) 時間，總共花費 O(N) 時間。 空間複雜度 : 求 1! 到 N!,總共 N 個問題，用一條 N 格陣列儲存全部問題的答案，空間複雜度 O(N) ---- ## 例題Q2 [遞迴數學式求解](https://zerojudge.tw/ShowProblem?problemid=d212)  $q$ 筆詢問 $1$ $\le q \le 2*10^5$ 每筆詢問給予一個數字 $n$ ($1$ $\le n \le 10^6$) ， 求 $f [ n ]$ 值為多少 思路 首先我們分析暴力做他的時間複雜度。 發現到這樣直接暴力解訪問f(n-2)+f(n-1)做會錯。 只需要開一個$10^6$的大小然後 $dp[i]$ 儲存 $f(i)$ 的結果就好，具體代碼如下。 ---- top-down ```cpp int f(int n){ if (n == 0 || n == 1) return 1; // 用 0 代表該問題還未計算答案 if (table[n]) return table[n]; return table[n] = f(n-1) + f(n-2); } int main(){ f(N); int q; while(cin>>q)){ cout<<f(q)<<'\n'; } } ``` ---- Bottom-up ```cpp int main(){ table[0] = 1; table[1] = 1; for (int i=2; i<=N; i++) table[i] = table[i-1] + table[i-2]; int q; while(cin>>q)){ cout<<f(q)<<'\n'; } } ``` ---- 分析例題二的時間複雜度以及空間複雜度 時間複雜度 : 總共 N 個問題，每個問題花費 O(1) 時間，總共花費 O(N) 時間。 空間複雜度 : 求 1 到 N,總共 N 個問題，用一條 N 格陣列儲存全部問題的答案，空間複雜度 O(N) --- ## DP的時間/空間 複雜度&&轉移式 ---- ## DP的時間/空間 複雜度 簡單的時間複雜度 : 狀態數\*轉移複雜度 難的時間複雜度 : 根據每個人會有不同的實作方式去計算 狀態數 : 計算最終答案總共需要用到的子問題數量 轉移複雜度 : 計算任一個子問題的複雜度 空間複雜度 : 很直觀根據你開了多少來確定，應該不用太多描述。 ---- ## DP的轉移式 * 轉移式是用來表達DP的數學式子，類似遞迴數列的式子 * 不管你用何種實作方式都可以寫出一種DP的轉移式，有些簡單明瞭有些複雜到爆 * 主要是描述如何用小問題的解計算出大問題的解，也就是大問題跟小問題之間的關係 * 與greedy不同的是greedy是一直使用同種策略，dp在複雜時會使用小問題擇優，或是多個小問題的集合求解。 ---- ### 範例 - $f(n)=f(n-1)+f(n-2)$ --- [遞迴數學式問題](https://zerojudge.tw/ShowProblem?problemid=d212) - $dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}$ --- [單調隊列優化](https://zerojudge.tw/ShowProblem?problemid=c528) - $dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})$ --- [二階背包問題](https://zerojudge.tw/ShowProblem?problemid=a587) - $dp[i]=max(dp[i],dp[j]+1),\forall arr[i] > arr[j]\land i > j$ --- [LIS 最長遞增子序列](https://zerojudge.tw/ShowProblem?problemid=d052) - $dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$ --- [LCS 最長共通子序列](https://zerojudge.tw/ShowProblem?problemid=c001) ---- ### DP的生命就是轉移式 - 清楚且完整的表達DP的關係 - 每一層的dp都有他所代表的東西 - 從轉移式中可以看出遞迴計算大問題所需要的子狀態與計算方式 - 大多DP可以從轉移式看出總狀態數與轉移複雜度 - 列出轉移式後，照著打就可以輕鬆的寫出DP的程式了(尤其是top-down) - 容易推導dp優化 --- # 下課時間 --- ## DP經典問題實作 * 零錢問題 * 背包問題 * 最長遞增子序列(LIS) * 最長共同子序列(LCS) ---- ## 零錢問題 題序 : 身上帶太多的零錢會很麻煩，因此會希望店員在找零錢能夠以最少的硬幣數來找，而不是全部都用1元塞給我們。 :cactus: 也就是要用最少的硬幣數湊出目標數字，具體作法為比較「每個硬幣的面額」與「其次小硬幣的面額」 :moneybag: 假設需要找$86 【[情況1](https://zerojudge.tw/ShowProblem?problemid=d904)】硬幣有：$50, $10, $5, $1 四種面額，由於每個數字都是次小數字的倍數，因此可以直接用greedy寫掉，從最大的硬幣去選。答案為 50\*1 + 10\*3 + 5\*1 + 1\*1 總共六枚 【[情況2](https://zerojudge.tw/ShowProblem?problemid=d133)】硬幣有：$50, $46, $10, $5, $1 五種面額，這時會發現greedy好像怪怪的，因此這時候就需要使用 [ 動態規劃 ] 去完成這題。 ---- * $dp[ x ]$：紀錄目前要湊成金額 $x$ 的最少硬幣數目。 * 測試每個硬幣面額$coins[ i ]$ * 狀態轉移方程：當採用一個新的硬幣面額可以使用更少的硬幣數目來湊成金額 j 時，更新 `dp[` $j$ `] = min( dp[` $j$ `], dp[` $j$ `– coins[` $i$ `]] + 1)` * 初始化 : $dp[ i ] = \infty$ * 時間複雜度 : 找錢的範圍$N$，零錢種類數量$M$，總共有$NM$個問題，因此時間複雜度為$O(NM)$ ---- ## [背包問題](https://zerojudge.tw/ShowProblem?problemid=b131) n 個物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包有重量限制，如果物品太重，就會撐破背包。 :handbag: 這就是廣為人知的背包問題，其有許多變形，而本堂課將介紹最經典的 [ 0/1 背包問題 ] 「 0/1 」的意思是：每種物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。 看到這種問題若沒學過直覺通常會是貪心，不管是貪心他的價值或是貪心他的CP值也好，在這種題目下面都是錯的。 0/1 背包問題的關鍵點，在於如何有效利用背包的剩餘重量，找出最好的物品組合方式。 ---- 第一步，分割問題。然而分割問題的方式很簡單：對某一件物品來說，我們可以選擇放或不放；然後移去這件物品，縮小問題範疇。 一件物品不放進背包，背包價值不變、背包耐重不變；一件物品放進背包，背包價值上升、背包耐重下降。遞迴公式為： $c$ ($n$, $w$) $=$ $max$$( c(n-1, w)$, $c(n-1, w-weight[n])$ $+$ $cost[n]$ ) 就可以依照這個遞迴公式去設計top-down的版本，而bottom-up的迴圈版本如下: ```cpp for (int i = 0; i < n; ++i) for (int j = w; j - weight[i] >= 0; j--) // 由後往前 dp[j] = max(dp[j], dp[j - weight[i]] + cost[i]); ``` ---- * $dp[ x ]$：紀錄目前背包重量限制為 $x$ 的可裝最大價值。 * 測試每個物品$weight[ i ]$ * 狀態轉移方程：當有一個更好的方法是在同重量下可以獲得更高價值時，更新 $dp[j] = max(dp[j], dp[j - weight[i]] + cost[i]);$ * 初始化 : $dp[ i ] = 0$ * 時間複雜度 : 背包的範圍$N$，物品種類數量$M$，總共有 $NM$ 個問題，因此時間複雜度為 $O(NM)$ ---- ## 最長遞增子序列(LIS) 題序 : 從一連串的整數序列中選出最長的嚴格遞增子序列（strictly longest increasing subsequence）。例如：在 $1, 3, 2, 2, 4, 0$ 中最長的嚴格遞增子序列為 $1, 3, 4$ 或者 $1, 2, 4$。 第一步 分割問題，會發現有許多遞增子序列都是符合要求的子序列，因此解法只需要記錄在每個長度下最長的遞增子序列長度 第二步 設計算法，每次檢查當前的是否比前一個大，若是 則 dp 式轉移+1 ---- 範例代碼 ```cpp int LIS(){ // 初始化。每一個數字本身就是長度為一的 LIS。 for (int i=0; i<N; i++) length[i] = 1; for (int i=0; i<N; i++) // 找出 s[i] 能接在哪些數字後面， // 若是可以接，長度就增加。 for (int j=0; j<i; j++) if (s[j] < s[i]) length[i] = max(length[i], length[j] + 1); // length[] 之中最大的值即為 LIS 的長度。 int l = 0; for (int i=0; i<N; i++) l = max(l, length[i]); return l; } ``` ---- * $dp[ i ]$ : 以$s[i]$為結尾的最長遞增子序列長度 * 測試每個字串結尾$s[ i ]$ * 狀態轉移方程：當有一個更好的方法是在同長度下可以獲得更長序列時，更新 : $dp[i]=max(dp[i],dp[j]+1)$ * 初始化：$dp[i]=1, (1 \le i \le n)$ 至少選自己長度為1 * 時間複雜度 : 狀態數$O(N)$，轉移複雜度$O(N)$，共有$N*N$個問題，所以總複雜度$O(N^2)$ ---- ## 最長共同子序列(LCS) 題序 : 給定兩個字串$s, t$，求 $s$ 與 $t$ 的最長共同子序列( Longest Common Subsequence ) 第一步 分割問題，會發現有許多共同子序列都是符合要求的子序列，因此解法只需要開兩個維度記錄在每個分別前綴下的最長共同子序列長度 第二步 設計算法，每次檢查當前的是否與另一個的當下一樣，若是一樣 則 $dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1$ 否則 $dp[ i ][ j ]$ 就會等於 $dp[i-1][j]$ 或 $dp[ i ][ j-1 ]$ ---- ### sample x = "ABCBDAB" y = "BDCABA"  ---- ## 路徑回朔 要尋找哪一個才是合法的LCS時，我們就需要紀錄每一個字符的選取，由於每次查找的是 $dp[x-1][y]$ 跟 $dp[x][y-1]$ 那個長度更長。最後從 $len1$ , $len2$ 开始往前回溯，輸出最常公共子序列。 ---- 範例代碼 ```cpp void output(int x,int y){ if(!x&&!y) return ; if(tag[x][y]==0){ output(x-1,y-1); cout<<s1[x-1]; } else if(tag[x][y]==1) output(x-1,y); else output(x,y-1); } int main(){ while (cin >> s1 >> s2) { l1 = strlen(s1); l2 = strlen(s2); for(int i=1;i<=l1;i++) tag[i][0]=1; for(int i=1;i<=l2;i++) tag[0][i]=-1; for (int i=1; i<=l1; i++) { for (int j=1; j<=l2; j++) { if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; tag[i][j] = 0; } else if(dp[i-1][j]>=dp[i][j-1]){ dp[i][j] = dp[i-1][j]; tag[i][j] = 1; } else{ dp[i][j]=dp[i][j-1]; tag[i][j] = -1; } } } cout << dp[l1][l2] << "\n"; output(l1,l2); } } ``` ---- * $dp[i][j]$代表字串前綴$s_{0...i}$與$t_{0...j}$的LCS * 轉移式 : $dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$ * 初始化 : $dp[i][1]=dp[1][j]=0$ * 時間複雜度 : 狀態數$O(n^2)$，轉移複雜度$O(1)$，總複雜度$O(n^2)$ * 通常為了方便會把 $dp$ 陣列平移，且此 DP 可以滾動 --- ## DP優化 ---- ## 時間上的優化 - 有非常多的種類，分別用在不同的情況 - 單調隊列優化、斜率優化、四邊形優化、分治優化、矩陣快速冪、多項式乘法、aliens優化... - 由於是進階內容，本堂課程內容著重於讓大家認識DP以及可以靠自己列出轉移式，因此本堂沒有要教，若已熟知基礎DP內容或是對以上優化有興趣都可以再來敲我們問 ---- ## 空間上的優化 ### 滾動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]; ``` 就成功的作出了空間優化了 --- # 副教練的總結 DP是個博大精深的演算法，初學者剛學演算法很快就會碰到，然而難的DP也可以到變成防破台 :fearful: 也是因為DP不論從難度、類型來看，變化都非常多，所以幾乎所有競賽 DP 都扮演很重要的角色(台灣站更是每年 DP 占了都 1/3 的題數)，也因此好好學會DP非常的重要! DP不算是一個制式的演算法，而是一種概念，因此它的用途/形式多變想學好它不是很容易，要能在在看到題目時有辦法快速辨別能不能 DP/怎麼 DP 等只能靠多看題目多練習(把各種類型的DP都看很多次自然而然就會熟悉模式了(O)) :poop: --- Jakao ---- ## 我的總結 DP雖然有著需要通靈，通靈比賽等臭名，不過若你有著很清晰的思路可以分析每一個階段的話，其實DP不是一個需要那麼害怕的算法。:beer: 需要記得的就是在最一剛開始給你們舉例的步驟 - 遇到問題-尋找問題分割方法-把大問題遞迴分割成更小的問題-設計計算過程-實作 也有人可以幾乎沒練習多少題就可以DP很強，那些通靈系選手就不太需要理他們 :beers: