{%hackmd @hipp0\Hippotumuxthem %} <style> .text-center{ text-align: center; //文字置中 } .text-left{ text-align: left; //文字靠左 } .text-right{ text-align: right; //文字靠右 } </style> <style> .reveal .slides { text-align: left; font-size:30px; } </style> ## 修課表單  --- - 複習 (DSU) - DP (動態規劃) - 數論 (快速冪，模運算，費馬小定理，矩陣快速冪) --- ## DSU 併查集（英文：Disjoint-set data structure，直譯為不交集資料結構）是一種資料結構，用於處理一些不交集（Disjoint sets，一系列沒有重複元素的集合）的合併及查詢問題。 ---- ### 核心三要素 - 查詢：查詢某個元素屬於哪個集合，通常是返回集合內的一個「代表元素」。這個操作是為了判斷兩個元素是否在同一個集合之中。 - 合併：將兩個集合合併為一個。 - 添加：添加一個新集合，其中有一個新元素。添加操作不如查詢和合併操作重要，常常被忽略。 ----  ---- ## 使用 DFS 暴力搜尋，效率不好! ---- ### 簡單的概念 - 標記組別 - 相連 => 同個組別 - 一開始定義自己為一個組別 ---- 首先，還沒有任何網路線連接時，每一台電腦都是屬於自己的群組，也就是同組內的最小號碼都是自己  ---- 如果此時連接1和5，那就把5號電腦那格改成1號。  ---- 在連接2和7，就把7號改成2號，詢問7號和1號相通嗎? 答案是並不相通，因為1號屬於1號群組，7號屬於2號群組  ---- 如果在連接2和5 請注意：因為7也和2同一組，因此要把2和7都改成1號群組，再詢問一次7號和1號相通嗎？ 這時因為7號和1號都屬於1號群組，所以是相通的。  ---- ### 效率不好 雖然作法簡單，但看出問題所在了嗎？ 每次改動會耗上很多時間，尤其當其一群組擴大的時候像是  如果要連接1號和2號，那麼就要把2號至100萬號都改成1號群組，這樣就要改999999次了。 此時只要轉個小想法，就可以省下很多時間了。 ---- ### 想法 核心思路: "通常" 並不是會詢問到每一個人的狀況，並且中途也會加入連線，導致很多改動其實是沒有必要的，現在假設問題以及連線都是隨機分配的狀況。 - 只要標記自己的老大是誰 - 尋找的時候只要找到最終的老大就好 也就是如果兩個人的最終老大同一個，那他們就視為同個幫派 ----  ---- ### 實作 (初始化) 設定自己為一個群組，也就是自己是自己的老大 ```cpp= vector<int> vec(n+1); // 看編號是 0~n-1 or 1~n for(int i = 0 ; i <= n; i++) boss[i] = i; ``` ---- ### 查詢 (找最終老大) ```cpp= int find_root(int x, vector<int> &boss) { // 如果自己的老大是自己，代表自己是最終老大 if (boss[x] == x) return x; int root = find_root(boss[x], boss); //找老大的最終老大 boss[x] = root; // 改自己的老大為最終老大 return root; // 回傳找到的老大 } ``` ---- ### 合併 (兩幫派合併) 合併方式可以自己定義，例如讓 A 幫派合併到 B 幫派 or 反過來 ```cpp= void connect(int A, int B, vector<int> &boss) { int root_A = find_root(A, boss); int root_B = find_root(B, boss); boss[root_A] = root_B; // 把A幫派的老大設為B幫派的老大 return; } ``` ---- ### 主函式(初始化) ```cpp= int main(void){ int n, a, b; cin >> n; //有n個成員 vector<int> boss(n+1); for (int i = 0 ; i <= n ; i++) boss[i] = i; //初始化 } ``` ---- ### 連接和詢問 ```cpp= string qus; // 連接 or 問問題 while (cin >> qus) { cin >> a >> b; if (qus == "connect") { //連接ab connect(a, b, boss); } else if (find_root(a, boss) == find_root(b, boss)) { //判斷ab是否相通 cout << "a and b connect" << '\n'; } else { cout << "a and b not conncect" << '\n'; } } ``` ---- ### 時間複雜度 注意我寫的版本已經是有所謂的路徑優化，但並沒有啟發式合併，也就是連結時誰要讓誰是老大，優化情況下會是選擇人多的為老大。 - 只使用路徑優化的最糟糕情況 $O(M * log n)$ - 或者更精確來說 $\Omega(mlog_{1+\frac{n}{m}}n)。$ - 加上啟發式合併 $\Theta(M*\alpha(n))$ (正常情況下 $\alpha(n)\leq 4$) ---- ### 題外話 使用路徑優化就是在 find_root 時所有路過節點都會設 boss\[x] = root。 請注意如果你學到可持久化並查集，或者線段樹分治+DSU，就不會使用路徑優化，一般會使用啟發式合併。 在正常 DSU 中，已經有論文說明不使用啟發式合併最糟糕也是 $O(M logn)$ 足夠應付題目了，除非真的有人刻意去出這種測資。 另外複雜度的 $\alpha(n)$ 叫做反阿克曼函數，有興趣可以自己查詢。 --- ## Dynamic Programming 動態規劃是一種通過把原問題分解為簡單的子問題來求解最終問題的方法，他並不是某種具體的算法，而是一種解決特定問題的方法，種類也更為繁雜，另外動態規劃也可以視為一種求解最佳化的方法。 (和分治法最不同的地方為，大致上子問題是 dependent，而分治為 independent) ---- ### 基本思維 - 定義子問題。 - 找出問題與子問題之間的(遞迴)關係。 - 找出子問題的計算順序來避免以遞迴的方式進行計算。 - 存取已知子問題答案，用空間換取時間 ---- ### 例子 費波那契數 費波那契數 定義為: $F_{0}=0$ $F_{1}=1$ ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}（n≧2）$ ---- 根據之前的練習，會寫出這樣的函式 ```cpp= int f(int n){ if(n == 0) return 0; if(n == 1) return 1; return f(n-1) + f(n-2); } ``` ---- ### 分析 再根據演算法複雜度練習題，複雜度為 $O(2^n)$ 實際上，會發現其中重複算了很多同樣的數字，所以如果能記錄下來的話，就可以避免重複運算 ---- ### 改進 ```cpp= int dp[10000]; // 假設已經設好 dp[0] = 0, dp[1] = 1; int f(int n) { if (n == 0 || dp[n] != 0) return dp[n]; int ans = f(n-1)+f(n-2); dp[n] = ans; // 重點 return f(n-1) + f(n-2); } ``` ---- ### 時間複雜度 會發現，如果算 f(n) 會避免掉重複運算，一樣會跑到 n = 0, 1 才會回傳，所以跑了 n~0 也就是時間複雜度為 O(n) ---- ### 改進II 其實也不需要用遞迴的方式解，可以直接從頭開始列表出來 ```cpp= int main(void) { int n; cin >> n; int dp[n+1] = {0}; dp[0] = 0, dp[1] = 1; for (int i = 2 ; i <= n ; i++) { dp[i] = dp[i-1] + dp[i-2]; } } ``` ---- ### 時間複雜度 很明顯跑了一個長度為 n 的迴圈，所以時間複雜度為 O(n) ---- ### Bottom up / Top down - top-down : 程式碼中採用遞迴結構計算，從大問題往小問題遞迴(因此小問題先被解決)。這個實作方式的好處為只計算必要的問題，以及不必煩惱計算優先順序。 - 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 ---- ### 動態規劃適用於 - 最優子結構 - 無後效性 - 子問題重疊/相關 ---- ### 最優子結構 (也可能適用於貪心解) 在貪心已經有提過，這邊講解一下流程 1. 證明最優解的第一個組成部分是做出一個選擇 2. 給定最優解的選擇後，確定產生哪些子問題 (規劃空間) 3. 證明組成源問題的最優解組成部分，每個子問題就是本身的最優解。 (使用反證) ---- ### 無後效性 求解的子問題，不會受到後續決策影響。 ---- ### 子問題重疊 如果有大量重複子問題，可以利用空間把解存下來，避免重複求解。 ---- ### 複雜度分析 一個 DP 如果狀態有 $O(n^x)$ 而轉移式涉及 $O(n^y)$ 個狀態，一般可稱為 xDyD 的 DP - 簡單的時間複雜度 : 狀態數\*轉移複雜度 = $O(n^{x+y})$ - 難的時間複雜度 : 根據每個人會有不同的實作方式去計算 - 狀態數 : 計算最終答案總共需要用到的子問題數量 - 轉移複雜度 : 計算任一個子問題的複雜度 - 空間複雜度 : 很直觀根據你開了多少來確定，應該不用太多描述。 ---- ### 成為通靈大師 (DP轉移式) 或稱遞迴轉移式，也有人稱狀態轉移。 子問題可以看成一個狀態，目前的狀態是根據之前的那些狀態轉移，設計 DP 時，最重要的就是找出狀態轉移。 ---- 以費波那契數來看 : $\begin{cases} f(n) = f(n-1) + f(n-2) \space | \space \forall n \in \mathbb{N}, \space n\geq 2\\ f(0) = 0\\ f(1) = 1\\ \end{cases}$ 可以看出每一個狀態是經由前兩個狀態轉移而來  ---- ### DP 的生命就是轉移式 - 清楚且完整的表達DP的關係 - 從轉移式中可以看出遞迴計算大問題所需要的子狀態與計算方式 - 大多DP可以從轉移式看出總狀態數與轉移複雜度(推複雜度) - 列出轉移式後，照著打就可以輕鬆的寫出DP的程式了 - 容易推導dp優化 - 然後你就成為通靈大師了 ---- ## 例子: 爬樓梯問題 題目: 兔子在爬樓梯的時候，可以選擇一次跳三格樓梯，或者一次跳一格樓梯，兔子從 0 階層 (平地) 開始爬，求爬到第 n 格的方法數。 ---- ### 思路 1. 找到第一組成部分也就是第 0 階方法數為 1 2. 第 n 階可以跳到 n + 3 和 n + 1，就可以轉移過去 3. 所以得到轉移式，定義 i 是台階，j 是跳的第幾次 $$ f(i, j) = f(i-1, j-1) + f(i-3, j-1)\\ $$ 4. 初始化 f(0, 0) = 1; ---- ### Botton-up $$ f(i, j) = f(i-1, j-1) + f(i-3, j-1)\\ $$ 逆推回去，不用管是第幾次跳過來，很像費式數列 ```cpp= int dp[n+1] = {0}; // 全部預設 0 dp[0] = 1; // 初始化定義 for (int i = 0 ; i < n ; i++) { dp[i+1] += dp[i]; if (i + 3 <= n) dp[i+3] += dp[i]; } ``` ---- ### 實作建議 - 雖然都說直接用 vector 比較好，但對於 dp 來說比較不會改動(動態拓展)，排序之類的，所以創建 dp 可以直接用陣列比較方便。 - 在推導的時候，可以用類似句子來想 "定義 F(n) 是第 n 項的最佳解" "定義 F(i, j)是從 i ~ j 的最佳解" \... 之類的。 - 建立 dp 的時候，轉移式有可能導致 index 跑到負數，所以要注意從哪個 index 開始例如 0 or 1 開始 --- ## DP 經典例子 - LCS - LIS - 0/1背包問題 - 計數問題 (巴斯卡三角形) ---- ## 經典例子: LCS (最長公共子序列) 題目: 給定兩個字串 $S_1$ 和 $S_2$，求出兩個字串的最長公共子序列。 ex: abdeabc azedeacbaa 最長公共子序列 = adeab 長度為 5 ---- ### 思路 - 定義 DP(i,j) 是 $S_1$ 取前 i 個字元，$S_2$ 取前 j 個字元的最佳解 - 轉移式??? - 初始化 DP(i,0) = 0，DP(0,j)，因為什麼字元都沒有 ---- ### 轉移式推導 假設 $S_1$ 和 $S_2$ 的最後一個元素分別以 $e_1$ 與 $e_2$表示，剩餘部分以 $d_1$ 與 $d_2$ 表示，故可以將序列 S1 與 S2 表示如下： $S_1=d_1+e_1$ $S_2=d_2+e_2$ 接下來就可以分三個討論，並且定義 S 為 DP(i, j) 的答案字串 ---- ### 情況一 如果 S 中沒有包含 $e_1$ 也不包含 $e_2$，所以這樣 S 不會受到 $e_1, e_2$ 影響 - $DP(i, j) = DP(i-1, j-1)$ ---- ### 情況二 如果 S 中有包含 $e_1$ 但不包含 $e_2$，所以這樣 S 不會受到 $e_2$ 影響 - $DP(i, j) = DP(i, j-1)$ 反之，如果包含 $e_2$ 但不包含 $e_1$ - $DP(i,j) = DP(i-1, j)$ ---- ### 情況三 如果 S 中包含 $e_1$ 和 $e_2$，代表這個值是需要的，會被納進來答案裡面，也可以推論出他們是目前尾巴加進來的。 - $DP(i,j) = DP(i-1, j-1) + 1$ ---- ### 推論 所以推論出，只有 S 中包含 $e_1$ 和 $e_2$，才會影響到現在答案，而 S 要包含 $e_1, e_2$ 也就是當 $e_1 = e_2$ 的時候，所以可以寫出以下轉移式 $\begin{cases} DP(i,j) = DP(i-1, j-1) + 1 \space , \space if \space e_1[i] == e_2[j]\\ DP(i,j) = max(DP(i-1, j), DP(i, j-1), DP(i-1, j-1)) \space , \space Others\\ DP(i,0) = 0 ,\space DP(0, j) = 0 \space , \space initialize\\ \end{cases}$ ---- ### 推論 劃減一下，並且 $e_1[i]$ 其實就是 $S_1[i]$ ，$e_2[j]$ 是 $S_2[j]$，推導一下，發現根本不需要 max 到 DP(i-1, j-1) 這一項 $\begin{cases} DP(i,j) = DP(i-1, j-1) + 1 \space , \space if \space S_1[i] == S_2[j]\\ DP(i,j) = max(DP(i-1, j), DP(i, j-1)) \space , \space Others\\ DP(i,0) = 0 ,\space DP(0, j) = 0 \space , \space initialize\\ \end{cases}$ ---- 轉移式有 i-1 j-1 所以讓 index 從 1 開始可以避免掉 index = -1 的問題 ### 實作 複雜度: $O(nm)$ ```cpp= int LCS (string S1, string S2) { int n = S1.length(), m = S2.length(); int dp[n+1][m+1] = {0}; for (int i = 1 ; i <= n ; i++) dp[i][0] = 0; for (int j = 1 ; j <= m ; j++) dp[0][j] = 0; for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= m ; j++) { if (S1[i-1] == S2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } return dp[n][m]; } ``` ---- ## 經典例子: LIS (最長遞增子序列) 題目: 在一個序列 S 中，找到最長(嚴格)遞增的子序列。 ex: 1 5 6 2 1 7 9 最長遞增子序列 = 1 5 6 7 9 長度為 5 ---- ### 思路 會發現有許多遞增子序列都是符合要求的子序列，因此解法只需要記錄在每個長度下最長的遞增子序列長度。 - 定義 DP(i) 是答案有 S\[i] 的最長遞增子序列，也就是要考慮S\[i]進來 - 轉移式??? - 初始化 DP(i) = 1 假設一開始最長只有自己 ---- ### 轉移式 既然要考慮 S 結尾為 S\[i] 的最長遞增子序列，所以如果有比前面第 j 個數字大的話，那就可以考慮放在 j 後面也就是 DP(j) + 1，繼續比，就只需要找最大值就好，得到 $DP(i) = max(DP(i), DP(j) + 1) \space | \space if \space S[i] > S[j]$ ---- ### 實作 LIS 複雜度 $O(n^2)$ ```cpp= int LIS (vector<int> &vec) { int ans = 0, n = vec.size(); int dp[n] = {0}; // 建議還是先設全部為 0 for (int i = 0 ; i < n ; i++) dp[i] = 1; //LIS for (int i = 0 ; i < n ; i++) { for (int j = 0 ; j < i ; j++) { if (vec[i] >= vec[j]) dp[i] = max(dp[i], dp[j] + 1); } ans = max(ans, dp[i]); } return ans; } ``` ---- ### 優化 之後提到單調對列優化後，就可以得到 $O(nlogn) 的解$ ---- ### 注意 - LCS LIS 這邊只有回傳最大值而已，如果要輸出解(所有解)的話，可以自己嘗試看看，用 backtracking 的方式 - 注意 DP 要不要從 0 開始數。 ---- ## 經典例子: 背包問題 (01背包) 問題: 有 n 個物品儘量塞進背包裡面，想要背包裡面的物品總價值最高。背包有重量限制，如果物品太重，就會撐破背包，求最大價值。 :handbag: ---- ### 背包問題 廣為人知的背包問題，是一種 NPC 問題，其有許多變形，先介紹最經典的 \[ 0/1 背包問題 ] 「 0/1 」的意思是：每種物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。 看到這種問題若沒學過直覺通常會是貪心，不管是貪心他的價值或是貪心他的CP值也好，在這種題目下面都是錯的。 0/1 背包問題的關鍵點，在於如何有效利用背包的剩餘重量，找出最好的物品組合方式。 ---- ### 思路 - 定義 DP(i,j) 為背包重量為 i 時，裝下第 j 個物品後的最大價值 - 轉移式?? - 初始化: DP(i, 0) = 0, DP(0, j) = 0 ---- ### 轉移式 不難看出，兩種情況 1. 裝的下 j 物品: 價值 v\[j] + 剩下重量 i - w(j) + 沒有裝 j 物品的最大值 或者是乾脆不裝 j，取 j-1 物品的最大價值 2. 裝不下 j 物品，那就是只有只有裝 j-1 物品的最大價值 $DP(i, j) = max(DP(i, j-1), DP(i - w(j),\space j-1) + v[j])) \space ,\space if \space i \geq w[j]$ $DP(i, j) = DP(i, j-1) \space ,\space if \space i < w[j]$ ---- ### 實作 (Top-down) ```cpp= int solve() { int n, k; // 寶物數量 n， 背包承受重量 k cin >> n >> k; vector<pair<int,int>> box(n+1); //定義first為重量，second為價值 for (int i = 1 ; i <= n ; i++) cin >> box[i].first; for (int i = 1 ; i <= n ; i++) cin >> box[i].second; // 假設題目最大只有 1000 重量 1000物品 int dp[1000][1000] = {0}; for (int j = 1 ; j <= n ; j++){ //每個寶物 for (int i = 0 ; i < box[j].first ; i++) dp[i][j] = dp[i][j-1]; for (int i = box[j].first ; i <= k ; i++) //背包重量 dp[i][j] = max(dp[i][j-1],dp[i-box[j].first][j-1]+box[j].second); } return dp[k][n]; } ``` ---- ### 空間有點小 會發現，因為陣列最多可以開到 $10^7$ 如果放二維陣列的話大概只能放 $10^3$，這樣有點少，所以來想如何優化空間。 想一下，不開二維陣列存取的話，這樣只能放重量，不能放物品，那這樣的話會根據轉移式有個問題，迴圈是從重量輕往重的跑，那如果當背包承受很重為 W，裝了 j 物品後會剩下 W-j 但根本不知道 DP(W-j) 有沒有裝過 j 物品了!! 轉念一想，那是不是直接讓迴圈從背包承重 "重往輕" 的跑，就不會遇到這問題了! ---- ### Botton-up ```cpp= int dp[100005] = {0}; for (int j = 1 ; j <= n ; j++) //每個寶物 for (int i = k ; i >= box[j].first ; i--) //背包重量 dp[i] = max(dp[i],dp[i-box[j].first]+box[j].second); return dp[k]; ``` ---- ### 題外話 - 或者也可以發現，狀態只需要考慮兩種(這一次跟上一次)，可以用 0 1 交替，這樣就可以建立 dp\[n]\[2] 來存 - 背包問題還有很多變形，會比較困難，所以有機會再來講。 ---- ## 經典計數問題: (二項式定理) - 或者說帕斯卡三角形  ---- ### 帕斯卡三角形 - 初始化最頂端為 1，DP(1,1) = 1 - 轉移式 $\begin{cases} DP(i,j) = DP(i-1, j) + DP(i-1, j-1)\space, \space if \space i \neq 0 \space or \space i \neq j\\ DP(i,j) = 1 \space, \space if \space i = 1 \space or \space i = j\\ \end{cases}$ 這樣就可以推導出 C n 取 m 的值了。 (簡單的轉移式不需要在實作了吧!) ---- ## 結尾 DP 的想法有時會有點神奇，類型也非常非常多種，請不要害怕他，很多時候還是有跡可循的!，可以先按照基本步驟來想，大事化小，小事化無，把題目的問題慢慢拆解成小問題，想辦法去定義 DP，就能夠把關係式解出來的，而且我也相信數學系的各位們肯定都喜歡自己推導 DP 轉移式的 !! 另外目前只討論一些簡單的DP，接下來還有機會講到比較進階的DP，以及一些優化DP的方式。 --- ## 數論 - 快速冪 - 模運算 - 費馬小定理 - 應用 - 矩陣快速冪 https://hackmd.io/@HIPP0/B1Of0lP5s