# 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) ## <font color='darkblue'>什麼是動態規劃</font> 雖名動態規劃(Dynamic Programming，簡稱DP) 其實它既非動態，也非規劃，名字取得不太恰當XD 動態規劃的核心精神為： <font color='darkpink'>**同樣的問題不要再算第二遍**</font> 接下來你在這一章會看到的所有題目 都是能夠用一般的方法解決的 但這些問題都很冗，需要很多步驟才能算完 用一般的方法來解，讓電腦真的做這麼多步驟，太暴力也太天真了 若是在Green Judge上送出這樣天真的程式 大多會得到TLE(超過時限)或是SE(系統中斷) 動態規劃的目的就在於「盡可能地減少無謂的運算」 來加快程式總執行的速度 ## <font color='darkblue'>同樣的問題不要再算第二遍</font> 如果一模一樣的問題會一直重複遇到 那麼就把已經算過的問題用表格存起來 日後再遇到相同的問題時，就不用重新算一遍，直接從表格裡拿答案來用就好！ 到底怎麼樣的題目會一直需要算重複的問題? 請見以下例子 <font color='darkorange'>【例題】</font> > 還記得費氏數列吧! 它可以用遞迴函數來處理 > 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 你會發現它跑到天荒地老都不會算完 這就是為什麼我們需要動態規劃 <font color='darkpink'>**它為什麼慢?**</font> 假設今天要計算的是f(100) 為了要算出f(100)，必須先算出<font color='blue'>f(98)</font>與<font color='green'>f(99)</font> 為了要算出<font color='blue'>f(98)</font>，必須先算出f(96)與<font color='red'>f(97)</font> 為了要算出<font color='green'>f(99)</font>，必須先算出<font color='red'>f(97)</font>與<font color='blue'>f(98)</font>，可是<font color='red'>f(97)</font>與<font color='blue'>f(98)</font>已經算過了，再算一次就很浪費時間 再繼續推下去你會發現，f(96)、f(95)...一直到f(1)，都被重複計算了好幾次 如果毫不簡化，計算f(100)就需要$3*10^{20}$次的運算 f(1000000)更是不得了的天文數字 雖然看似多次，但其實很多地方的運算都可以省下來 如果第一次算的時候有把結果先存起來 那麼後面需要這些值的時候就可以直接拿來用 例如 剛才如果有把<font color='red'>f(97)</font>與<font color='blue'>f(98)</font>的值用變數儲存起來的話 在計算<font color='green'>f(99)</font>時就可以直接取這兩個值相加 但光是存<font color='red'>f(97)</font>與<font color='blue'>f(98)</font>絕對不夠，乾脆用個陣列把所有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秒就能解決了！ ## <font color='darkblue'>適用情境：計算排列組合數量</font> 建議做題目的步驟可以是： 1.用紙筆或是在腦海中推出它的遞迴式 2.用程式將它的遞迴函數寫出來 3.加上動態規劃的表格陣列、查表格、存表格 <font color='darkpink'>**遞迴式怎麼推?**</font> 對於這些走路方法組合數量的問題 可以先想想第一步有哪些走法 走了其中一種走法後，問題就會變成剩下的路的走法組合數量 將所有第一步走完後的結果加起來，就是所有組合數量 <font color='darkorange'>【例題】</font> > 樓梯有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); } ``` 再把動態規劃的部分補上去，這一題就完成了 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b024: 指南宮的階梯 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b024) 如果遞迴式子有兩個參數 像是f(x, y) 既然參數有2個 那麼動態規劃時用來儲存答案的表格就也要是2維的陣列 <font color='darkorange'>【例題】</font> > 已知函數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; } ``` 簡單來講，可以看遞迴式有幾個參數 就用幾維度的陣列去儲存運算結果 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b025: 棋盤格城市 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b025) 以上兩題是遞迴式已經擺明給你了 接下來要面臨的挑戰是需要自己設計適合的遞迴式的 <font color='darkorange'>【例題】</font> > 好熱阿~ > 草莓冰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元要湊巧克力冰跟牛奶冰 如果有存下結果，就不需要一直重新計算了 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b029: 福袋!福袋! ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b029) ## <font color='darkblue'>適用情境：找最佳解(最大值、最小值)</font> <font color='darkorange'>【例題】</font> > 好熱阿~ > 草莓冰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; } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b028: 忙碌的超商店員 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b028) ## <font color='darkblue'>經典題型：背包問題</font> <font color='darkorange'>【例題】</font> > 你有一個背包，容量為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]; } } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [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停留在原樣 最後加上動態規劃的表格就完成囉 請自行修改 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b031: 吃到飽餐廳 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b031) ## <font color='darkblue'>經典題型：最長遞增子序列</font> <font color='darkorange'>【例題】</font> > 從班上抓若干個人請他們照座號順序排好 > 如果要求他們照座號排好後的身高順序也是絕對遞增的 > 請問最多可以抓幾個人? - 如果班上只有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; } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b032: 持續進步獎 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b032) ## <font color='darkblue'>經典題型：最長共同子序列</font> <font color='darkorange'>【例題】</font> > 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; } ``` 記得加上動態規劃的表格阿！ 練習題裡的猴子輸入的是字串，不是陣列喔 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [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)
Last changed by  
 
Chu-Ling Ko
25112
Published on HackMD