# 分治法與動態規劃 WiwiHo --- https://hackmd.io/@wiwiho/crc1082algo https://tg.pe/xgaG  --- # 分治法 Divide and Conquer ---- 把一個問題分成多個部分 對每個部分分別求解後 再求出全部的解 ---- ## 範例 - 合併排序 - 快速排序 --- ## 逆序數對 ----  ---- 先將數列砍成兩半 求在兩邊的逆序數對 順便把兩邊由大到小排序好 再求跨越兩邊的 ---- ### 求兩邊的逆序數對 遞迴處理 ---- ### 求跨越兩邊的逆序數對 如果兩邊都先排序好了 在同一邊的東西的相對位置可能改變 但在不同邊的不變 ----  Note: 畫圖 --- # 前綴和與差分 --- ## 前綴和 ---- $S_i=\sum_{k=1}^i a_k$ 並且令 $S_0=0$ ---- $\sum_{k=l}^r a_k=\sum_{k=1}^r a_k - \sum_{k=1}^{l-1} a_k=S_r-S_{l-1}$ --- ## 差分 ---- $D_i=a_i-a_{i-1}$ 並且令 $a_0=0$ ---- ### 性質 - $\sum_{k=1}^i D_k = a_i$ - $\sum_{k=l}^r D_k = a_r - a_{l-1}$ ----  ---- 將 $a_l,a_{l+1},...,a_r$ 加上 $v$ $D$ 的變化： - $D_l$ 加上 $v$ - $D_{r+1}$ 減少 $v$ $\Rightarrow$ 變成單點修改 --- # 動態規劃 Dynamic Programming --- ## DP 的原則 ----  ---- 遞迴？ ----  ---- 有好多子問題是重複的 ---- ### 解決方法 把已經算過的存下來 ---- ### DP 的特性 - 重複子問題 - 最佳子結構 - 無後效性 Note: - 重複子問題：同樣的子問題會被多次查詢。 - 最佳子結構：問題被拆成子問題後，可以用子問題的最佳解拼回該問題最佳解，有點 Greedy 的概念。 - 無後效性：子問題不會互相呼叫，也就是說，你不會一直呼叫呼叫呼叫然後回到原點，所以你可以找到一個正確的算出子問題答案的順序。 ---- ### 狀態 例如費氏數列的 $f(1)$、$f(2)$、$f(3)$…… 這些存下來的東西稱為狀態 ---- ### DP 的步驟 1. 設置狀態 2. 導出轉移式 3. 設置初始狀態 ---- ### bottom-up vs. top-down - 分治：用遞迴 - top-down：用遞迴 - bottom-up：用迴圈 ---- top-down 用在狀態數多但很多沒有用的狀況 但遞迴的常數大 所以幾乎所有狀態都有用時 用 bottom-up 比較好 ----  ---- ### 設置狀態 $dp[i][j]=$ 第 $i$ 天做活動 $j$ 時最少要休息幾天 - $j=0$：休息 - $j=1$：運動 - $j=2$：寫程式 ---- ### 狀態轉移 如果第 $i$ 天不能做活動 $j$ 則 $dp[i][j]=\infty$，否則 - $dp[i][0]=\min\{dp[i-1][0], dp[i-1][1], dp[i-1][2]\} + 1$ - $dp[i][1]=\min\{dp[i-1][0], dp[i-1][2]\}$ - $dp[i][2]=\min\{dp[i-1][0], dp[i-1][1]\}$ ---- ### 初始狀態 $dp[0][0] = 0$ ---- ### 轉移順序 按 $n$ 從小到大計算 ---- ### 答案 $\min\{dp[n][0],dp[n][1],dp[n][2]\}$ ---- ### 時間複雜度 狀態數 $\times$ 轉移複雜度 $O(n) \times O(1)=O(n)$ --- ## 區間 DP ----  ---- ### 設置狀態 $dp[l][r]=$ 將第 $l$ 隻到第 $r$ 隻史萊姆 合併成一隻需要的最少成本 ---- 第 $l$ 隻到第 $r$ 隻史萊姆合起來的大小 $\sum_{k=l}^r a_k$ 記作 $s[l][r]$ ---- ### 狀態轉移 $dp[l][r]=\min\{dp[l][k] + dp[k+1][r] + s[l][k] + s[k+1][r] | l \leq k < r\}$ ---- ### 轉移順序 從 $r-l$ 小的做到大的 ---- ### 初始狀態 $dp[i][i]=0$ ---- ### 答案 $dp[1][n]$ ---- ### 時間複雜度 轉移：$O(n)$ 狀態數：$O(n^2)$ $\Rightarrow O(n^3)$ --- ## 背包問題 --- ## 0/1 背包問題 ----  ---- ### 設置狀態 $dp[i][j]$ 是將前 $i$ 種物品中的一些放進背包 且總體積**不超過** $j$ 時的最大總價值 ---- ### 狀態轉移 前 $i$ 種物品中的一些放入背包 等同於將前 $i-1$ 種物品中的一些放入背包 再放入或不放入第 $i$ 種物品 $dp[i][j]=\begin{cases} \max(dp[i-1][j-w_i] + v_i, dp[i-1][j]), & \quad \text{if }j \geq w_i \\ dp[i-1][j], & \quad \text{otherwise} \end{cases}$ ---- ### 初始狀態 $dp[0][j]=0$ ---- ### 轉移順序 $i$ 由小到大、$j$ 由小到大 ---- ### 時間複雜度 轉移：$O(1)$ 狀態數：$O(nm)$ $\Rightarrow O(nm)$ ---- ### 空間複雜度 等等講 --- ### 無限背包問題 ----  ---- ### 設置狀態和初始狀態 和 0/1 背包一樣 ---- ### 狀態轉移 改一下轉移式？ ---- #### 想法 1 將前 $i$ 種物品中的一些放入背包 等同於將前 $i-1$ 種物品中的一些放入背包 再不放入或放入若干個第 $i$ 種物品 $dp[i][j]=\max\{dp[i-1][j-kw_i]+kv_i | 0 \leq j-kw_i, k \in \mathbb{N}_0\}$ ---- 轉移複雜度：$O(m)$ 有點太大 ---- #### 想法 2 也可以說成是 「將前 $i-1$ 種物品中的一些放入背包 再放入一個第 $i$ 種物品」 或「將前 $i$ 種物品中的一些放入背包 再放入一個第 $i$ 種物品」 $dp[i][j]=\begin{cases} \max(dp[i-1][j-w_i]+v_i, dp[i][j-w_i]+v_i, dp[i-1][j]), & \quad \text{if } j \geq w_i\\ dp[i-1][j], & \quad \text{otherwise} \end{cases}$ ---- 由於 $dp[i][j-w_i] \geq dp[i-1][j-w_i]$ $dp[i][j]=\begin{cases} \max(dp[i][j-w_i]+v_i, dp[i-1][j]), & \quad \text{if } j \geq w_i\\ dp[i-1][j], & \quad \text{otherwise} \end{cases}$ ---- 轉移複雜度：$O(1)$ --- ## 有限背包問題 ----  ---- ### 方法 1 把同一種的 $c_i$ 個物品 視為 $c_i$ 種只有一個的物品 然後用 0/1 背包做 物品數：$\sum c_i$ 時間複雜度：$O(m\sum c_i) \geq O(nm)$ ---- ### 方法 2 把同一種的 $c_i$ 種物品分成 $O(\log c_i)$ 種 總數要是 $c_i$ ---- 分法： 找到最大的 $x$ 滿足 $2^x-1 \leq c_i$ 分成數量分別是 $1,2,4,...,2^{x-1}$ 的 $x$ 種 總數是 $2^x-1$ 再有一種的數量是 $c_i-(2^x-1)$ ---- $1,2,4,...,2^x$ 可以湊出 $[0,2^x-1]$ 的所有數字 加上 $c_i-(2^x-1)$ 可以湊出 $[c_i-(2^x-1), c_i]$ 的所有數字 聯集：$[0,c_i]$ ---- 分割後 把同一種的物品壓成只有一個 用 0/1 背包做 物品種數：$O(\sum \log c_i)$ 時間複雜度：$O(m \sum \log c_i)$ --- ## 背包問題的變形 ---- ### 各種問題描述 - 有各種不同面額的鈔票（面額可能互不為因倍數），求最少用幾張鈔票可以湊出指定的價錢。 - 有一個數列，求能否從這個數列中拿出一些數字，使得總和為某個指定的數。 - 給一個數字 $n$，求有幾種正整數的組合（同樣數字可重複，但順序不同的也視為相同組合）的和為 $n$。 ---- ### 各種變化 - 總體積是某個數有幾種放法。 - 能不能湊出某個總體積。 - 最少用幾個東西能湊出某個總體積。 --- ## 滾動陣列 ---- 背包問題的空間複雜度都和狀態數相同 ---- ### e.g. 0/1 背包 狀態數：$O(nm)$ ---- 但是看看轉移式 $dp[i][j]=\begin{cases} \max(dp[i-1][j-w_i] + v_i, dp[i-1][j]), & \quad \text{if }j \geq w_i \\ dp[i-1][j], & \quad \text{otherwise} \end{cases}$ ---- 算 $dp[i][j]$ 只會用到 $dp[i-1][...]$ $\Rightarrow$ 有些狀態過一陣子就沒用了 ---- ### 解決方法 把不用的狀態丟掉 $\Rightarrow$ 滾動陣列 ---- 把 $dp$ 看成二維表格 在計算某一列時只會用到它的上一列 所以從第一列做到最後一列 算完某一列後就可以把上一列丟掉 --- ### 位元 DP ----  ---- $dp[s]=$ 集合 $s$ 是否滿足條件 $dp[s]=\max\{dp[s-S_i] | S_i \subset s\}$ $dp[0]=1$ ---- 時間複雜度： $$O(m2^n)$