分治法與動態規劃

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)\)