---
tags: CRC
---

# 分治法與動態規劃
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)$