演算法基礎：從動態規劃看人生

動態規划算得上編程學習中十分重要的一種演算法了，今天就借POJ上一道題為大家介紹一下動態規劃的思維方法。

1、入門（到放棄...）

首先，什麼是動態規劃？

維基百科上是這麼說的：

動態規劃（英語：Dynamic programming，簡稱DP）是一種在數學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

聽上去有點像「大事化小，小事化了」哈，這不禁讓人想起了另一種極其相似的演算法：

遞歸

從遞歸例題如斐波那契數列（OpenJudge - 2753:菲波那契數列）中就可以了解到遞歸的基本思想：

雖然我不知道斐波那契數列第n個數是多少，但我可以通過尋找第n-1，n-2個數是多少來解決。雖然我還是不知道第n-1，n-2是多少，但我可以通過尋找n-3來解決，如此反覆，直到找到斐波那契的第1、2個數——也就是1、1，倒推回來，我們就可以知道第n個數究竟是多少了：

f(n)=f(n-1)+f(n-2)

用C++來表達就是：

int Fibonacci(int n){ if(n==1){return 1;} if(n==2){return 1;} if(n>2){return Fibonacci(n-1)+Fibonacci(n-2);} else return 0;}

可以看到，遞歸也是把問題分解成一個個子問題來解決的。那麼，動態規劃和遞歸又有什麼區別呢？

如果說遞歸是一個喜歡刨根問底的小朋友，那麼動態規劃就是一個不僅喜歡刨根問底，還喜歡拿個小本本邊問邊做記錄的小朋友。

2、動態規劃的解題思（tao）路（lu）

第一，絕對不意氣用事；

第二，絕對不漏判任何一件壞事；

第三，絕對裁判的公正漂亮，裁判機器人蜻蜓隊長前來覲見！

不好意思走錯片場了...

第一步：界定子問題。

第二步：設計解決子問題的遞歸函數

第三步：找到並解決最初始的問題（類似斐波那契數列的n=1,n=2的情況）

3、學以致用

1088：滑雪

描述：Michael喜歡滑雪，這並不奇怪， 因為滑雪的確很刺激。可是為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區域中最長的滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。下面是一個例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。輸入輸入的第一行表示區域的行數R和列數C(1 <= R,C <= 100)。下面是R行，每行有C個整數，代表高度h，0<=h<=10000。輸出輸出最長區域的長度。樣例輸入

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

樣例輸出

25

原題地址：

http://bailian.openjudge.cn/practice/1088/

第一個問題：

子問題是什麼呢？

我們可以定義子問題為：區域上任意一點的下滑路徑是多長？

第二個問題：

如何建立一個遞歸函數來求區域每一點的下滑路徑？

初步思考發現，可以通過以下步驟解決：

1、對當前點的上、下、左、右點的高度進行比較，如果有比當前點低的點則進行步驟2，如果沒有則進行步驟3。

2、下滑的長度+1，將新的點設為當前點（注意，此處有遞歸）回到步驟1

3、函數結束。

4、在所有的下滑路線中尋找最長的那個，並輸出。

第三個問題：

Base cases是什麼？

其實就是：當一個點的上、下、左、右點都比它高的時候。此時的下滑長度應該是多少？沒錯，是 1。

更多的問題：

如何保證下滑的時候不重複走已經走過的地方？

設置標記。可以對區域每個點進行標記，走過的標記為1，沒走過的標記為0。

這一點是不是讓你想起了前面那個邊問問題邊拿小本本記（ji）錄（chou）的小朋友？

可惜不是的。小朋友還在下面（stewed noodles）。

思路基本清楚啦，我們開干吧：

解法一、（遞歸）

#include <iostreamusing namespace std;//2-dementional array classclass arr{public: int** a; int r,c;//store the row and column arr(int h,int w) { r=h; c=w; a=new int*[h ]; for(int i=0;i<h ;i++) { a[i]=new int[w ]; } for(int r=0;r<h ;r++) { for(int c=0;c<w ;c++) { a[r][c]=0; } } } int *operator[](int i) { return a[i]; } ~arr() { for(int i=0;i<r ;i++) { delete [] a[i]; a[i]=NULL; } delete a; a=NULL; } arr(arr& b)//attention, if do not write your own copy constructor, the value of array can not pass to assign to function. Aka Runtime Error. { r=b.r; c=b.c; a=new int*[b.r ]; for(int i=0;i<b.r ;i++) { a[i]=new int[b.c ]; } for(int r=0;r<b.r ;r++) { for(int c=0;c<b.c ;c++) { a[r][c]=b[r][c]; } } }};int maxstep=0;//to store the max stepsvoid ski(arr &a,arr &trace,int r,int c,int step);int main(int argc, const char * argv[]){ int h,w; cin>>h>>w; arr a(h,w); for(int r=0;r<h;r++) { for(int c=0;c<w;c++) { cin>>a[r][c]; } } for(int r=0;r<h;r++) { for(int c=0;c<w;c++) { arr b(a); arr trace(a.r,a.c); int step=0; ski(b,trace,r,c,step); } } cout<<maxstep<<endl; return 0; }void ski(arr &a,arr &trace,int r,int c,int step){ step++; trace[r][c]=1;//mark the place youve been. //cout<<a[r][c]<<endl; if((r-1)>=0&&a[r-1][c]<a[r][c]&&trace[r-1][c]!=1)//do not write:if(a[r-1][c]<a[r][c]&&(r-1)>=0)!!! { ski(a,trace,r-1,c,step);//recur here } if((r+1)<a.r&&a[r+1][c]<a[r][c]&&trace[r+1][c]!=1) { ski(a,trace,r+1,c,step); } if((c-1)>=0&&a[r][c-1]<a[r][c]&&trace[r][c-1]!=1) { ski(a,trace,r,c-1,step); } if((c+1)<a.c&&a[r][c+1]<a[r][c]&&trace[r][c+1]!=1) { ski(a,trace,r,c+1,step); } if(step>maxstep) { maxstep=step; } trace[r][c]=0;//cancel the mark return;}

提交後的結果是：

內存:392kB

時間:1289ms

?Time Limit Exceeded

簡而言之，方法可以得出正確的結果，但，超時了。

問題出在哪呢？

自定義的動態二維數組類arr絕對是個拖油瓶。

好，那就幹掉他吧。

解法二、（遞歸）

#include <iostream>using namespace std;int trace[110][110];int a[110][110]; //replace the class arrint h,w;int maxstep=0;void ski(int r,int c,int step);int main(int argc, const char * argv[]){ cin>>h>>w; for(int r=0;r<h;r++) { for(int c=0;c<w;c++) { cin>>a[r][c]; } } int maxmax=h*w; for(int r=0;r<h;r++) { for(int c=0;c<w;c++) { int step=0; ski(r,c,step); if(maxstep==maxmax)break; } if(maxstep==maxmax)break; } cout<<maxstep<<endl; return 1; }void ski(int r,int c,int step){ step++; trace[r][c]=1;//mark the point if((r-1)>=0&&a[r-1][c]<a[r][c]&&trace[r-1][c]!=1) { ski(r-1,c,step); } if((r+1)<h&&a[r+1][c]<a[r][c]&&trace[r+1][c]!=1) { ski(r+1,c,step); } if((c-1)>=0&&a[r][c-1]<a[r][c]&&trace[r][c-1]!=1) { ski(r,c-1,step); } if((c+1)<w&&a[r][c+1]<a[r][c]&&trace[r][c+1]!=1) { ski(r,c+1,step); } if(step>maxstep) { maxstep=step; } trace[r][c]=0;//unmark return;}

提交後到底是怎樣的結果呢？

內存:368kB

時間:1005ms

?Time Limit Exceeded

的確快了不少，但還是不夠。

這個時候，拿小本本記錄的問題小孩終於出場了：

解法三、（動態規劃）

此解法與上面解法的不同之處在於，對每個點運用迭代函數ski計算最長下滑路徑後，都會用二維數組storage[110][110]記錄下來，下次再滑到同樣的地方（比如說點(r,c)）時，就不需要滑到底才知道最長的路徑是多長了，直接查記錄（加上storage[r][c]），就OK。

這樣一來，就減少了許多重複勞動。

#include <iostream>using namespace std;int trace[110][110]{0};int a[110][110]{0};int storage[110][110]{0};//to store the longest step of each pointint h,w;int maxstep=0;int ski(int r,int c);int main(int argc, const char * argv[]){ cin>>h>>w; for(int r=0;r<h;r++) { for(int c=0;c<w;c++) { cin>>a[r][c]; } } for(int r=0;r<h;r++) { for(int c=0;c<w;c++) { ski(r,c); } } cout<<maxstep<<endl; return 0; }int ski(int r,int c){ if(storage[r][c]>0) return storage[r][c]; trace[r][c]=1; int tempstep[4]{0}; if((r-1)>=0&&a[r-1][c]<a[r][c]&&trace[r-1][c]!=1) { tempstep[0]=!storage[r-1][c]?ski(r-1,c)+1:storage[r-1][c]+1;//if storage is not 0, do not recur, use the result stored in storage[][] } if((r+1)<h&&a[r+1][c]<a[r][c]&&trace[r+1][c]!=1) { tempstep[1]=!storage[r+1][c]?ski(r+1,c)+1:storage[r+1][c]+1; } if((c-1)>=0&&a[r][c-1]<a[r][c]&&trace[r][c-1]!=1) { tempstep[2]=!storage[r][c-1]?ski(r,c-1)+1:storage[r][c-1]+1; } if((c+1)<w&&a[r][c+1]<a[r][c]&&trace[r][c+1]!=1) { tempstep[3]=!storage[r][c+1]?ski(r,c+1)+1:storage[r][c+1]+1; } for(int i=0;i<4;i++) { storage[r][c]=max(tempstep[i],storage[r][c]); } if(storage[r][c]==0) storage[r][c]=1; if(storage[r][c]>maxstep) { maxstep=storage[r][c]; } trace[r][c]=0; return storage[r][c];}//測試數據/* 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9*/

這次提交後，看到的，到底是怎樣恐怖的畫面呢！？

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

內存:500kB

時間:7ms

Accept

我滴個媽，比解法二快了整整143倍啊！

四、從演算法看生活

人生在世，每天都有許許多多不同的感悟，每分每秒都在成長。為什麼有些人成長得很快，而有些人過了許多年依舊是老樣子？

劉未鵬曾在《暗時間》里提到，在我們突然想通某些東西的時候，往往也會發現，其實我們在很久以前早就想通過，只是後來忘了，如今又重新想通。

這樣一來，人生其實是在領悟-忘記-重新領悟的死循環中，而身在其中卻還以為自己在不斷進步。

想想真是可怕。

回過頭來看看動態規劃這個演算法，它為什麼能比改進後的迭代演算法快143倍？

唯一關鍵的區別就在於：

動態規劃這個小孩子總是在把自己學到的新東西都整理記錄下來，而迭代這個小孩子沒有。

子曰：「學而時習之，不亦說乎。」

記錄每天犯下的錯，總結每天的進步，雖然昨天的自己並不是一個巨人，但站在他的肩膀上，依舊能讓你以極快的速度成長。

就像這個小朋友一樣：

也歡迎關注我的讀書公眾號啦~

林木蔚然讀書會（ID：EspressoOcean）