喬治·桑塔亞納說過惜犀，“那些遺忘過去的人注定要重蹈覆轍忧换。”這句話放在問題求解過程中也同樣適用向拆。不懂動(dòng)態(tài)規(guī)劃的人會(huì)在解決過的問題上再次浪費(fèi)時(shí)間，懂的人則會(huì)事半功倍酪耳。要了解這句話浓恳，得從動(dòng)態(tài)規(guī)劃的含義說起。

什么是動(dòng)態(tài)規(guī)劃碗暗？

quora上有這樣一個(gè)問題:

How should I explain dynamic programming to a 4-year old?底下有個(gè)42K贊同的答案颈将，是這樣說的:

*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*"What's that equal to?"

*counting* "Eight!"

*writes down another "1+" on the left*

"What about that?"

*quickly* "Nine!"

"How'd you know it was nine so fast?""You just added one more"

"So you didn't need to recount because you remembered there were eight!DynamicProgramming is just a fancy way to say 'remembering stuff to save time later"

就不翻譯了，相信大家都能看懂言疗。

現(xiàn)在晴圾，我們來看一下動(dòng)態(tài)規(guī)劃的官方定義：

動(dòng)態(tài)規(guī)劃算法是通過拆分問題，定義問題狀態(tài)和狀態(tài)之間的關(guān)系噪奄，使得問題能夠以遞推（或者說分治）的方式去解決死姚。

動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段）勤篮，按順序求解子階段都毒，前一子問題的解，為后一子問題的求解提供了有用的信息碰缔。在求解任一子問題時(shí)账劲，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解瀑焦。依次解決各子問題腌且，最后一個(gè)子問題就是初始問題的解。

按照定義榛瓮，動(dòng)態(tài)規(guī)劃的原理是將一個(gè)問題分解成子問題铺董，逐漸求解局部最優(yōu)解并擴(kuò)展，最終得出全局最優(yōu)解榆芦。但是我覺得的這個(gè)不是動(dòng)態(tài)規(guī)劃的核心思想柄粹，或者說，一個(gè)”大問題“之所以能用”動(dòng)態(tài)規(guī)劃解決匆绣，并不是因?yàn)樗懿鸾獬梢欢研栴}藻三，而是這些”小問題“會(huì)不會(huì)被被重復(fù)調(diào)用。?這個(gè)概念很重要盅粪，實(shí)際上很多問題都可以拆解成小問題來解決咏删，例如我們之前講的貪心算法，但這個(gè)區(qū)別決定了該選取哪種算法 拣凹。

動(dòng)態(tài)規(guī)劃能解決什么問題森爽？

如果一個(gè)問題滿足以下兩點(diǎn)，那么它就能用動(dòng)態(tài)規(guī)劃解決嚣镜。

1.問題的答案依賴于問題的規(guī)模爬迟，也就是問題的所有答案構(gòu)成了一個(gè)數(shù)列。舉個(gè)簡單的例子菊匿，1人有2條腿付呕，2個(gè)人有4條腿，n個(gè)人有多少條腿?答案是2n條腿跌捆。這里的2n是問題的答案徽职，n則是問題的規(guī)模，顯然問題的答案是依賴于問題的規(guī)模的答案是因變量佩厚，問題規(guī)模是自變量姆钉。因此，問題在所有規(guī)模下的答案可以構(gòu)成一個(gè)數(shù)列(f(1)抄瓦，f(2)...f(n))潮瓶，比如剛剛“數(shù)腿”的例子就構(gòu)成了間隔為2的等差數(shù)列(0,2.4....2n) 。

2.大規(guī)模問題的答案可以由小規(guī)模問題的答案遞推得到钙姊。還是剛剛“數(shù)腿” 的例子筋讨，顯然f(n)可以甚于f(n-1) 求得: f(n)= f(n-1)+2

動(dòng)態(tài)規(guī)劃的應(yīng)用？

應(yīng)用場景：動(dòng)態(tài)規(guī)劃比較合適的就是來求最優(yōu)問題的摸恍，比如求最大值悉罕，最小值等等赤屋。它可以顯著的降低復(fù)雜度，節(jié)約計(jì)算時(shí)間壁袄。所有的導(dǎo)航系統(tǒng)都采用了動(dòng)態(tài)規(guī)劃类早。

我們就是以導(dǎo)航為例來看看動(dòng)態(tài)規(guī)劃吧。

比如嗜逻，我們想找到從北京到廣州的最短行車路線或者最快行車路線涩僻。當(dāng)然，最直接的笨辦法是把所有可能的路線看一遍栈顷，然后找到最優(yōu)的逆日。這種辦法只有在節(jié)點(diǎn)數(shù)是個(gè)位數(shù)的圖中還行得通，當(dāng)圖的節(jié)點(diǎn)數(shù)（城市數(shù)目）有幾十個(gè)的時(shí)候萄凤，計(jì)算的復(fù)雜度就已經(jīng)讓人甚至計(jì)算機(jī)難以接受了室抽，因?yàn)樗锌赡苈窂降膫€(gè)數(shù)隨著節(jié)點(diǎn)數(shù)的增長而成呈指數(shù)增長（或者說幾何級(jí)數(shù)），也就是說每增加一個(gè)城市靡努，復(fù)雜度要大一倍坪圾。顯然我們的導(dǎo)航系統(tǒng)中不會(huì)用這種笨辦法。

以上面的問題為例惑朦，當(dāng)我們要找從北京到廣州的最短路線時(shí)兽泄，我們先不妨倒過來想這個(gè)問題：假如我們找到了所要的最短路線（稱為路線一），如果它經(jīng)過鄭州漾月，那么從北京到鄭州的這條子路線（比如是北京-> 保定->石家莊->鄭州病梢，稱為子路線一），必然也是所有從北京到鄭州的路線中最短的梁肿。

在實(shí)際實(shí)現(xiàn)算法時(shí)飘千，我們又正過來解決這個(gè)問題，也就是說栈雳，要想找到從北京到廣州的最短路線，先要找到從北京到鄭州的最短路線缔莲。當(dāng)然哥纫，聰明的讀者可能已經(jīng)發(fā)現(xiàn)其中的一個(gè)"漏洞"，就是我們?cè)谶€沒有找到全程最短路線前痴奏，不能肯定它一定經(jīng)過鄭州蛀骇。不過沒有關(guān)系，只要我們?cè)趫D上橫切一刀读拆，這一 刀要保證將任何從北京到廣州的路一截二擅憔，如下圖。

那么從廣州到北京的最短路徑必須經(jīng)過這一條線上的某個(gè)城市（圖中藍(lán)色的菱形） 檐晕。我們可以先找到從北京出發(fā)到這條線上所有城市的最短路徑暑诸，最后得到的全程最短路線一定包括這些局部最短路線中的一條蚌讼，這樣，我們就可以將一個(gè)"尋找全程最短路線"的問題个榕，分解成一個(gè)個(gè)小的尋找局部最短路線的問題篡石。只要我們將這條橫切線從北京向廣州推移，直到廣州為止西采，我們的全程最短路線就找到了凰萨。這便是動(dòng)態(tài)規(guī)劃的原理。采用動(dòng)態(tài)規(guī)劃可以大大降低最短路徑的計(jì)算復(fù)雜度械馆。

動(dòng)態(tài)規(guī)劃的過程胖眷？

當(dāng)要應(yīng)用動(dòng)態(tài)規(guī)劃來解決問題時(shí)，歸根結(jié)底就是將動(dòng)態(tài)規(guī)劃拆分成以下三個(gè)關(guān)鍵目標(biāo)霹崎。

1.建立狀態(tài)轉(zhuǎn)移方程

這一步是最難的珊搀，大部分人都被卡在這里。這步?jīng)]太多的規(guī)律可說仿畸，只需抓住個(gè)思維: 當(dāng)做已經(jīng)知道f(1)~ f(n- 1)的值食棕，然后想辦法利用它們求得f(n)。

2.緩存并復(fù)用以往結(jié)果

這一步不難错沽，但是很重要簿晓。如果沒有合適地處理，很有可能就是指數(shù)和線性時(shí)間復(fù)雜度的區(qū)別千埃。在我們上面的例子中憔儿，每加入一條橫截線，線上平均有十個(gè)城市放可，從廣州到北京最多經(jīng)過十五個(gè)城市谒臼，那么采用動(dòng)態(tài)規(guī)劃的計(jì)算量是 10×10×15，而采用窮舉路徑的笨辦法是 10 的 15 次方耀里，前后差了萬億倍蜈缤。

3.按順序從小往大算

這里的“小和“大”對(duì)應(yīng)的是問題的規(guī)模，在這里也就是我們要從f(0), f(1).到f(n)依次順序計(jì)算冯挎。這點(diǎn)從導(dǎo)航的例子來看底哥，似乎顯而易見，因?yàn)闋顟B(tài)方程基本限制了你只能從小到大一步步遞推出最終的結(jié)果房官。

經(jīng)典動(dòng)態(tài)規(guī)劃

我們來嘗試用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)經(jīng)典斐波那契數(shù)列

斐波那契數(shù)列: 0,1. 1,2,3,5,8, 13, 21,34.55, 89, 1443....

它遵循這樣的規(guī)律:當(dāng)前值為前兩個(gè)值的和趾徽。

那么第n個(gè)值為多少?

我們用兩種方法來做比較:

方法一：簡單遞歸

如上所示，代碼簡單易懂翰守，然而這代碼卻極其低效孵奶。

下圖通過展示求解f(6)的過程說明了其原因。如圖蜡峰，隨著遞歸的深入了袁，計(jì)算任務(wù)不斷地翻倍朗恳！

方法二：動(dòng)態(tài)規(guī)劃

先上代碼≡缦瘢看不懂也沒關(guān)系僻肖，看看如果完成這三個(gè)目標(biāo)的就行了。

目標(biāo)1卢鹦，建立狀態(tài)轉(zhuǎn)移方程(完成)臀脏。也就是前面的f(n)= f(n-1)+ f(n- 2)。

目標(biāo)2冀自，緩存并復(fù)用以往結(jié)果(完成)揉稚。在線性規(guī)劃解法中，我們把結(jié)果緩存在results列表熬粗，同時(shí)在results[il = rsutsti11 + resultsti 2]中進(jìn)行了復(fù)用搀玖。這相當(dāng)于我們只需完成圖2中紅色部分的計(jì)算任務(wù)即可，時(shí)間復(fù)雜度瞬間降為O(n) 驻呐。

目標(biāo)3,按順序從小往大算(完成)灌诅。?for循環(huán)實(shí)現(xiàn)了從0到n的順序求解，讓問題按著從小規(guī)模往大規(guī)模求解的順序走含末。

堪稱完美猜拾！