:+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1:
2019 Week 9: Dynamic Programming (動態規劃)
=
[第二週教材](https://hackmd.io/s/r14Do56HN#%E5%88%86%E6%B2%BB%E6%B3%95)中分治法，提到了每個子問題都需**互相獨立**，就是每分割都將產生全新的問題
而本週介紹的動態規劃則適合在大部分的問題**互相重疊**
回憶一下[第二週教材](https://hackmd.io/s/r14Do56HN#%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83)的那段話： "從邊界遞推地紀錄所有問題的解，且一個項用到前一項的最佳結果，就是動態規劃的精神。"
這裡給出正式的定義：
一個問題若能用 Dynamic Programming (以下簡稱 DP) 求解，其該問題含有以下三個性質：
* 最優子結構
問題的**最優解**，是該子問題最優解的合併解。其子問題也具有同樣的特性
* 重複子問題
有很多子問題可歸為**同樣**的問題
* 無後效性
確定的子問題解，並不會受到其他決策影響(還在整個問題的求解過程中)
==DP 不滿足[第一週教材](https://hackmd.io/s/B175UeTrV#%E4%BB%80%E9%BA%BC%E6%98%AF%E6%BC%94%E7%AE%97%E6%B3%95)中提到的演算法三步驟，它僅是個方法==
# DP 入門
考慮一個問題
:::info
要買價值 $15$ 元的商品，有 $10$ 元、$5$ 元、$1$ 元硬幣，要求花**最少**的**硬幣數**。
:::
日常生活中有個**貪心策略**是，每次用額面較大的硬幣去付
這樣就能使用較少的硬幣數，也就是 $\underline{1}\cdot 10 + \underline{1}\cdot 5 + \underline{0}\cdot 1$
:::info
同樣 $15$ 元的商品，若現在硬幣額面只有 $11$ 元、$5$ 元、$1$ 元
:::
顯然上述貪心策略就不是最佳策略了。
設 $f(x)$ 為價值 $x$ 元的商品所需要的最少硬幣數
若第一次：
- 選 $11$ 元則可能 $f(15) = f(4) + 1$
- 選 $5$ 元則可能 $f(15) = f(10) + 1$
- 選 $1$ 元則可能 $f(15) = f(14) + 1$
將問題以 $f$ 形式化後：
$$f(x) = \min\{f(x-11), f(x-5), f(x-1)\} + 1$$
也就是說，求解 $f(x)$ 需要用到 3 個**子問題的解**：
$$f(x-11), f(x-5), f(x-1)$$
以及邊界：
$$f(0) = 0$$
### 最優子結構
$f(x)$ 的定義為湊出 $x$ 元的**最少**硬幣數
最少即 $f(x)$ 的**最優解**，而 $f(x)$ 仰賴 3 個子問題的最優解
### 無後效性
若求出了 $f(4) = 4$，則不管**未來**要求任何 $f(t)$ 的解都**不會改變** $f(4)$ 的解
### 重複子問題
若求 $f(9)$ 則需要先求解 $f(8), f(4)$
$f(4)$ 在之前**可能**已經找到解了，這就是**重複**的子問題
也就是說**無需**再為 $f(9)$ 重新計算 $f(4)$
# 經典 DP 問題
有非常多實用的演算法是使用 DP 方法所設計的，
比起學習這些演算法的實作，更重要的是要學習如何**應用 DP** 去**設計**出演算法
## Fibonacci 數
Fibonacci **數列**由 $0, 1$ 開始，之後的數為前兩項相加得來
也就是 $0,1,1,2,3,5,8,13,21,...$
:::info
求數列第 $n\in \mathbb{N}$ 項的數
:::
考慮用遞迴寫：
```cpp
int solve(int n) {
if (n == 1 || n == 2) return 1;
return solve(n-1) + solve(n-2);
}
```
每個子問題都將分為兩個子問題，複雜度為 $O(2^n)$
而實際上此演算法將**同樣**的子問題計算過兩次以上
例如在 $n = 5$ 時，會重複計算 `solve(3)` 兩次:
```graphviz
digraph {
nodesep=0.4; //was 0.8
ranksep=0.5;
{ node[style="invis", label=""]; x_5; }
{ node[style="invis", label="", width=.1]; x_4; x_3; lx_3}
{ node[style="filled", fillcolor="#FFA500"]; 3; }
{ node[label="3", style="filled", fillcolor="#FFA500"]; l_3; }
{ node[label="2"]; l_2; }
{ node[label="2"]; r_2; }
{ node[label="2"]; ll_2; }
{ node[label="1"]; r_1; }
{ node[label="1"]; l_1; }
{ rank=same; 4; 3; x_5 }
{ rank=same; l_3; l_2; x_4 }
{ rank=same; r_2; r_1; x_3 }
{ rank=same; ll_2; l_1; lx_3 }
5 -> 4
5 -> 3
4 -> l_3
4 -> l_2
3 -> r_2
3 -> r_1
l_3 -> ll_2
l_3 -> l_1
{
edge[style="invis"];
5 -> x_5
4 -> x_5 -> 3
4 -> x_4
l_3 -> x_4 -> l_2
3 -> x_3
r_2 -> x_3 -> r_1
l_3 -> lx_3
ll_2 -> lx_3 -> l_1
}
}
```
### 記憶化 (memoization[^memoization])
也就是說，只要在每次解出子問題後將結果**記錄**，下一次遇到**重複**的子問題就無需計算
複雜度改進為 $O(n)$
- **top-down**
```cpp
int solve(int n) {
if (fib[n]) return fib[n];
return fib[n] = solve(n-1) + solve(n-2);
}
```
由原問題開始遞歸逐步計算子問題的解
優點：不會計算太多子問題
缺點：呼叫函式的成本頗高
- **bottom-up**
```cpp
fib[1] = fib[2] = 1;
for (int i = 3; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];
```
由邊界(最小子問題)逐步計算到原問題的解
優點：若適當的設計迭代順序則能很好的壓縮空間
缺點：**可能**會多計算無用的子問題
#### 練習：
[CODEFORCES 327A Flipping Game](https://codeforces.com/contest/327/problem/A)
[CODEFORCES 1033C Permutation Game](https://codeforces.com/problemset/problem/1033/C)
\* [CODEFORCES 1133E K Balanced Teams](https://codeforces.com/contest/1133/problem/E)
---
在繼續往下讀前，先複習[第四週教材](https://hackmd.io/s/SJ7nxwRL4#%E6%90%9C%E5%B0%8B)中關於搜尋的術語
## 背包問題
:::info
給固定體積的背包，以及各**種**體積及價值不盡相同的物品
在背包容量不超過體積上限的前提，使總價值**最大**。
:::
經典的背包問題有以下幾類:
- 無限背包問題：
對每**種**物品，其個數是**無限**多個
- 01 背包問題：
對每**種**物品，其個數是 $1$ 個
- 多重背包問題：
對每**種**物品，其個數是**有限**多個
先用一個比較生活化的例子來說，假設有一個古代的東方商人想沿著絲路走至西方販賣珍奇古物，但是他當然沒辦法將所有店內的商品帶去，所以為了最大化此趟旅程所能賺到的錢，他必須在他的大後背包內放入總價值最多的商品
>對沒錯，他要用走的
假設他的大背包容量為 $8$ 公升，以下是一些他想帶去販售的商品:
|Index|價值|體積|
|---|---|---|
|1|$10$ 克朗|$2$ L|
|2|$80$ 克朗|$3$ L|
|3|$110$ 克朗|$4$ L|
|4|$150$ 克朗|$5$ L|
|5|$200$ 克朗|$6$ L|
以商品都能賣出去為前提，請問該怎麼帶才能最大化收益呢？
在進入正題前，讀者可以先思考一下這個看起來似乎蠻簡單的問題
要使得總價值最大不就是先算好各物品的 C/P 值，然後從最高的開始挑起嗎？
這樣做會發生什麼事？ 最佳解又是多少？
==背包問題的術語約定：==
- $P_i$ 代表第 $i$ 件物品的價值
- $V_i$ 代表第 $i$ 件物品的體積
## 01 背包問題
例如：
|價值|體積|
|---|---|
|$70$ 克朗|$2$ L|
|$80$ 克朗|$4$ L|
假設剩下 $4$ L 的體積，無限背包問題中會選兩個 $2$ L 的商品；
但在 01 背包問題中，只能選擇 $4$ L 的商品
先設計出狀態的定義，以及狀態轉移方程：
**狀態** $S(i, n)$ 表示**只**考慮 $1$ 到 $i$ 項物品，背包體積為 $n$ 時的最大價值。
這個最大值，是下列兩項其中之一
- 包含第 $i$ 個物品： $S(i-1, n - V_i) + P_i$
- 不包含第 $i$ 個物品： $S(i-1, n)$
也就是**狀態轉移**方程：
$$ S(i, n) = \max(S(i-1, n - V_i) + P_i, S(i-1, n))$$
而當背包體積小於 $V_i$ 時，
$$S(i, n) = S(i-1, n)$$
以及**邊界** (當沒有挑任何物品時)：
$$S(0, n) = 0$$
假設有 $C$ 種物品，利用上述觀念來寫：
```cpp
for (int n = 0; n <= maxn; n++) S[0][n] = 0;
for (int i = 1; i < C; i++)
for (int n = 0; n <= maxn; n++) {
if (n >= V[i])
S[i][n] = max(S[i-1][n], S[i-1][n-V[i]] + P[i]);
else
S[i][n] = S[i-1][n];
}
```
### 空間優化
狀態定義 $S(n)$ 代表目前背包體積為 $n$ 的最大價值
然後面對第 $i$ 個物品，考慮該不該拿，其中狀態轉移方程：
$$\forall n. S(n) = \max(S(n-V_i) + P_i)$$
```cpp
for (int i = 1; i < C; i++)
for (int n = maxn; n >= V[i]; n--)
S[n] = max(S[n], S[n-V[i]] + P[i]);
```
這裡有個重點：
```cpp
for (int n = maxn; n >= V[i]; n--)
```
此順序必須為**從大到小**，
舉個反例，若當 $S(n-V_i)$ 決定拿 $i$ 物品， $S(n)$ 也決定拿 $i$ 物品
由於若 $S(n) = S(n-V_i) + P_i$，這樣 $S(n)$ 相當於**拿了兩次** $i$ 物品，違反了 01 背包問題的前提。
> 這個優化叫做滾動陣列
#### 範例 [UVa OJ 10465 Homer Simpson](https://uva.onlinejudge.org/external/104/10465.pdf)：
:::info
辛普森先生吃 Krusty 漢堡需要 $m$ 時間，Apu’s Kwik-e-Mar 漢堡則需要 $n$ 時間
給定 $t$ 時間，辛普森先生**不想浪費**任何時間，無時無刻得一直吃漢堡，求辛普森先生在 $t$ 結束前能吃的最多漢堡數。
如果一定得浪費時間，辛普森先生可以喝啤酒(?)
要求輸出辛普森先生在時限內可以吃進**最多**的漢堡數，若可以喝啤酒，則需要再輸出浪費多少時間。
:::
因為每種漢堡可以吃無限多個，但 01 背包問題限制**每種只能選一次**
也就是說，只要**創造**更多種漢堡就好！
對於原本的漢堡
創造出個數(價值)為 $2, 3, ..$，以及吃的時間(體積)為 $m\cdot 2, m\cdot 3, ..$ 的多種漢堡(物品)
不過各位學過二進制都知道，只需要 $1, 2, 4, 8, ..$ 就可以做出任意正整數
```cpp
int C = 1;
for (int i = 0; m * pow(2, i) <= t; i++) {
V[C] = m * pow(2, i);
P[C] = pow(2, i);
C++;
}
for (int i = 0; n * pow(2, i) <= t; i++) {
V[C] = n * pow(2, i);
P[C] = pow(2, i);
C++;
}
```
轉成背包問題的術語後，
定義狀態 $S(i, n)$ 表示只考慮 $1$ 到第 $i$ 種物品、背包體積 $n$ 且**不浪費**任何體積的最大價值
則狀態轉移方程：
$$ S(i, n) = \max(S(i-1, n),S(i-1, n - V_i) + P_i)$$
但當 $n$ 小於 $V_i$ 或 $S(i-1, n-V_i)$ **無解**時，
$$S(i, n) = S(i-1, n)$$
$S(x, y)$ 無解的意思是： 背包體積為 $y$ 時，選 $x$ 物品一定得**浪費**體積！
而邊界為 (當背包體積為 $0$)：
$$ \forall i. S(i, 0) = 0$$
上段創造了 $C$ 種物品，利用上述觀念來寫：
```cpp
for (int i = 1; i < C; i++)
for (int n = 0; n <= t; n++)
S[i][n] = (n==0)? 0 : -1;
for (int i = 1; i < C; i++)
for (int n = 0; n <= t; n++) {
if (n >= V[i] && S[i-1][n-V[i]] != -1)
S[i][n] = max(S[i-1][n], S[i-1][n-V[i]] + P[i]);
else
S[i][n] = S[i-1][n];
}
```
其中 `-1` 代表無解的狀態。
接著看浪費多少體積：
```cpp
for (int n = t; n >= 0; n--) if (S[C-1][n]) {
printf("%d", S[C-1][n]);
if (n < t) printf(" %d", t-n);
putchar('\n');
break;
}
```
#### 練習：
[UVa OJ 624 CD](https://uva.onlinejudge.org/external/6/624.pdf)
[UVa OJ 10130 SuperSale](https://uva.onlinejudge.org/external/101/10130.pdf)
[UVa OJ 10819 Trouble of 13-Dots](https://uva.onlinejudge.org/external/108/10819.pdf)
## 無限背包問題
首先設計出此問題的**狀態定義**：
$S(n)$ 狀態表示在背包體積為 $n$ 時的最大價值
> 最好盡可能簡單直覺
假設背包體積為 $n-V_i$，則加入第 $i$ 個物品後，總價值為：
$$S(n-V_i) + P_i$$
所以，**狀態轉移方程**為：
$$S(n) = \max_i(S(n - V_i) + P_i)$$
> 對於解 $S(n)$，每次討論 $i$ 物品時，子問題都需先得到最優解
> 也就是 $S(n-V_i)$ 要先得到最優解，才能求解 $S(n)$
以及**邊界** (還未挑任何物品)： $$\forall n.S(n) = 0$$
假設有 $C$ 種物品，利用上述觀念來寫：
```cpp
memset(S, 0, sizeof S); // 還未挑任何東西的初始邊界
for (int i = 1; i <= C; i++)
for (int n = V[i]; n <= maxn; n++)
S[n] = max(S[n], S[n-V[i]] + P[i]);
```
與 01 背包的[空間優化](#空間優化)版本相反，這裡 $n$ 順序該**從小到大**
> 理解這段程式碼得先看懂 01 背包的空間優化
#### 範例 [UVa OJ 10465 Homer Simpson](https://uva.onlinejudge.org/external/104/10465.pdf)：
與 01 背包問題的範例一樣：
```cpp
memset(S, -1, sizeof S);
S[0] = 0;
for (int j = m; j <= t; j++) if (S[j-m] != -1) S[j] = max(S[j], S[j-m] + 1);
for (int j = n; j <= t; j++) if (S[j-n] != -1) S[j] = max(S[j], S[j-n] + 1);
```
接著看浪費多少時間：
```cpp
for (int i = t; i >= 0; i--) if (S[i]) {
printf("%d", S[i]);
if (i < t) printf(" %d", t-i);
putchar('\n');
break;
}
```
#### 練習：
[UVa OJ 10980 Lowest Price in Town](https://uva.onlinejudge.org/external/109/10980.pdf)
[POJ 2063 Investment](http://poj.org/problem?id=2063)
## Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence 中譯為 最長**遞增**子序列
:::info
在給定 $N$ 長度序列 $a$，找到一個子序列，為**嚴格遞增**且長度**最長**。
:::
例如 $a = (\textbf{1}, 4, \textbf{2}, 3, 8, \textbf{3}, \textbf{4}, 1, \textbf{9})$
則 LIS 為 $(1, 2, 3, 4, 9)$ 或 $(1, 2, 3, 8, 9)$
仔細考慮，若某數字在某遞增子序列**後**出現，並且它比此序列的末項還**大**，那麼加入它就能形成更長的遞增子序列！
不過在那之前，這個遞增序列是如何求得的？
通過上述，定義狀態 $S(n)$ 為以第 $n$ 個數為**結尾**的 LIS **長度**，
> 意思是在 $a_1, a_2, .., a_n$ 之間找個一定要包含 $a_n$ 的 LIS
且狀態轉移方程為，對於所有 $i < n$ 且 $a_n > a_i$：
$$S(n) = \max(S(i) + 1)$$
>也就是找出所有在 $a_n$ 之前的遞增子序列，選出最長的
若找不到 $a_n$ 之前的遞增子序列，邊界為：
$$S(n) = 1$$
```cpp
for (int n = 1; n <= N; n++) {
S[n] = 1;
f[n] = n;
}
for (int n = 2; n <= N; n++) // N 為 a 的總長度
for (int i = 1; i <= n; i++)
if (a[n] > a[i] && S[n] < S[i] + 1) {
S[n] = S[i] + 1;
f[n] = i; // 紀錄遞增子序列
}
```
複雜度為 $O(N^2)$
其中 `f[n]` 代表遞增子序列中 `a[f[n]]` 下個接 `a[n]`
例如 $a = (\textbf{1}, 4, \textbf{2}, \textbf{3}, \textbf{8}, 3, 4, 1, \textbf{9})$
得出 $f = (\textbf{1}, 1, \textbf{1}, \textbf{3}, \textbf{4}, 3, 4, 8, \textbf{5})$
所以利用 `f` 就能將其中一個 LIS 輸出！
$a_9 = \textbf{9}$ 為末項的 LIS 為例：
$f_9 = 5 \rightarrow a_5 = \textbf{8}$
$f_5 = 4 \rightarrow a_4 = \textbf{3}$
$f_4 = 3 \rightarrow a_3 = \textbf{2}$
$f_3 = 1 \rightarrow a_1 = \textbf{1}$
$f_1 = 1$
> $f_i = i$ 表示 $a_i$ 為欲輸出的 LIS 首項
### 另一種狀態定義
直覺的，**當前** LIS 末項數字越小，那麼**越有可能**使得 LIS 繼續變長
根據這樣的**貪心策略**，
定義狀態 $S(i, l)$ 為 $(a_1, a_2, .., a_i)$ 長度 $l$ 的 LIS **最小**末項
狀態轉移方程：
$$
S(i, l) =
\begin{cases}
\min(a_i, S(i-1, l)) &\text{if } a_i > S(i-1, l-1) \\
S(i-1, l) &\text{otherwise}
\end{cases}
$$
> $S(i, l)$ 有可能**無解**， 或許找不到長度為 $l$ 的 LIS
邊界：
$$S(1, 1) = a_1$$
```cpp
for (int l = 1; l <= N; l++) S[1][l] = INF;
S[1][1] = a[1];
int t = 1; // LIS 初始長度
for (int i = 2; i <= N; i++) {
for (int l = 1; l <= t; l++) S[i][l] = min(a[i], S[i-1][l]);
if (a[i] > S[i-1][t]) S[i][++t] = a[i];
}
```
> 這裡尚未用 `f` 去紀錄 LIS
由於狀態的解是 $i$ 從小到大遞推得到，可用**滾動陣列**壓縮一個維度
> 同學自行研究，這很簡單的
且這裡 $S$ 是**單調**的，於是每次將 $a_i$ 更新至序列中，就使用二分搜！
```cpp
for (int i = 1; i <= N; i++) S[i] = INF, f[i] = i;
S[1] = a[1];
int t = 1; // LIS 初始長度
for (int i = 1; i <= N; i++) {
int l = lower_bound(S+1, S+t+1, a[i]) - S;
if (l == t+1) t++;
S[l] = a[i];
p[l] = i;
f[i] = (l==1)? i : p[l-1];
}
```
其中 `p[l]` 為 `S[l]` 在原本 $a$ 序列中的位置
且由於長度是從 $1$ 開始的，所以左邊界為 $1$，右邊界為 $t$
複雜度為 $O(N \log_2 N)$
#### 練習：
[UVa OJ 10131 Is Bigger Smarter?](https://uva.onlinejudge.org/external/101/10131.pdf)
[UVa OJ 10534 Wavio Sequence](https://uva.onlinejudge.org/external/105/10534.pdf)
[UVa OJ 437 The Tower of Babylon](https://uva.onlinejudge.org/external/4/437.pdf)
[CODEFORCES 1257E The Contest](https://codeforces.com/contest/1257/problem/E)
## Longest Common Subsequence (LCS)
Longest Common Subsequence 中譯為 最長**公共**子序列
:::info
在兩個序列 $A, B$ 中找到一個**相同**(公共)且**最長**的子序列。
:::
例如：
$A = (\textbf{1}, 4, 2, 3, 8, \textbf{3}, \textbf{4}, \textbf{1}, \textbf{9})$
$B = (0, \textbf{1}, \textbf{3}, 7, 7, \textbf{4}, \textbf{1}, 9, \textbf{9})$
則 LCS 為 $(1, 3, 4, 1, 9)$
與 LIS 類似，
若某數字在某公共子序列**後**出現，並且它為兩序列的**公共**數字，那麼加入它就能形成更長的公共子序列！
不過在那之前，這個公共序列是如何求得的？
通過上述，定義狀態 $S(n, m)$ 為以 $A_n$ 以及 $B_m$ 為**結尾**的 LCS **長度**，
則狀態轉移方程為：
$$
S(n, m) =
\begin{cases}
S(n-1, m-1) + \textbf{1} &\text{if } A_n = B_m \\
\max(S(n-1, m), S(n, m-1)) &\text{if } A_n \not= B_m
\end{cases}
$$
也就是找出在 $B_m, A_n$ 之前的公共子序列，選出最長的！
假設 $A$ 序列長度為 $\text{AN}$，$B$ 序列長度為 $\text{BN}$，利用上述定義：
```cpp
for (int n = 1; n <= AN; n++)
for (int m = 1; m <= BN; m++) {
if (A[n] == B[m])
S[n][m] = S[n-1][m-1] + 1;
if (A[n] != B[m])
S[n][m] = max(S[n-1][m], S[n][m-1]);
}
```
一樣的，假設 $A, B$ 為
$$B = (0, \textbf{1}, \textbf{3}, 7, 7, \textbf{4}, \textbf{1}, 9, \textbf{9}) \\ A = (\textbf{1}, 4, 2, 3, 8, \textbf{3}, \textbf{4}, \textbf{1}, \textbf{9})$$
則輸出 $S$ 會長這樣 (第一個 row 為 $B$， 第一個 column 為 $A$)：
| | | | | | | | | | |
|---|---|---|---|---|---|---|---|---|---|
| | 0 | <div id="lcs"> **1** </div> | <div id="lcs"> **3** </div> | 7 | 7 | <div id="lcs"> **4** </div> | <div id="lcs"> **1** </div> | 9 | <div id="lcs"> **9** </div> |
| <div id="lcs"> **1** </div> | 0 | <div id="len"> **1** </div> | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| 2 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| <div id="lcs"> **3** </div> | 0 | 1 | <div id="len"> **2** </div> | 2 | 2 | 2 | 2 | 2 | 2 |
| 8 | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| <div id="lcs"> **4** </div> | 0 | 1 | 2 | 2 | 2 | <div id="len"> **3** </div> | 3 | 3 | 3 |
| <div id="lcs"> **1** </div> | 0 | 1 | 2 | 2 | 2 | 3 | <div id="len">**4**</div> | 4 | 4 |
| <div id="lcs"> **9** </div> | 0 | 1 | 2 | 2 | 2 | 3 | 4 | 5 | <div id="len">**5**</div> |
標上紫色的為 LCS 中的數，而粉紅則為此時的**長度**
也就是說，只要順著狀態轉移方程以及 $S$ 上的數，就能找到 LCS
```cpp
int n = AN, m = BN;
while(n && m) {
if (S[n][m] != max(S[n-1][m], S[n][m-1])) {
LCS.push_back(A[n]);
n--; m--;
}
else if (S[n][m] == S[n-1][m]) n--;
else if (S[n][m] == S[n][m-1]) m--;
}
reverse(LCS.begin(), LCS.end());
```
#### 練習：
[UVa OJ 10405 Longest Common Subsequence](https://uva.onlinejudge.org/external/104/10405.pdf)
[UVa OJ 10066 The Twin Towers](https://uva.onlinejudge.org/external/100/10066.pdf)
[UVa OJ 10192 Vacation](https://uva.onlinejudge.org/external/101/10192.pdf)
[UVa OJ 531 Compromise](https://uva.onlinejudge.org/external/5/531.pdf)
# Greedy method (貪心法)
>貪心法是 DP 的一種特例
回憶一下[第二週教材](https://hackmd.io/s/r14Do56HN#%E8%B2%AA%E5%BF%83%E6%B3%95)的那段話：
"每次做一個在當下看起來最佳的決策，進而漸漸求出全局最佳解"
一旦**證明**問題能被貪心法解決，通常貪心法是問題的最佳策略，因為放棄搜索所有解答空間，效率會提高不少。
通常**觀察**出一個問題是否有最優子結構時
就可**假設**看看：下某個決策能漸漸朝全局最佳解的方向走
接著**證明**每次做這個決策一定不會更差
> **證明**(或直覺?)很重要，有些看似美好的假設，不見得能求得問題的解
#### 範例 [TIOJ 1072 A.誰先晚餐](https://tioj.ck.tp.edu.tw/problems/1072)：
直覺是先讓**吃最慢**的人先上菜
比較看看，若 $a$ 和 $b$ 的吃速 $E_a < E_b$，煮菜速度 $C_a, C_b$
- 先讓 $a$ 上，總時間： $C_a + \max(E_a, C_b + E_b) = C_a + C_b + E_b$
- 先讓 $b$ 上，總時間： $C_b + \max(E_b, C_a + E_a)$
- 不管 $a, b$ 誰先上，其他人用餐時間都不會受到影響 (自行證明吧)
將總時間的 $C_b$ 消去後發現 $C_a + E_b$ 大於 $\max(E_b, C_a + E_a）$，
所以先讓 $b$ (吃較慢)上菜會比較快！
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e4 + 10;
int N, C[maxn], E[maxn];
int main()
{
while(scanf("%d", &N) && N) {
vector<int> idx;
for(int i = 0; i < N; i++) {
scanf("%d%d", &C[i], &E[i]);
idx.push_back(i);
}
sort(idx.begin(), idx.end(), [&](int x, int y) { return E[x] > E[y]; });
int cook = 0, time = 0;
for(int i: idx) {
cook += C[i];
time = max(time, cook + E[i]);
}
printf("%d\n", time);
}
return 0;
}
```
#### 範例 [CODEFORCES 1076C Make It Equal](https://codeforces.com/problemset/problem/1065/C)：
> 是第一場比賽的題目呢
模擬切格子的步驟就行了
從最高的地方 (`maxh`) 一路一層層往最低處 (`1`) 看
```cpp
for(int i = maxh; i >= 1; i--) {
:
.
}
```
對於每一層，收集**該層**的**格子**們 $s$，收集完存到累計的 `sum` 中
```cpp
sum += s;
```
但是當該層的格子加進 `sum` 中會超過 $k$ 時，就不能再收集了
此時**這個位置**就是要 slice 的地方
```cpp
if(sum + s > k) slice++, sum = 0;
```
而當 $s$ 等於 $n$ 時，也就是所有 tower 都**一樣高**了，就可以結束了
```cpp
if(s == n) {
if(sum) slice++;
break;
}
```
這裡特別注意 `sum` 如果還有東西，表示結束前還要切一刀 (slice)
在以上步驟之前，我們還得問，如何知道**某層**的 $s$ 為何？
```cpp
for(int i = 0; i < n; i++) scanf("%d", &h), s[h]++;
for(int i = maxh; i >= 1; i--) s[i-1] += s[i];
```
以下完整解題程式碼：
```cpp
#include<bits/stdc++.h>
using namespace std;
int const maxh = 2e5 + 10;
int n, k, s[maxh];
int main()
{
scanf("%d%d", &n, &k);
int h;
for(int i = 0; i < n; i++) scanf("%d", &h), s[h]++;
for(int i = maxh-1; i >= 1; i--) s[i-1] += s[i];
int sum = 0, ans = 0;
for(int i = maxh-1; i >= 1; i--) {
if(s[i] == n) {
if(sum) ans++;
break;
}
if(sum + s[i] > k) ans++, sum = 0;
sum += s[i];
}
printf("%d\n", ans);
return 0;
}
```
#### 練習:
[CODEFORCES 1140D Minimum Triangulation ](https://codeforces.com/problemset/problem/1140/D)
[ZEROJUDGE d652 貪婪之糊](https://zerojudge.tw/ShowProblem?problemid=d652)
[ZEROJUDGE d133 00357 - Let Me Count The Ways](https://zerojudge.tw/ShowProblem?problemid=d133)
[TIOJ 1861 蘿莉切割問題](https://tioj.ck.tp.edu.tw/problems/1861)
[TIOJ 1636 錢包的路](https://tioj.ck.tp.edu.tw/problems/1636)
[STEP5 0021 背包問題](http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0021)
[^memoization]: 這單字並沒有拼錯。
<style>
#len{
width: 100%;
height: 100%;
background-color: #FFAAAA;
color: #D91C21;
}
#lcs{
width: 100%;
height: 100%;
background-color: #C7B6EC;
color: #655091;
}
table.part tbody tr td {
text-align: center;
line-height: 36.5px;
padding: 0 0 0 0;
}
</style>
Sign in with Wallet
Connect another wallet