Ch15 動態規劃

# Ch15 動態規劃 > 搭配[green judge解題系統](http://www.tcgs.tc.edu.tw:1218/) > Special thanks to [台中女中sagit老師](http://www.tcgs.tc.edu.tw/~sagit/index.htm) \<$\_ \_$\> ## > 上一章：[貪婪演算法](https://hackmd.io/s/rkhigGlTG) > 下一章：[回溯法](https://hackmd.io/s/B1Q0_-whQ) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## 什麼是動態規劃 雖名動態規劃(Dynamic Programming，簡稱DP) 其實它既非動態，也非規劃，名字取得不太恰當XD 動態規劃的核心精神為： **同樣的問題不要再算第二遍** 接下來你在這一章會看到的所有題目都是能夠用一般的方法解決的但這些問題都很冗，需要很多步驟才能算完用一般的方法來解，讓電腦真的做這麼多步驟，太暴力也太天真了若是在Green Judge上送出這樣天真的程式大多會得到TLE(超過時限)或是SE(系統中斷) 動態規劃的目的就在於「盡可能地減少無謂的運算」來加快程式總執行的速度 ## 同樣的問題不要再算第二遍 如果一模一樣的問題會一直重複遇到那麼就把已經算過的問題用表格存起來日後再遇到相同的問題時，就不用重新算一遍，直接從表格裡拿答案來用就好！到底怎麼樣的題目會一直需要算重複的問題? 請見以下例子 【例題】 > 還記得費氏數列吧! 它可以用遞迴函數來處理 > F(0)=0 > F(1)=1 > F(n)=F(n-1)+F(n-2) > 輸入一個n，請輸出F(n) > n的範圍可以到1000000 這題我們已經在遞迴的章節練習過了遞迴的程式可以這樣寫 ```cpp= long long f(int n) { if(n==0) return 0; if(n==1) return 1; return f(n-1)+f(n-2); } int main() { int n; cin>>n; cout<<f(n)<<endl; } ``` 不過因為當時的題目n最大也不超過35 但現在你把這支程式拿去執行，n輸入1000000 你會發現它跑到天荒地老都不會算完這就是為什麼我們需要動態規劃 **它為什麼慢?** 假設今天要計算的是f(100) 為了要算出f(100)，必須先算出f(98)與f(99) 為了要算出f(98)，必須先算出f(96)與f(97) 為了要算出f(99)，必須先算出f(97)與f(98)，可是f(97)與f(98)已經算過了，再算一次就很浪費時間再繼續推下去你會發現，f(96)、f(95)...一直到f(1)，都被重複計算了好幾次如果毫不簡化，計算f(100)就需要$3*10^{20}$次的運算 f(1000000)更是不得了的天文數字雖然看似多次，但其實很多地方的運算都可以省下來如果第一次算的時候有把結果先存起來那麼後面需要這些值的時候就可以直接拿來用例如剛才如果有把f(97)與f(98)的值用變數儲存起來的話在計算f(99)時就可以直接取這兩個值相加但光是存f(97)與f(98)絕對不夠，乾脆用個陣列把所有f(x)都存起來吧！接下來就來修改我們剛才的程式 ```cpp= long long F[1000005]; //用來存算完的結果 long long f(int n) { if(n==0) return 0; if(n==1) return 1; //發現f(n)已經計算過了 if(F[n]!=-1) return F[n]; //可以直接從陣列裡拿值出來用 //f(n)還沒被計算過，那就算一下吧 F[n]=f(n-1)+f(n-2); //算完先存起來 return F[n]; } int main() { for(int i=0;i<1000000;i++) F[i]=-1; //先把F[i]通通改成-1，代表還沒算過f(i) int n; cin>>n; cout<<f(n)<<endl; } ``` 如此一來，就算n是1000000，程式也頂多運算1000000次，1秒就能解決了！ ## 適用情境：計算排列組合數量 建議做題目的步驟可以是： 1.用紙筆或是在腦海中推出它的遞迴式 2.用程式將它的遞迴函數寫出來 3.加上動態規劃的表格陣列、查表格、存表格 **遞迴式怎麼推?** 對於這些走路方法組合數量的問題可以先想想第一步有哪些走法走了其中一種走法後，問題就會變成剩下的路的走法組合數量將所有第一步走完後的結果加起來，就是所有組合數量 【例題】 > 樓梯有n階，每次可以走1階或是3階，請問n階樓梯總共有幾種走法? 假設n階樓梯總共有f(n)種走法我們知道 1. 剩下的階梯數量少於3階時，一定只能一步一步走完，也就是只有1種走法 2. 否則，第一步有兩種選擇： - 第一步走了1階的話，會剩下n-1階，也就是還有f(n-1)種走法 - 第一步走了3階的話，會剩下n-3階，也就是還有f(n-3)種走法所以它的遞迴式可以列成 ```cpp= long long f(int n) { if(n<3) return 1; else return f(n-1)+f(n-3); } ``` 再把動態規劃的部分補上去，這一題就完成了 【學生練習題】 > - [ ] [Green Judge b024: 指南宮的階梯 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b024) 如果遞迴式子有兩個參數像是f(x, y) 既然參數有2個那麼動態規劃時用來儲存答案的表格就也要是2維的陣列 【例題】 > 已知函數f(x,y)的定義為： > 如果 $x$ 是 0，則 $f(x,y)$ 為 2 > 否則，如果 $y$ 是 0，則 $f(x,y)$ 為 3 > 否則，$f(x,y)$ 為 $f(x-1,y)+f(x,y-1)$ > > 已知x和y都確定小於1000 > 輸入x與y，輸出f(x, y) 首先先將遞迴式寫出來 ```cpp= int f(int x, int y) { if(x==0) return 2; if(y==0) return 3; return f(x-1, y)+f(x, y-1); } ``` 接下來是動態規劃的部分利用一個二維陣列儲存已經算好的結果 ```cpp= int F[1005][1005] //陣列開在函式外面，大小比x和y的極限稍微大一點就可以了 int f(int x, int y) { if(x==0) return 2; if(y==0) return 3; if(F[x][y]!=-1) return F[x][y]; F[x][y]=f(x-1, y)+f(x, y-1); return F[x][y]; } int main() { for(int i=0;i<1003;i++){ for(int j=0;j<1003;j++){ F[i][j]=-1; } } int x, y; cin >> x >> y; cout << f(x, y) << endl; return 0; } ``` 簡單來講，可以看遞迴式有幾個參數就用幾維度的陣列去儲存運算結果 【學生練習題】 > - [ ] [Green Judge b025: 棋盤格城市 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b025) 以上兩題是遞迴式已經擺明給你了接下來要面臨的挑戰是需要自己設計適合的遞迴式的 【例題】 > 好熱阿~ > 草莓冰2元 > 檸檬冰5元 > 巧克力冰10元 > 牛奶冰20元 > 你有N元，希望「正好花完」，請問買的冰有幾種組合? 首先可以先列舉草莓冰要買幾杯假設N是21元那麼草莓冰可以買0杯、或1杯...或10杯，總共有11種可能若買0杯草莓冰的話，還會剩21元，接下來要考慮檸檬、巧克力、牛奶各要買幾杯來湊滿21元若買1杯草莓冰的話，還會剩19元，接下來要考慮檸檬、巧克力、牛奶各要買幾杯來湊滿19元 . . . 若買10杯草莓冰的話，還會剩1元，接下來要考慮檸檬、巧克力、牛奶各要買幾杯來湊滿1元總之，第一層已經列舉所有可能的草莓數量了所以後面就只需列舉檸檬巧克力牛奶了，**再也不考慮買草莓** 因此遞迴式需要的參數有 1. 這時考慮的是第幾種口味 2. 剩多少錢要湊遞迴式結束的情境有 1. 只剩0元了，湊滿了，回傳1代表「這是其中一種組合」 2. 還有剩下的錢，但所有種類冰都考慮完了，回傳0代表「這不是其中一種組合」遞迴式的本體 1. 對於當下考慮的口味，用迴圈列舉可以買的杯數 2. 在迴圈中呼叫自己，並且把考慮的口味改成下一個口味，剩下的錢改成剩下的錢 3. 把回傳的所有數加總，並且回傳範例如下 ```cpp= int buyIceCream(int index, int remain) { if(remain==0) return 1; if(index>=4) return 0; int ans=0; for(int i=0;i*price[index]<=remain;i++){ ans = ans + buyIceCream(index+1, remain-i*price[index]); } return ans; } ``` 還沒完，還要加上動態規劃的表格 ```cpp= int dp[10][1005]; int buyIceCream(int index, int remain) { if(remain==0) return 1; if(index>=4) return 0; if(dp[index][remain]!=-1) return dp[index][remain]; int ans=0; for(int i=0;i*price[index]<=remain;i++){ ans = ans + buyIceCream(index+1, remain-i*price[index]); } dp[index][remain]=ans; return ans; } ``` ```cpp=19 int main() { int n; cin>>n; memset(dp, -1, sizeof(dp)); //把 dp 表格全部洗成-1 int ans=buyIceCream(0, n); cout<<ans; } ``` 動態規劃可以省掉什麼案例呢例如草莓冰買了5杯，檸檬冰買了0杯，剩下11元要湊巧克力冰跟牛奶冰或是草莓冰買了0杯，檸檬冰買了2杯，剩下11元要湊巧克力冰跟牛奶冰一樣是剩下11元要湊巧克力冰跟牛奶冰如果有存下結果，就不需要一直重新計算了 【學生練習題】 > - [ ] [Green Judge b029: 福袋!福袋! ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b029) ## 適用情境：找最佳解(最大值、最小值) 【例題】 > 好熱阿~ > 草莓冰2元 > 檸檬冰5元 > 巧克力冰10元 > 牛奶冰20元 > 你有N元，希望「正好花完」，最少要買多少杯冰? 這題跟剛才那題超級像的喔還記得上一題是想要算出「總共有幾種買法」所以要用迴圈把每一種買法都加起來而這一題是問「最少杯的買法」所以一樣要用迴圈只是要改成紀錄「最小的數字」首先可以先列舉草莓冰要買幾杯假設N是21元那麼草莓冰可以買0杯、或1杯...或10杯，總共有11種可能買0杯草莓冰的話，還會剩21元，接下來要考慮檸檬、巧克力、牛奶最少買幾杯可以湊滿21元，再加上0杯就會是這種組合的總杯數買1杯草莓冰的話，還會剩19元，接下來要考慮檸檬、巧克力、牛奶最少買幾杯可以湊滿19元，再加上1杯就會是這種組合的總杯數 . . . 買10杯草莓冰的話，還會剩1元，接下來要考慮檸檬、巧克力、牛奶最少買幾杯可以湊滿1元，再加上10杯就會是這種組合的總杯數這11種草莓冰買法裡面選最少杯的就會是草莓冰的最佳買法考慮每一種冰時，選擇所有買法裡面最少杯的就是答案了要記得很可能會出現湊不出來的情況例如所有種類的冰都考慮完了，卻還有剩下的錢這種情況就要特地回傳一種奇怪數字來幫助辨別例如我習慣回傳-1，因為 -1 絕對不會是正常可能出現的答案 (哪會有-1杯呢？) 但是如果在湊不出來時選擇回傳3就不行了，因為你無法分辨是真的算出來3杯，還是在表示湊不出來遞迴式需要的參數和上一題是一樣的 1. 這時考慮的是第幾種口味 2. 剩多少錢要湊遞迴式結束的情境有 1. 只剩 0 元了，那就是 0 杯，回傳 0 代表「再買 0 杯可以花完」 2. 還有剩下的錢，但所有種類冰都考慮完了，回傳 -1 來提醒自己「這不是一個可行的組合」遞迴式的本體 1. 對於當下考慮的口味，用迴圈列舉可以買的杯數 2. 在迴圈中呼叫自己，並且把考慮的口味改成下一個口味，剩下的錢改成剩下的錢 3. 如果得到 -1，則跳過；否則看看是不是一種能夠讓總杯數更少的買法範例如下 ```cpp= int buyIceCream(int index, int remain) { if(remain==0) return 0; if(index>=4) return -1; int ans=999999; for(int i=0;i*price[index]<=remain;i++){ int t=buyIceCream(index+1, remain-i*price[index]); if(t>=0){ if(t+i<ans) ans=t+i; } } return ans; } ``` 還沒完，還要加上動態規劃的表格 ```cpp= int dp[10][1005]; int buyIceCream(int index, int remain) { if(remain==0) return 0; if(index>=4) return -1; if(dp[index][remain]!=-1) return dp[index][remain]; int ans=999999; for(int i=0;i*price[index]<=remain;i++){ int t=buyIceCream(index+1, remain-i*price[index]); if(t>=0){ if(t+i<ans) ans=t+i; } } dp[index][remain] = ans; return ans; } ``` ```cpp=20 int main() { int n; cin>>n; memset(dp, -1, sizeof(dp)); int ans=buyIceCream(0, n); cout<<ans; } ``` 【學生練習題】 > - [ ] [Green Judge b028: 忙碌的超商店員 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b028) ## 經典題型：背包問題 【例題】 > 你有一個背包，容量為w > 還有各式各樣的物品，分別的體積與價值都不同 > 你可以決定要將哪些物品裝進背包裡 > 但這些物品的體積加起來不能超過背包的容量 > 請問總共最多可以裝到多大的價值? 有限的背包容量每一樣物品都可以選擇要裝或不裝每一樣物品也有不同的體積與價值首先會想猜測，是不是從CP值最高的開始裝呢? 假設背包的容量為12單位外套的體積為9，價值為20 麵包的體積為4，價值為8 水壺的體積為6，價值為13 乍看之下覺得外套的CP值最高所以先把外套放進背包裡這時背包的容量只剩3了，再也裝不下任何東西因此總價值為20 但是如果放的是麵包和水壺背包的容量剩下2，總價值為21 你會發現這樣反而能達到更大的價值因此「先放CP值最高的物品」不是正確的策略了必須每一種可能都試試看才知道哪種是最好的 ### 列出遞迴式對於每一種物品，都有「拿或不拿」兩種選擇如果拿了外套，那麼總價值就是「剩餘容量為3的背包決定其他兩種物品」加上外套的價值如果不拿外套，那麼總價值就是「剩餘容量為12的背包決定其他兩種物品」因此決定要不要拿外套，就是在這兩者中選較大價值的那種決定完外套之後，接下來就是決定要不要拿麵包等到所有物品都被決定過後，就算是看過所有情況了但有一種情況你別無選擇那就是你的剩餘容量小於目前正在被決定的物品的體積這樣的話，一定得跳過這項物品了接下來可以寫出遞迴式囉 ```cpp= int knapsack(int index, int capacity) { if(index==n) return 0; int dont_take = knapsack(index+1, capacity); if(capacity<volumn[index]){ return dont_take } else{ int take=value[index]+knapsack(index+1, capacity-volumn[index]); return max(dont_take, take); } } ``` ### 加上動態規劃以上的做法，因為每一種物品都被決定了要拿或是不拿因此可能的組合就有2^n種，實在太多了但是相同的情況常常重複出現舉例來說，假設容量為100的書包要考慮帽子、餅乾、水壺、麵包、鉛筆在選了帽子而不選餅乾水壺後，剩下80容量要考慮麵包和鉛筆在選了餅乾和水壺而不選帽子後，一樣是剩下80容量要考慮麵包和鉛筆我們就不須重新算一次80容量考慮麵包和鉛筆可以得到多少價值了所以可以加上動態規劃的表格 ```cpp= int DP[105][1005]; int knapsack(int index, int capacity) { if(index==n) return 0; if(DP[index][capacity]!=-1) return DP[index][capacity]; int dont_take = knapsack(index+1, capacity); if(capacity<volumn[index]){ DP[index][capacity]=dont_take; return DP[index][capacity]; } else{ int take=value[index]+knapsack(index+1, capacity-volumn[index]); DP[index][capacity]=max(dont_take, take); return DP[index][capacity]; } } ``` 【學生練習題】 > - [ ] [Green Judge b030: 隨選視訊 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b030) ### 同一種物品可以拿無限多次如果同一種物品可以拿無限多次的話拿了一個之後還是可以考慮要不要拿剛才的那個除非不拿了，才要換成考慮下一個 ```cpp= int knapsack(int index, int capacity) { if(index==n) return 0; int dont_take = knapsack(index+1, capacity); if(capacity<volumn[index]){ return dont_take } else{ int take=value[index]+knapsack(index, capacity-volumn[index]); return max(dont_take, take); } } ``` 這裡的程式唯一跟上一題不一樣的地方只有第10行傳入函式的index+1改成index了因為拿完之後可能還會想拿剛才那種所以還是把index停留在原樣最後加上動態規劃的表格就完成囉請自行修改 【學生練習題】 > - [ ] [Green Judge b031: 吃到飽餐廳 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b031) ## 經典題型：最長遞增子序列 【例題】 > 從班上抓若干個人請他們照座號順序排好 > 如果要求他們照座號排好後的身高順序也是絕對遞增的 > 請問最多可以抓幾個人? - 如果班上只有1號一個人的話，那答案當然是1 - 如果班上只有1號和2號兩個人的話，那麼就看看2號是不是比1號高，是的話答案就是2，否則答案會是1 - 如果班上有1、2、3三個人的話，那麼3號要看的是 1.他比1號高嗎?是的話，那1號的答案再加一就會是一個可能的答案 2.他比2號高嗎?是的話，那2號的答案再加一就會是另一個可能的答案這兩個答案取較大者就是答案 - 如果班上有1、2、3、4四個人的話，那4號要看的就是 1.他比1號高嗎?是的話，那1號的答案再加一就會是一個可能的答案 2.他比2號高嗎?是的話，那2號的答案再加一就會是另一個可能的答案 3.他比3號高嗎?是的話，那3號的答案再加一就會是另一個可能的答案這三個答案取較大者就是答案 - 以下，以此類推接下來要用程式寫出這個函式來算出「如果n號當最後一個的話，最多可以取幾個」 ```cpp= int LIS(int n) { if(n==1) return 1; //因為1號要當最後一個的話，只能拿1號了 int ans=1; //因為前面都不拿，只拿n號的話，就是1個 for(int i=1;i<n;i++){ if(a[n]>a[i]){ int candidate=LIS(i)+1; if(candidate>ans) ans=candidate; } } return ans; } ``` 該加上動態規劃囉 ```cpp= int DP[105]; int LIS(int n) { if(n==1) return 1; //因為1號要當最後一個的話，只能拿1號了 if(DP[n]!=-1) return DP[n]; int ans=1; //因為前面都不拿，只拿n號的話，就是1個 for(int i=1;i<n;i++){ if(a[n]>a[i]){ int candidate=LIS(i)+1; if(candidate>ans) ans=candidate; } } DP[n]=ans; return ans; } ``` ```cpp=18 int main() { for(int i=0;i<105;i++){ DP[i]=-1; } int N; cin>>N; for(int i=1;i<=N;i++){ cin>>a[i]; } int ans=1; for(int i=1;i<=N;i++){ int q=LIS(i); if(q>ans) ans=q; } cout<<ans<<endl; } ``` 【學生練習題】 > - [ ] [Green Judge b032: 持續進步獎 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b032) ## 經典題型：最長共同子序列 【例題】 > 4班的同學照座號排排站 > 5班的同學也照座號排排站 > 想要從4班和5班裡面各取N個人出來 > 使得在維持原本順序的情況下 > 倆倆並排的人們身高都相同 > 請問最多可以取幾個人出來? 先從1號開始想看看： - 如果4班的1號和5班的1號身高相同，那麼絕對要取他們，再從2號比2號開始試 - 如果1號們身高不同，那麼有兩種可能 1.不取4班的1號了，4班從2號開始試 2.不取5班的1號了，5班從2號開始試以上這兩者取較大的答案，就是答案我們來用代數表示看看： - 如果4班的a號和5班的b號身高相同，那麼絕對要取他們，再從a+1號比b+1號開始試 - 如果4班的a和5班的b身高不同，那麼有兩種可能 1.不取4班的a號了，4班從a+1號開始試 2.不取5班的b號了，5班從b+1號開始試以上這兩者取較大的答案，就是答案還要記得，如果其中一班已經試完所有人了，那答案就會是0 ```cpp= int LCS(int a, int b) { //如果已經試完所有人了，答案就是0 if(a==N4) return 0; if(b==N5) return 0; //如果4班的a號和5般的b號一樣高，答案就是1加上取完這兩人後剩下的結果 if(C4[a]==C5[b]) return 1+LCS(a+1, b+1); //否則，各自拿掉第一人試試看 int candidate1=LCS(a+1, b); int candidate2=LCS(a, b+1); return max(candidate1, candidate2); } ``` ```cpp=16 int main() { cin>>N4; for(int i=0;i<N4;i++) cin>>C4[i]; cin>>N5; for(int i=0;i<N5;i++) cin>>C5[i]; int ans=LCS(0, 0); cout<<ans<<endl; } ``` 記得加上動態規劃的表格阿！練習題裡的猴子輸入的是字串，不是陣列喔 【學生練習題】 > - [ ] [Green Judge b033: 兩隻猴子 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b033) ## > 上一章：[貪婪演算法](https://hackmd.io/s/rkhigGlTG) > 下一章：[回溯法](https://hackmd.io/s/B1Q0_-whQ) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)