# NYCU PCCA 2022 Winter Camp 0126
## [基礎動態規劃](https://www.youtube.com/watch?v=Im8BTk1Pykw&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=6)
今天的內容只有這個 但是影片幾乎快3小時...
### 前言
動態規劃（Dynamic Programming, DP）是一種演算法的設計方式。
不具備演算法定義上固定的指令集和流程，也因此==解題競賽經常出現==。
### 先備知識
建議先了解再繼續閱讀~
1. Big O 要會估計
2. 暴力搜尋要使用DP優化
3. recursive (遞迴)
### 爬樓梯問題
每一階樓梯可以往上跨1或是2步，請問跨到第n階有幾種方式？
假設 n = 4，會有5種方式。
我們可以一個一個找，也就是暴力模擬，但是當 n 很大時，就會TLE
事實上，如果你的觀察力敏銳，就能發現：
**走到第 n 階的方法數是第 n-1 階的方法數加上第 n-2 階的方法數！！！**
with knowing this, we can...
1. 從第 n 層慢慢遞迴下去 (Top-down)
2. 從第 0 階慢慢往上推 (Bottom-up)
### What is dp?
核心觀念：<font size = 4>==將大問題轉成同性質小問題==</font>
則小問題便會因為性質相同，能變成更小的問題，直到規模足夠小的時候，能直接得知答案，這相當於求原問題的遞迴解
* 法 1：**不重複計算**
e.g. 費氏數列
f(n) = f(n-1) + f(n-2)
f(1)=1, f(2)=1
如果要計算 f(6)，要像下圖一樣
f(6) = <font color = "#F0F">f(5)</font> + <font color = "#2D9">f(4)</font>
= <font color = "#F0F">f(4) + f(3)</font> + <font color = "#2D9">f(3) + f(2)</font>
= <font color = "#F0F">f(3) + f(2) + f(2) + f(1)</font> + <font color = "#2D9">f(2) + f(1) + f(2)</font>
= . . . . . .
這當中有許多重複的計算，那如果我們把算過的資訊記錄下來呢？
就只要計算 6 次！
* 法 2：**狀態壓縮**
不儲存不需要的狀態，壓縮掉資訊，以提高執行效率
e.g. 爬樓梯的 dp[5]
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
2 2 1
2 1 2
1 2 2
只要處存有 8 種方式就好，不需要知道每種方式的詳細步驟
<font size = 4>如果某些狀況在未來擁有相同發展，便可以被壓成相同狀態來看待！</font>
* 法 3：**轉移**
轉移就是如何將原本問題與子問題的解產生關聯，進而從原本的解，求得原問題的解
* **複雜度估計**
複雜度基本上就是狀態數量乘以狀態轉移的複雜度
e.g.
爬樓梯問題需要計算的狀態量為n個，空間複雜度為O(n)
時間複雜度為狀態數量乘以2，共是2n，時間複雜度為O(n)
* **總結**
1. 當你看到一個題目能切成相同性質的子問題時，往DP的方向去思考
2. 試著去定義狀態，並盡量壓縮掉無意義的資訊（避免陣列開太大、空間複雜度太大）
3. 考慮狀態轉移式，注意邊界問題
4. 複雜度是否合理，如果太大，試著優化狀態轉移式，若還是不行就得重新定義狀態
:::warning
**最難的地方：定義狀態轉移式** → 只能靠多刷題累積觀察經驗
:::
### 題目類型
#### 1. 計數型
一般會叫你計算出總共有多少情況
e.g. 前面提到的爬樓梯問題, 爬格子問題 . . .
**爬格子問題**：有 n * m 的方格，想要從最左上到最右下，且只能走最短路徑 (只能往右和往下走)，共有幾種方法？
解法：由於只能往右和往下走，在某一格的方法數必定來自左邊的方法數和右邊的方法數相加
> **計數型的轉移必須包含所有類型，才不至於少算
> 各種情形必須獨立不重複，才不至於多算
> → 「不漏不重」**
#### 2. 最佳化型
如果將爬樓梯問題改成最佳化型：
走上第 i 階階梯要花 cost[i] (cost[i]>0) 元，從第 0 階開始往上，每次可以跨一階或是兩階，請問走到第 n 階花費最少要付多少錢？
第 n 階的最小花費要不來自第 n-1 階或 n-2 階再加上走到第 n 階的費用
``` cpp
dp[n] = min(dp[n - 1], dp[n - 2]) + cost[n]
```
:::danger
⚠注意！！！
使用DP的前提是必須證明「子問題的最佳解能得到原問題的最佳解」
:::
舉個反例：
假設我們現在尋求走上第 n 階時，個位數最小的花費
如果第 5 階的個位數有 6 和 9 兩種可能
但是踏上第 6 階的花費如果是 2 塊錢，
那麼最低花費應該是 (9 + 2) % 10 = 1，而不是 (6 + 2) % 10 = 8
錯誤的原因是：只存最小花費 **未必使之後的解是最小花費**
那怎麼辦呢？
改善方法：除了==改變狀態==，也可以對狀態==追加描述、增維==
將狀態改為 dp[i][j] 表示踏上第 i 階時，達到個位數花費 j 是否有可能
``` cpp
dp[i][j] = (dp[i - 1][k] || dp[i - 2][k]) // k 滿足 k + cost[i] 的個位數為 j
```
### 例題舉隅
#### 1. 切棍子問題
有一根長度為n的木棍，cuts數組標記棍子上一些需要被切開的位置，每次切開所花費的花費是那條木棍的長度，求最佳切割的順序下的最小成本。(Leetcode 1547)
我們所知道的正解：
7+4+3+2=16
<h5> 1. 暴力解？</h5>
複雜度為 O(m!)
<h5> 2. DP 解法？</h5>
假設我們已經知道所有子問題的解了.....
```cpp
dp(i,j)=min(dp(i,k)+dp(k,j))+cuts[j]-cut[i], k=i+1,.....,j-1
```
意義：
棍子的最小花費就是枚舉第一刀的切法後，兩條子木棍的最小花費總和加上該木棍的長度！
實作：
```cpp=
sort(cuts.begin(), cuts.end());
int stick(int st, int en) {
if(en - st == 1) return 0;
if(dp[st][en] != b) return dp[st][en];
for(int i = st + 1; i < en; i++) {
if(dp[st][en] == 0) {
dp[st][en]=stick(st, i) + stick(i, en) + (cuts[en] - cuts[st]);
}
else {
dp[st][en] = min(dp[st][en], stick(st, i) + stick(i, en) + (cuts[en] - cuts[st]));
}
}
return dp[st][en];
}
```
複雜度：
假設 cuts 裏面有m個元素，每次狀態轉移要花 O(m)，總共有 m^2^ 種狀態，故複雜度是 O(m^3^)
#### 2. 找零錢問題
給你一個金額 n 元，請你回答有多少種硬幣組合方式。
你的幣值有 1元, 5元, 10元, 25元, 50元
請注意，當 n = 0 時，我們算它是一種方式
(from Lucky Cat)
直觀想法：
``` cpp
dp[n] = dp[n-1] + dp[n-5] + dp[n-10] + dp[n-25] + dp[n-50];
```
Does it work？
dp[1] = 1, dp[5] = 2
假設用剛剛的式子算 n=6，則 dp[6] = dp[6-1] + dp[6-5] = 3
但是 n=6 只有 111111 和 51 兩種方法
why？ 因為重複計算 15 和 51
為了避免這種排列順序不同，組合卻相同的情形，我們希望讓==小的先放、大的後放==，這樣保證了順序必定由小至大，不會反過來，不會出現僅排列不同的問題。
考慮前 n 種硬幣組成金額 m 的情形，可以分成使用第 n 種硬幣，以及不使用，共兩種可能。
不使用的話就只靠前 n-1 種硬幣；使用的話就必須前 n 種組成 m-value[n]，
加上第 n 種硬幣剛好金額 m。
```cpp
dp[n][m] = dp[n-1][m] + dp[n][m-value[n]]
```
dp[n-1][m] 定義上必不包含第 n 種硬幣；
而 dp[n][m-value[n]] 則包含 0 至多個第 n 種硬幣，加上一個第 n 種硬幣，則至少有 1 個。
於是兩邊獨立不交集，又互相補完 0 和多個第 n 種硬幣的可能情形。
**滾動陣列**
考慮第 n 種硬幣時，從轉移來看，實際上只需要 dp[n] 和 dp[n-1] 兩條陣列。
因此，可用兩條陣列 p, q 分別代表 dp[n-1] 和 dp[n]，之後交替代表 dp[n] 和 dp[n-1]，
即為滾動數組，可將空間複雜度自 nm 降至 2n。
實作方法 (通常使用3. 4.)：
1. 視奇偶互相交替使用
2. 將新算的結果複製到舊的
3. 宣告 int dp[2][M]; 用 dp[n&1] 和 dp[(n-1)&1] 分別代表
> n&1 和 n%2 是等價的
5. 宣告兩條陣列和兩個指標 p, q 並透過交換 p, q 來輪替
:::spoiler 聽起來已經不錯了
還可以優化喔 不要停下來
:::
我只想用一條陣列啦！
考慮到方向性，m 一定是從金額較小的 m-value[n] 轉移落來的，方向單一，故可用一條陣列
而剛進到第 n 個硬幣時，陣列存的是 n-1 時的內容，便可寫成：
```cpp
dp[m] += dp[m-value[n]];
```
```cpp
for (int i = value[n]; i <= M; i++) {
dp[i] += dp[i-value[n]]
}
// 注意for迴圈順序，如果順敘寫反那答案就會錯喔~
```
<h4> 3. 背包問題 </h4>
有 n 個物品，每個物品有自己的 價值 : c[i] 和 體積 : w[i]
還有一個容量為 m 的背包
求最佳情況下，可以放入背包的最高價值
<h5> Greedy? </h5>
如果我們直接根據每個物品的價值除以體積來挑呢?
反例 :
當背包容量為 6
且有下方四個物品
| | 價值 | 體積 | CP值 |
| -------- | -------- | -------- | -------- |
| 物品A | 2 | 3 | 0.66 |
| 物品B | 4 | 3 | 1.33 |
| 物品C | 2 | 4 | 0.5 |
| 物品D | 5 | 4 | 1.25 |
:::warning
不會是最佳解
:::
<h5> 暴力？ </h5>
直接爆開所有組合
:::warning
開心TLE😀
:::
<h5> 以DP觀點來思考 </h5>
* **壓縮狀態**
知道有更高價值的解，就不需要紀錄
* **最簡單的狀況**
當沒有物品時，背包體積 0 ~ m 的最佳解 ?
* **同性質小問題**
已知 i – 1 個物品，體積 0 ~ m 的解
→ 前 i 個物品，背包體積 0 ~ m 的解 ?
<h5> 初始條件及轉移式 </h5>
初始化 :
``` cpp
for(j: 0 ~ m) dp[0][j] = 0
```
轉移 :
``` cpp
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + price[i])
```
舉例來說...
| | 價值 | 體積 | CP值 |
| -------- | -------- | -------- | -------- |
| 物品A | 2 | 3 | 0.66 |
| 物品B | 4 | 3 | 1.33 |
| 物品C | 2 | 4 | 0.5 |
| 物品D | 5 | 4 | 1.25 |
#### 4. 最長遞增子序列(LIS)
給一個長度為 n 的陣列
挑出陣列中幾個遞增的元素
找到所有可能中，最長會是多長
##### 用 DP 觀點來思考
* **壓縮狀態**
知道有更長的解，就不需要紀錄
* **最簡單的狀況**
當陣列長度為 1 的時候，解為 ?
* **同性質小問題**
已知 0 ~ i – 1 前所有陣列的解
→ 0~i 陣列的解 ?
##### 初始條件及轉移式
初始化 :
```cpp
for(i : 0 ~ n) dp[i] = 1
```
轉移 :
```cpp
if(arr[i] > arr[j])
dp[i] = max(dp[i], dp[j] + 1)
```
### 其他
#### 1. 回溯法
額外存取最佳解的來源
適合用在問題為「如何得到最佳解」的情況
#### 2. 滾動陣列
動態規劃中，有些資訊再也不會用到了，我們可以透過拿這些陣列來做新一輪的 DP，而不是在開新的陣列，以壓縮記憶體空間。
---
## 課後講義-DAG DP
### 什麼是DAG?
DAG (Directed Acyclic Graph)，又稱作無環有向圖
顧名思義為一個有向圖，圖上不會有環，各節點沒必要相連，也可以被視作為樹。
### DAG 和 DP 的關係
如果將 DAG 圖上的節點看作是某個狀態
而箭頭從 A 指向 B，代表B為A的一個子問題
當我們滿足所有子問題之後，就能夠得到原問題的解了
因此 DAG 跟動態規劃看似無關，但不少問題都可以轉化為 DAG 問題了。
最常見的有三種問題：
1. 最長路徑
2. 最短路徑
3. 路徑計數問題
接下來就介紹幾個運用例題：
### 嵌套矩形問題
有n個矩形，每個矩形可以用兩個整數a,b描述表示長和寬。
矩形X(a,b)可以巢狀嵌套在矩形Y(c,d)中若且為若a<c, b<d 或 b<c, a<d(相當於把矩形X旋轉90度)。
例如(1,5)可以嵌套在(6,2)內，但不能嵌套在(3,4)內。你的任務是選出盡量多的矩形排成一航，使得除了最後一個之外，每一個矩形都可以嵌套在下一個矩形內
#### 解題分析：
矩形之間的「可嵌套」必定不會有雙向邊（大的不能套到小的），而且也不可能會有環，因此是一個典型的二元關係。那這種情況就可以建成一個DAG圖。
把每一個點當成一個矩形，而A指向B則代表A能夠嵌套B。在這樣的情況下，我們要求的就是DAG上的最長路徑。
#### 實際作法：
我們可以去計算每個點的入度（即被幾個箭頭指向），如果為0的話就是無法再被嵌套了，即能夠得到該點的解答
#### 狀態轉移式：
dp[點A能被嵌套的最大數量]=max(dp[子節點Xi能被嵌套的最大數量])+1, i=所有指向A的點
每次我們確定一個節點的最佳解時，就可以將其轉移到母問題，然後拔掉這個點還有相連的邊
這樣我們能逐漸地計算出每一個點的最佳解，最終得到答案。
### 硬幣問題
有n種硬幣，面值分別為V~1~, V~2~, ..., V~n~，每種都有無限多。給定非負整數S，可以選用多少個硬幣，使得面值之和恰好為S?
輸出硬幣數目的最小值和最大值。(1≤n≤100, 0≤S≤10000, 1≤V~i~≤S)
#### 解題分析：
雖然看上去和上一題很不一樣，但本題的本質也是DAG上的路徑問題。我們把每種面值看作一個點，表示「還需要湊足的面值」，則初始狀態為S，目標狀態為0。若目前在狀態i。每使用一個硬幣j，狀態便轉移到i−V~j~
## 快樂 DP 時間
### 基礎題單
[Radio Commercials](https://open.kattis.com/problems/commercials)
[Alphabet](https://open.kattis.com/problems/alphabet)
[Walrus Weights](https://open.kattis.com/problems/walrusweights)
[Knapsack](https://open.kattis.com/problems/knapsack)
[Increasing Subsequence](https://open.kattis.com/problems/increasingsubsequence)
[Nine Packs](https://open.kattis.com/problems/ninepacks)
[Spiderman’s Workout](https://open.kattis.com/problems/spiderman)
[Presidential Elections](https://open.kattis.com/problems/presidentialelections)
[uva674 快樂找零錢](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=615)
[uva11351 約瑟夫問題](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2326)
[TOJ80 game](https://toj.tfcis.org/oj/pro/80/)
### 進階題單
[Canonical Coin Systems](https://open.kattis.com/problems/canonical)
[2021icpc台北站的i (題敘去右邊statment裡的題本找)](https://codeforces.com/gym/103443/problem/I)
[Restaurant Orders](https://open.kattis.com/problems/orders)
[leetcode446](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/)
[leetcode354(想要nlogn很難)](https://leetcode.com/problems/russian-doll-envelopes/)
Sign in with Wallet
Connect another wallet