# 分治法與動態規劃
WiwiHo
---
https://hackmd.io/@wiwiho/crc1082algo
https://tg.pe/xgaG
![](https://i.imgur.com/KqGWkCw.png)
---
# 分治法
Divide and Conquer
----
把一個問題分成多個部分
對每個部分分別求解後
再求出全部的解
----
## 範例
- 合併排序
- 快速排序
---
## 逆序數對
----
![](https://i.imgur.com/RPpw4Ms.png)
----
先將數列砍成兩半
求在兩邊的逆序數對
順便把兩邊由大到小排序好
再求跨越兩邊的
----
### 求兩邊的逆序數對
遞迴處理
----
### 求跨越兩邊的逆序數對
如果兩邊都先排序好了
在同一邊的東西的相對位置可能改變
但在不同邊的不變
----
![](https://i.imgur.com/tRigtvS.png =500x)
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}$
----
![](https://i.imgur.com/FXO7rJ8.png)
----
將 $a_l,a_{l+1},...,a_r$ 加上 $v$
$D$ 的變化:
- $D_l$ 加上 $v$
- $D_{r+1}$ 減少 $v$
$\Rightarrow$ 變成單點修改
---
# 動態規劃
Dynamic Programming
---
## DP 的原則
----
![](https://i.imgur.com/fA2IIUC.png)
----
遞迴?
----
![](https://i.imgur.com/S6sn7DA.png)
----
有好多子問題是重複的
----
### 解決方法
把已經算過的存下來
----
### 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 比較好
----
![](https://i.imgur.com/3BoAw51.png)
----
### 設置狀態
$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
----
![](https://i.imgur.com/NiKDIQF.png)
----
### 設置狀態
$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 背包問題
----
![](https://i.imgur.com/i51eGr1.png)
----
### 設置狀態
$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)$
----
### 空間複雜度
等等講
---
### 無限背包問題
----
![](https://i.imgur.com/V9IHKXI.png)
----
### 設置狀態和初始狀態
和 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)$
---
## 有限背包問題
----
![](https://i.imgur.com/9vhhFaG.png)
----
### 方法 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
----
![](https://i.imgur.com/2f2u64g.png)
----
$dp[s]=$ 集合 $s$ 是否滿足條件
$dp[s]=\max\{dp[s-S_i] | S_i \subset s\}$
$dp[0]=1$
----
時間複雜度:
$$O(m2^n)$
{"metaMigratedAt":"2023-06-15T09:08:07.779Z","metaMigratedFrom":"YAML","title":"分治法與動態規劃","breaks":"false","contributors":"[{\"id\":\"02353542-5acb-4a66-abd0-128b1af24abb\",\"add\":5351,\"del\":86}]"}