<style>
h2{
color:#8B4746;
}
.blue{
color:#4A919E
}
</style>
<font color="#4A919E">DSA 第十週講義</font>
===
>[name= 沈奕呈、陳睿倬][time=Apr 1,2022 ]
###### tags:`DSA` `Data Structure and Algorithm` `資料結構` `演算法` `Data Structure` `Algorithm` `tcirc39th` `社課` `臺中一中電研社`
[TOC]
---
## <div class="blue">電研社</div>
社網:[tcirc.tw](https://tcirc.tw)
online judge:[judge.tcirc.tw](https://judge.tcirc.tw)
IG:[TCIRC_39th](https://www.instagram.com/tcirc_39th)
社課點名表單:[google 表單](https://judge.tcirc.tw/ShowProblem?problemid=c053)
~~社課點名表單:[google 表單](https://reurl.cc/g0V1mQ)~~
---
## Greedy(貪婪法)
每次都採取該問題下的最佳解，而最後的輸出就是每個子問題的最佳解總和。
通常遇到這類題型，我們要做的就是尋找題目答案的原則(規則)，再不斷地依據條件計算或更改輸出。
----
### 練習: [Add All](https://zerojudge.tw/ShowProblem?problemid=d221)
根據題目要求，我們要相加一個數列。而每兩個數字的相加成本為其相加後的總和。例如:
3+5 = 8 --> cost: 8
我們可以觀察一下範例測資，尋找輸出最小成本的規則
----
解答:
因為相加後的數視為一個新的數，所以n個數固定要加n-1次，導致每次相加的兩個數越小越好(目前最小的兩個數相加)
----
#### 細節:
1. 注意輸入大小，或相加過程中是否溢位
2. 時間: 由於此題輸入量5000 --> 如何有效率地尋找最小值，並在相加後排序
----
#### priority_queue
在寫競程時，排序有助於我們方便地對資料套用一些演算法。但同時也要注意排序所花的時間。
在這裡，每相加一次就要做排序 --> 若今天數列5000個 --> 做5000-2次排序。
此時，可以考慮STL以幫你寫好的容器且會排序，如:set、mutliset還有這裡的priority_queue(以下簡寫pq)
----
由於pq不是greedy的重點，這裡不會講太多，可以參考下面網址
[連結1](https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/)
[連結2](https://www.cplusplus.com/reference/queue/priority_queue/)
[連結3](https://yuihuang.com/cpp-stl-priority-queue/)
* pq.push(x): 將x加進pq
* pq.pop(): 將最大(小)的數字取出
* pq.top(): 檢視最大(小)的數字
* pq.size(): 回傳pq長度
* pq.empty(): 回傳有無數字
```cpp=
宣告
priority_queue<int> pq1 // 由大排到小
priority_queue<int, vector<int>, greater<int>> pq2 // 由小排到大
```
----
程式碼:
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int const MaxN = 5000;
int a[MaxN], N;
int main() {
ios::sync_with_stdio(0); // 資料有點多，加速讀取
cin.tie(0);
while (1){
ll x, cost = 0; // cost可能溢位
priority_queue<ll, vector<int> , greater<int> > pq;
cin >> N;
if (N <= 0)break;
for (int i=0;i<N;i++){
cin >> x;
pq.push(x);
}
while (pq.size()>1){
// 取最小的兩個數字
ll x1, x2;
x1 = pq.top();
pq.pop();
x2 = pq.top();
pq.pop();
x = x1+x2;
cost+=x;
pq.push(x);// 加完記得塞回去
}
cout << cost << endl;
}
return 0;
}
```
----
---
## DP
dynamic programming(動態規劃)，是分治法的延伸
DP的分割方法為，<font color="#ff0000">將原問題遞推成數個同性質的子問題</font>，過程中會將每個不同的子問題答案作記憶化儲存，如此一來，再次遇到相同的子問題時便可以直接套用答案，省去不必要的重複計算
所以 DP = Divide & Conquer + memoization
----
什麼時候適合用DP?
1. 最佳子結構性質：子問題的解可以推到原本的問題的解。
2. 重疊子問題：常常需要處理相同的子問題
- 不符合第一點的話沒辦法用DP
- 符合第二點的時候，記憶化儲存就能有效減少執行次數，以空間換取時間
----
### DP VS 分治
- <font color="#ff0000">DP:</font> DP的子問題是由原問題遞推出來的，所以常常需要處理相同的子問題
<!--原問題遞推出數個子問題-->
- <font color="#ff0000">分治:</font> 分治的子問題是由大問題切割出來的，雖不大重複，但會有跨區問題
----
### DP要點
dp 由四大要素組成
1. 尋找遞迴式(recurrence)
2. 定義子問題(state space)
3. 狀態轉移(state transition)
4. 找到原問題的答案
----
#### 1. 尋找遞迴式(recurrence)
找出這個問題的規律，像解數學一樣寫出遞迴關係式
----
ex.費式數列
- 設費式數列第n項為f(n)
f(n){
n=1 , f(1)=1
n=2 , f(2)=1
n>2 , f(n)=f(n-2)+f(n-1)}
----
#### 2. 定義子問題(state space)
(1)在分治法中，我們需要決定切割問題的方法；在dp中，我們則需要知道會出現的子問題有那些，來決定要計算的範圍
(2)開一個陣列當答案的存放區，依據要計算的範圍決定陣列的長度、答案放的位置
----
ex.尋找費式數列第$n$項
(1)需要計算的子問題:第一項的值、第二項的值、...、第$n$項的值
(2)開個長度為$n+1$的陣列$f$，決定把第i項的值放在 $f[i]$
ps.你也可以直接將陣列長度固定為$max_n+1$，反正題目輸入的資料量不會超過他規定的最大值$max_n$
----
#### 3. 狀態轉移(state transition)
根據前面求出的遞迴關係式，設定基本的子問題答案，再根據實作方法設計「轉移式」的表示法
如果沒有設定基本的子問題答案，你根本沒有推移子問題的起點(或終點)
----
將轉移式對應遞迴關係式，程式的實作方法不同，轉移式寫法就不同
```cpp=
//初始子問題答案設定(initialize)
f[1]=1;
f[2]=1;
//轉移式(之後要根據實作方法調整轉移式的表示法)
f[n]=f[n-1]+f[n-2];
```
----
#### 4. 找到原問題的答案
根據你定義子問題及狀態轉移的方法，推理答案會出現在陣列的哪一格
----
第$i$項會放在第$i$格，所以答案在陣列第$n$格
```cpp=
cout<<f[n];
```
----
釐清以上四點後就可以開始實作程式碼了，實作方式分兩種
- top down
使用遞迴由「原問題」推回「基本狀態」
- bottom up
使用迴圈由「基本狀態」推至「原問題」
----
用top down的方式比較好思考，但用bottom up的執行時間比較短，所以建議大家先用top down寫寫看，再想要怎麼轉成bottom up
---
### [frog 1](https://atcoder.jp/contests/dp/tasks/dp_a)
1. 設f(n)為跳到第n格的最小花費
f(1)=0
f(n)=min(f(n-2)+h[n-2]與h[n]的高度差 , f(n-1)+h[n-1]與h[n]的高度差)
2. 需計算跳到第1~n塊石頭的花費
`int c[n+1];` 第n格放f(n)的值
4.答案為c[n]
----
### top down
top down 是先問原問題的答案，為了尋求原問題的答案，使用遞迴回推其子問題的答案，當所有衍生出的子問題都推至「基本狀態」後，便能得解
----
3. 轉移式設計為 `return c[n]=遞迴式 ;`
```cpp=
c[1]=0;
int t1=topdown(n-1)+abs(h[n]-h[n-1]);//f(n-1)+樓差
int t2=topdown(n-2)+abs(h[n]-h[n-2]);//f(n-2)+樓差
return c[n]=min(t1,t2);
```
----
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
const int max_n=1e5+1;
const int max_v=1e4;
const int inf=1<<30;//不會落在答案範圍內
int h[max_n];
int c[max_n];
int topdown(int n){
//終止條件:起點<=第0塊石頭，不可能發生
//所以去掉這個選項->給出一個比所有可能答案都高的值
if(n<1) return inf;
if(c[n]==inf){//3.轉移式
int t1=topdown(n-1)+abs(h[n]-h[n-1]);//f(n-1)+樓差
int t2=topdown(n-2)+abs(h[n]-h[n-2]);//f(n-2)+樓差
return c[n]=min(t1,t2);//記得return的時候要記憶化
}
return c[n];//算過的子問題的值不會是inf，直接套答案
}
int main() {
for(int i=1;i<=n;i+=1){
cin>>h[i];
c[i]=inf;
}
c[1]=0;//基本的子問題答案
cout<<topdown(n)<<'\n';
}
return 0;
}
```
----
### bottom up
bottom up 藉由基本的子問題答案，使用for迴圈一步步組合成母問題的答案，當組合出原問題的答案，便能得解
----
3. 轉移式設計為 `c[n]=遞迴式 ;`
```cpp=
c[1]=0;
int t1=c[i-1]+abs(h[i]-h[i-1]);
int t2=c[i-2]+abs(h[i]-h[i-2]);
c[i]=min(t1,t2);
```
----
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
const int max_n=1e5+1;
const int max_v=1e4;
const int inf=1<<30;//不會落在答案範圍內
int h[max_n];
int c[max_n];
int main() {
for(int i=1;i<=n;i+=1){
cin>>h[i];
}
c[1]=0;
c[2]=abs(h[2]-h[1]);
for(int i=3;i<=n;i+=1){
int t1=c[i-1]+abs(h[i]-h[i-1]);
int t2=c[i-2]+abs(h[i]-h[i-2]);
c[i]=min(t1,t2);
}
cout<<c[n]<<'\n';
return 0;
}
```
---
### 背包問題
是DP裡的經典問題。大致上的敘述: 今天有一堆物品，每個物品有各自的價值和重量。所求: 在有重量限制的狀況下選擇物品的價值總和越高越好。
背包問題實際上有兩種，一個是物品可以分割，另一種是不行，就是說只能選或不選。前者可以特過前面講的greedy寫，計算價值/重量的比例，優先選擇比值較高的。
而DP在處理的是後者，又稱 0 1背包問題，是道非常經典的題目。下面我們拿個例題來做示範。
---
#### 例題: [搬家規劃問題](https://zerojudge.tw/ShowProblem?problemid=c147)
我們就來把DP的四大重點套進這個題目吧。先想子問題，由於每個重量有不同的組合方式，所以無法從重量拆問題。所以試試看能不能由物品下手。我們可以從一種物品開始擺。擺完後，再看另外一種物品，若物品有更好的選擇或組合，那就選最大的。
----
看起來這方式行得通。但要如何尋找每個狀態下的最佳解呢?
這時，我們可以連同其他重量的選擇也找好。
雖然我們無法從上個重量的答案推知下個重量的答案。
但是，藉由記錄每個重量，當前w的最佳解可以變成物品價值加上$W_{重量差值}$的最佳解，省去直接窮舉的時間。
----
weight: 1 2
value: 1 3
W: 5
|| 0 | 1 | 2 | 3|4|5|
|-| - | - | - | - |-|-|
|1| 0 |1 |1|1|1|1|
|2|0|1|3|4(3+W[1])|4|4|
----
遞迴式:
這裡區分一下: 物品價值$v_i$, $w_i$ 每個重量最佳解$a_w$
$a_w$ = $max(a_w, v_i+a_{w-w_{i}})$
狀態轉移:
每當有新物品進來時，掃過陣列一遍，對每個重量最佳解進行更新。但還需要另一個陣列紀錄原陣列答案。
----
```cpp=
#include <bits/stdc++.h>
using namespace std;
int const MaxW = 1e6;
vector<pair<int, int>> vec;
int N, W;
int arr[2][MaxW+1];
int ans = 0;
bool cmp(pair<int, int> a, pair<int, int> b){
if (a.first != b.first)
return (a.first < b.first);
else
return (a.second < b.second);
}
int main(){
stringstream ss1, ss2;
string s1,s2;
getline(cin, s1);
ss1 << s1;
string x;
int idx = 0, a;
int nowi = 0, nxti = 1;
while (ss1 >> x){
a = stoi(x);
vec.push_back({a, 0});
}
getline(cin, s2);
ss2 << s2;
while (ss2 >> x){
a = stoi(x);
vec[idx++].second = a;
}
cin >> W;
N = vec.size();
sort(vec.begin(), vec.end(), cmp);
//for (int i=0;i<N;i++){
// cout << vec[i].first << ' ' << vec[i].second << endl;
//}
memset(arr, 0, sizeof(arr));
for (int n=0;n<N;n++){
for (int w = 1;w<=W;w++){
if (vec[n].first > w)continue;
arr[nxti][w] = max(arr[nowi][w], arr[nowi][w - vec[n].first]+vec[n].second);
}
swap(nowi, nxti);
}
cout << arr[nowi][W] << endl;
return 0;
}
```
---
### 練習題
DP的題目到處都是...
[AtCoder DP Contest](https://atcoder.jp/contests/dp)：Atcoder上的一系列DP題，從簡單到困難都有，解完應該靈力會提升50%(?
[AP325](https://judge.tcirc.tw/Problems?page=4&&tabid=AP325)：第六章整章都是DP，開心解ㄅ\~大部分都不會太難，~~裡面似乎混了幾題有點可怕的東東~~
(解得一點都不開心:sob: by教學長)
{"metaMigratedAt":"2023-06-16T22:15:41.283Z","metaMigratedFrom":"YAML","title":"DSA 第十週講義 臺中一中電研社","breaks":true,"slideOptions":"{\"theme\":\"sky\",\"transition\":\"convex\"}","contributors":"[{\"id\":\"a031de8f-38ef-4123-9d53-e13dd69cbbc3\",\"add\":5390,\"del\":1180},{\"id\":\"6a5475c5-bfd3-428c-9219-c760b9000deb\",\"add\":22,\"del\":0},{\"id\":\"39148de1-346d-4e2e-81c6-55b8161c633e\",\"add\":4011,\"del\":361}]"}