# 111 選手班 - 動態規劃
###### tags: `宜中資訊` `CP`
2022.08.16

[110 slides](https://hackmd.io/@Ccucumber12/Bk6lLyuxF#/)

[背包九講](http://www2.lssh.tp.edu.tw/~hlf/class-1/lang-c/DP.pdf)

## 簡介
Dynamic Programming 動態規劃
- 把大問題分成小問題
- 記錄小問題的答案避免重複計算
- 以空間換取時間

### 三步驟求DP
#### 狀態
- 可以怎麼拆解問題？
- 有哪些資訊是必要的？
- 可以從狀態中求出答案嗎？
- 狀態大小

#### 轉移
- 如何獲得狀態答案？
- 該用甚麼順序計算？
- 轉移耗時

#### 初始
- 有哪些已知的答案？

### 計算方式
#### Top Down
透過遞迴分割問題，並將答案記錄起來。
如果遞迴到計算過的狀態，則直接回傳。
類似DFS
- 直覺簡單
- 不須煩惱計算順序
- 效率差 可能stack overflow

#### Bottom Up
透過迴圈，從初始狀態開始，將所有答案計算出來
- 效率高
- 常見(?
- 可能計算非必要狀態
- 反直覺 需考慮順序

## 基礎問題
### 合併史萊姆
有 $N$ 個史萊姆，第 $i$ 個大小為 $a_i$。
每次可以花費 $a_i + a_{i+1}$ 合併兩個相鄰的史萊姆，之後他們會合併成一個大小為兩個之和的史萊姆。
請問最小要花費多少才能將所有史萊姆合併成為一個。

- 狀態：$f(l, r) =$ 將 $l$ 到 $r$ 合併為一個史萊姆的花費
- 轉移：
- 切在 $l$：$f(l, l) + f(l+1, r)$
- 切在 $l+1$：$f(l, l+1) + f(l+2, r)$
- ...
- $f(l, r) = \displaystyle\min_{l \le i \le r} \{f(l, i) + f(i+1, r)\}$

時間複雜度
- 狀態：$\mathcal O(N^2)$
- 轉移：$\mathcal O(N)$
- 總計：$\mathcal O(N^3)$

### LCS
Longest Common Subsequence 最長共同子序列
給定兩個字串 $s, t$，請找到一個最長的字串使的它是 $s$ 和 $t$ 的共同子序列。

- 狀態：$f(i, j) =$ $s[1,i]$ 和 $t[1,j]$ 的 LCS
- 轉移
- $s[i] = t[j]$：$f(i-1, j-1) + 1$
- 不選：$\max\{f(i-1, j), f(i, j-1)\}$

時間複雜度
- 狀態：$O(N^2)$
- 轉移：$O(1)$
- 總計：$O(N^2)$

### LIS
Longest Increasing Subsequence 最長遞增子序列
給定一個序列，請找到一個最長的子序列使得它是遞增的
- 狀態：$f(i) =$ 選 $a[i]$ 下，$a[1,i]$ 的LIS
- 轉移：
- 限制：前一個選的數字要 $\le a[i]$
- $dp[i] = \displaystyle\max_{j<i \& a[j] < a[i]}(dp[j]) + 1$

時間複雜度
- 狀態：$\mathcal O(N)$
- 轉移：$\mathcal O(N)$
- 總計：$\mathcal O(N^2)$

#### 二分搜優化
- 若 $a[i] \le a[j]$ 且 $dp[i] \ge dp[j]$ 則 $a[j]$ 永遠不會被選到
- 紀錄所有可能會用到的 $(a[i], dp[i])$
- $dp[i]$ 恰巧會是每格 $+1$
- 只記錄 $(a[i])$
- 此時紀錄的 $a[i]$ 會是嚴格遞增
- 二分搜！

時間複雜度
- 狀態：$\mathcal O(N)$
- 轉移：$\mathcal O(\log N)$
- 總計：$\mathcal O(N\log N)$

#### 用 LIS 做 LCS
記錄每個字元在其中一個字串的位置，並尋找另外一個字串的LIS

## 背包問題
### 01 背包 價值好高
[例題一](https://atcoder.jp/contests/dp/tasks/dp_d)
- 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$
- 背包容量 $W$
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N \leq 100$，$W \leq 10^5$

**每個物品**
- 0: 不選，重量$+0$，價值$+0$
- 1: 選擇，容量$-w_i$，價值$+v_i$

**DP**
- $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。
- 考慮第 $i$ 個物品
- 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$
- 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_i]+v_i$
- Ans: $\text{dp}[N][W]$

**時間複雜度**
- Time: $\mathcal{O}(NW)$
- Space: $\mathcal{O}(NW)$

### 01 背包 重量好大
[例題二](https://atcoder.jp/contests/dp/tasks/dp_e)
- 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$
- 背包容量 $W$
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N \leq 100，W \leq 10^9，\sum v_i \leq 10^5$

**DP**
- $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，價值總合為 $j$ 的最小重量總和。
- 考慮第 $i$ 個物品
- 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$
- 1: $\text{dp}[i][j] = \text{dp}[i-1][j-v_i]+w_i$

**答案**
- 對於所有 $\text{dp}[i][j] \leq W$
- Max $j$

**初始化**
- $\text{dp}[i][0] = 0$
- $\text{dp}[i][j] = \inf, (j > 0)$

**時間複雜度**
- Time: $\mathcal{O}(N\sum v_i)$
- Space: $\mathcal{O}(N\sum v_i)$

### 無限背包
- 給定 $N$ 種物品，第 $i$ 種物品重量$w_i$，價值$v_i$
- 背包容量 $W$
- 選擇任意數量物品，每種不限個數，使得重量總和不超過容量，請問最大價值總和為何？
- $N \leq 100，W \leq 10^5$

**DP與轉移式**
- $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。
- 考慮第 $i$ 個物品
- 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$
- 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_i]+v_i$
- 2: $\text{dp}[i][j] = \text{dp}[i-1][j-2w_i]+2v_i$
- 3: $\text{dp}[i][j] = \text{dp}[i-1][j-3w_i]+3v_i$
- $\dots$
- 時間複雜度：$\mathcal O(NW)\times\mathcal O(W)$

**01與無限的差別**
- $\text{dp}[i][j] = \text{dp}[i-1][j - w_i] + v_i$
- 每項物品只能選一次
- 01背包
- $\text{dp}[i][j] = \text{dp}[i][j - w_i] + v_i$
- 每項物品選完之後還能選
- 無限背包

**優化**
- $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。
- 考慮第 $i$ 個物品
- 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$
- 1: $\text{dp}[i][j] = \text{dp}[i][j-w_i]+v_i$
- 複雜度
- 時間: $\mathcal{O}(NW)$
- 空間: $\mathcal{O}(NW)$

### 分組背包
- 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$，屬於組別 $k_i$
- 背包容量 $W$，物品共分為 $K$ 組
- 每組最多選擇一件物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N,K \leq 100$，$W \leq 10^5$

**DP**
- $\text{dp}[i][j]:=$只能選前 $i$ **組**物品的情況下，背包容量為 $j$ 的最大價值總和。
- 考慮第 $i$ **組**物品
- 考慮第 $i$ 組物品內，第 $u$ 個物品
- 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$
- 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_u]+v_u$
- Ans: $\text{dp}[K][W]$

**複雜度**
時間: $\mathcal{O}(NW)$
空間: $\mathcal{O}(NW)$

## 題單
- [Contest](https://vjudge.net/contest/510748#overview)
- Password: `111apcs`