動态規劃 肥波那期數列_粗析動态規劃DP

在吃了幾次DP的虧以後，我終于開始着手準備DP的博文了……

首先推薦一篇圖文：

轉自程式員小灰，侵删

圖文所使用的JAVA代碼我已經将其轉換為了CPP代碼并貼于文末，有興趣自取~~

首先讓我們來了解一下，什麼是動态規劃

動态規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動态規劃 ——引用自百度百科

動态規劃題目的特點：

1.計數有多少種方式走到右下角

有多少種方法挑選出K個數使得和為sum

……

2.求最大最小值從左上角走到右下角路徑的最大數字和

最長上升子序列長度

……

3.求存在性取石子遊戲，先手是否獲勝

能不能選出K個數使得和為sum

……

但是如果要求輸出所有的情況，則不是動态規劃的題目，此時應當考慮深搜或者疊代

動态規劃的題目沒有固定的模闆(變化比較多)，一般難度比較高，屬于中上難度，是必須要掌握的算法

動态規劃有三個重要的概念：最優子結構：問題的最優解由相關子問題的最優解集合組成

邊界：問題的邊界，得到有限的結果

狀态轉移公式：問題每一階段和下一階段的關系

動态規劃解題步驟：

說明：這裡我們直接借用侯老師的視訊給大家解釋，因為視訊時間較長，我給大家總結了關鍵點

首先引入一個題目：

我有十級台階，每次可以上一級或者兩級，我上完整個台階有多少鐘方法？

看完這個題目，你或許想的是用排列組合的思想，寫一個多層的虛幻周遊所有的情況然後統計最後的答案吧，但是這種算法所需的時間複雜度确實太大O(n2)，那有沒有更優秀的算法呢？

當然有！

有請今天的主角——動态規劃

要寫出動态規劃的題，我們需要如下3個步驟

1.确定狀态

确定狀态需要兩個意識：最後一步

子問題

我們首先來确定最後一步

在剛剛列出的問題中，最後一步有兩種走法：

走一步和走兩步，這兩種走法都是固定的

然後我們再來看看，假設走到第九級有X種走法，走到第八級有Y種走法

那麼，走到第十級有多少種走法呢？

哈哈，當然是X+Y種啦！因為走到第九級的時候，就隻有一種走法——走一步了

走到第八級的時候，也隻能走兩步，因為如果走一步的話，就包含在走到九級的情況中了

是以走到十級的情況隻有X+Y

2.轉移方程

現在，我們把走到第十級的方法數表示為F(10)

走到第九級和第八級的方法數分别表示為F(9)，F(8)

是以有F(10)=F(9)+F(8)

同理，有F(9)=F(8)+F(7)，F(8)=F(7)+F(6)……

于是我們歸納出如下一個公式：

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

這就是這道題階段與階段間的狀态轉移方程，決定了問題的每一個階段和下一個階段的關系

3.初始條件和邊界情況

但是當我們計算到最後一級或者兩級台階的時候，我們便無需繼續計算，于是F(1)和F(2)便是問題的邊界，但是如果一個問題沒有邊界，那麼我們永遠無法得到一個有限的結果

解決了如上三個問題，接下來便是寫代碼了

或許你會說，噫，不就是個遞歸麼，好辦！但是如果仔細分析，你會發現，如果使用遞歸，時間複雜度依舊是O(n2)，這就不是我們費勁來尋找更快的算法的理由的，在這個遞歸中，出現了大量的重複計算，比如F(10)=F(9)+F(8)，F(9)=F(8)+F(7)，F(8)=F(7)+F(6)，裡面的F(8)便被計算了兩次，當F(n)中n的值足夠大時，裡面重複計算的就更多，也許聰明的你很快就想到了使用備忘錄算法來解決這件事，但是使用備忘錄算法的空間複雜度卻有O(n)，這也是一個比較讓人頭疼的事情

那麼……有沒有更好的解決辦法呢？

突然，一個小夥伴發現，這個……莫非解釋傳說中的肥波納妾數列？(斐波那契數列)

是的，按照斐波那契數列的計算方式，我們可以很快的列出式子來解決這個問題int get_climbing_way(int n){

if (n<1) return 0;

if (n==1) return 1;

if (n==2) return 2;

int a=1,b=2,tmp=0;

for (int i=3;i<=n;i++){

tmp=a+b;

a=b;

b=tmp;

}

return tmp;

}

程式從i=3開始疊代，一直到i=n結束，時間複雜度O(n)，空間複雜度O(1)，是不是很便捷的算法呢？

當然，本文隻是粗略的解析了一下動态規劃，因為DP的變數實在太多，還是應當多加練題才能徹底參透DP

例題：

番外個體

1.圖文代碼翻譯：備忘錄算法int get_climbing_ways(int n){

if (n<1) return 0;

if (n==1) return 1;

if (n==2) return 2;

if (s.count(n)) return s[n];

int value=get_climbing_ways(n-1)+get_climbing_ways(n-2);

s[n]=value;

return value;

}

2.最後給個答案吧：89

若未經特殊說明，本文：《 粗析動态規劃DP 》為部落客原創作品，未經授權禁止轉載