一嗤锉、為什么要使用動態(tài)規(guī)劃
在前面的文章中渔欢，我們介紹了貪心算法、回溯算法瘟忱，它們和動態(tài)規(guī)劃一樣奥额，通常都可以用來解決多階段決策最優(yōu)解的問題。但是在一些場景下访诱，使用它們的話垫挨，并不能解決或者不能很好地解決這種多階段決策最優(yōu)解的問題。
我們來看一個例子触菜，假設(shè)我們背包能裝15公斤重的東西九榔，現(xiàn)在地上總共三種重量的物品若干，分別是1公斤涡相、5公斤和11公斤哲泊，那么如何才能使得背包裝滿15公斤，并且物品數(shù)量最少催蝗？
如果使用貪心算法的話切威，每一步都選擇當(dāng)下最優(yōu)的，那么肯定會選擇11+1+1+1+1丙号，那么背包中總共會有5件物品先朦。
如果使用回溯算法的話，就會對1犬缨、5喳魏、11這三個數(shù)字組合成15的排列組合進行窮舉，會造成很多肯定不是最優(yōu)解的垃圾解法怀薛，比如15個1公斤重的物品放進背包里面這種肯定不是最優(yōu)解的解法刺彩。這樣就會有很高的算法時間復(fù)雜度，空耗計算機資源。
正確的解法應(yīng)該是5+5+5创倔，這個解法才是這個問題的最優(yōu)解三热，那么如何找到一個算法來得到這個最優(yōu)解呢？這就是我們今天要講的主題——動態(tài)規(guī)劃（Dynamic Programming三幻，DP）就漾。
二、動態(tài)規(guī)劃理論
2.1 動態(tài)規(guī)劃是怎么尋找最優(yōu)解的念搬？
還是以上面的例子作說明抑堡，我們構(gòu)造一個二維數(shù)組，列表示背包中可能會有多少重量的東西朗徊，行表示第n次放入物品首妖。
當(dāng)前我們物品個數(shù)沒有限制，但是規(guī)格只有1爷恳、5有缆、11三種，那么在第一次選擇物品放入背包的時候温亲，只可能有三種狀態(tài)棚壁，即背包此時重量只可能是1、5栈虚、11（見如下表格）袖外；
在第二次選擇物品放入背包的時候，我們又可以有三種選擇魂务，所以應(yīng)該有九種結(jié)果曼验，其中四種超出背包重量限制，所以不符合要求粘姜，還有兩種重復(fù)了鬓照，所以此時的合法狀態(tài)就有四種（見如下表格）；
在第三次選擇物品放入背包的時候孤紧，同理豺裆，可以有十二種結(jié)果，排除超出背包重量的坛芽，和重復(fù)的留储，合法的有5種翼抠；此時背包重量首次達到了上限15咙轩，所以我們得到了最優(yōu)解，即+5+5+5這個解法（見如下表格）阴颖。
這就是一個動態(tài)規(guī)劃解決問題的思路活喊，把問題分解為多個階段，每個階段對應(yīng)一個決策量愧，我們需要記錄每一個階段的可達狀態(tài)钾菊，當(dāng)然需要去掉不合法的帅矗，合并重復(fù)的。然后通過當(dāng)前這一步得到的狀態(tài)集合來推導(dǎo)下一個狀態(tài)集合煞烫，如此動態(tài)地往前推進浑此，直至遇到最優(yōu)解。
和回溯算法相比滞详，我們并沒有計算所有的情況凛俱，那將是指數(shù)級增長的時間復(fù)雜度；我們把超出背包重量的給排除了料饥，把重復(fù)的合并了蒲犬，把得到最優(yōu)解后剩下的合法解求解過程給終結(jié)了，所以效率上比回溯算法高效很多岸啡。
| 1（放入第一個物品） | 2（放入第二個物品） | 3（放入第三個物品） | 4（放入第四個物品） | 5（放入第五個物品）...... | |
|---|---|---|---|---|---|
| 0 | |||||
| 1 | S(+1) | ||||
| 2 | S(+1+1) | ||||
| 3 | S(+1+1+1) | ||||
| 4 | |||||
| 5 | S(+5) | ||||
| 6 | S(+5+1)(+1+5) | ||||
| 7 | S(+5+1+1)(+1+5+1)(+1+1+5) | ||||
| 8 | |||||
| 9 | |||||
| 10 | S(+5+5) | ||||
| 11 | S(+11) | S(+5+5+1)(+5+1+5)(+1+5+5) | |||
| 12 | S(+11+1) | ||||
| 13 | S(+11+1+1) | ||||
| 14 | |||||
| 15 | S(+5+5+5) |
再來一個例子原叮，假設(shè)有如下這樣一個路徑圖，要求從左上角通過右移巡蘸、下移這兩個操作來到達右下角的目的地奋隶，每個格子中的數(shù)字表示需要花費的代價，那么怎么走才能使得代價最性没摹达布？
我們當(dāng)然可以通過回溯來窮舉所有解法，但我們要嘗試使用動態(tài)規(guī)劃逾冬。首先確定這的確是一個多階段尋找最優(yōu)解的問題黍聂，而且，劃分的步驟應(yīng)該如下所示身腻。
同樣的产还，我們構(gòu)造一個二維數(shù)組，其中的數(shù)值表示達到這個位置所需要花費的最小代價嘀趟，即到達這個位置的最優(yōu)解脐区。然后逐步往終點方向推進，等到了終點時她按，此時的顯示的代價就是我們需要的最優(yōu)解牛隅。
如上這種方法被稱為狀態(tài)表轉(zhuǎn)移法。但是要最終寫成代碼酌泰，我們還需要根據(jù)上述方法寫成狀態(tài)轉(zhuǎn)移方程媒佣，只要有了方程，這個問題就算解決大半了陵刹。
我們注意到每個位置上的值都是上面或者左邊位置上的值加上本位置上的值的最小值默伍，所以可以得出一個狀態(tài)轉(zhuǎn)移方程如下：
mind_dist[i][j]=cost[i][j]+min(min_dist[i][j-1],min_dist[i-1][j])
這就有點類似遞歸了，只不過這里遞歸得到的都是一個最優(yōu)子問題的解。當(dāng)然也糊，在求解每個位置的min_dist值的時候炼蹦，因為存在重復(fù)子問題，所以我們需要將每個子問題的解存下來狸剃，供后續(xù)需要時直接使用掐隐。
2.2 什么樣的問題可以考慮使用動態(tài)規(guī)劃來解決呢？
-
多階段決策最優(yōu)解問題模型
判斷當(dāng)前這個問題是否是分為多個階段來決策钞馁，從而尋找出最優(yōu)解的瑟枫？
將不同重量的物品放到背包中，就是一個多階段決策指攒，尋找最優(yōu)解的問題模型慷妙。
-
最優(yōu)子結(jié)構(gòu)
當(dāng)前問題的最優(yōu)解包含了子問題的最優(yōu)解。即允悦，我們可以通過子問題的最優(yōu)解來推導(dǎo)出父問題的最優(yōu)解膝擂。
假設(shè)我們最終得到了最優(yōu)解f(15)，那么它的前一個步驟肯定是f(14)隙弛、f(10)架馋、f(4)其中的一個，并且只能是它們?nèi)咧凶顑?yōu)的那個才能最終推導(dǎo)出最優(yōu)解f(15)全闷，所以f(15)肯定包含了其子問題的最優(yōu)解叉寂。
-
無后效性
在推導(dǎo)父問題解法的狀態(tài)時候，我們只需要關(guān)心其直接子問題的狀態(tài)值总珠，而不用關(guān)心這個子問題的狀態(tài)值是怎么來的屏鳍，并且這些子問題狀態(tài)值不會受到后續(xù)解決父問題的影響。
最優(yōu)解f(15)的推導(dǎo)只關(guān)心它的直接子問題f(14)局服、f(10)钓瞭、f(4)，這些子問題是怎么得出的淫奔，和f(15)沒有關(guān)系山涡，而且并不會因為選擇哪一個子問題推導(dǎo)出來f(15)，這三個子問題的狀態(tài)都不會因此而發(fā)生變化唆迁⊙即裕基本上只要符合多階段決策最有問題模型的問題，都能夠滿足這個特性唐责。
-
重復(fù)子問題
存在重復(fù)的子問題鳞溉；
這個很好理解，f(14)的子問題中我們需要求解f(9)妒蔚，而f(10)的子問題中也存在f(9)穿挨，這個f(9)就是f(14)和f(10)這兩個問題的重復(fù)子問題。
三肴盏、動態(tài)規(guī)劃使用場景舉例
3.1 0-1背包問題
這個問題上面已經(jīng)有例子了科盛，不再贅述。
3.2 DAG最短路徑問題
這個例子在原先講解貪心算法的時候有提到過菜皂。
使用貪心算法求得的解是S->A->E->T贞绵，總代價為1+4+4=9；
而實際最優(yōu)解是S->B->D->T恍飘，總代價為6榨崩。
那么如何利用動態(tài)規(guī)劃來求解呢？同樣的章母，我們需要構(gòu)造一個二維數(shù)組母蛛，行是需要執(zhí)行的步驟，列是所有的節(jié)點乳怎。我們把從起點S開始每一步的合法狀態(tài)都列舉出來彩郊，到達每個節(jié)點的代價值則用重復(fù)子問題中的最小值來代表，這其實就是最優(yōu)子問題蚪缀，然后基于每一步動態(tài)地往目標(biāo)推進秫逝，最終到達終點T，此時計算出來的最優(yōu)解就是全局最優(yōu)解询枚。
| step1 | step2 | step3 | |
|---|---|---|---|
| S | |||
| A | 1(S,A) | ||
| B | 2(S,B) | ||
| C | 3(S,C) | ||
| D | 4(S,B,D) |
||
| E | 5(S,A,E)(S,C,E) | ||
| F | 6(S,A,F) |
||
| T | 6(S,B,D,T) |
3.3 拼寫糾錯問題
- 編輯距離违帆，將一個字符串轉(zhuǎn)化成為另一個字符串，需要的最少編輯次數(shù)金蜀。編輯距離越大刷后，說明相似程度越小，兩個相同的字符串其編輯距離為0渊抄。
- 萊文斯坦距離惠险，只允許通過增加、刪除抒线、替換字符這三個編輯操作班巩，是衡量兩個字符串差異程度的指標(biāo)。
- 最長公共子串嘶炭，只允許通過增加抱慌、刪除兩個編輯操作，是衡量兩個字符串相似程度的指標(biāo)眨猎。
以上兩種編輯距離的求解過程就可以使用動態(tài)規(guī)劃來解決抑进，可以抽象為把一個字符串變成另一個字符串，求解需要的最少編輯次數(shù)睡陪。
四寺渗、和其它算法的比較
貪心算法匿情、回溯算法和動態(tài)規(guī)劃這三種可以劃分為一類，它們都是用來解決多階段決策最優(yōu)解問題的解法思路信殊。
其中炬称，回溯算法是一種萬能的方法，它通過窮舉多階段的所有路徑來找到最優(yōu)解涡拘，缺點就是算法的時間復(fù)雜度非常高玲躯，只適合小數(shù)據(jù)量問題的求解，大數(shù)據(jù)量場景下還是不建議使用它鳄乏。
貪心算法和動態(tài)規(guī)劃則是兩種不同的解決思路跷车，貪心算法比較短視，每個步驟只是選擇當(dāng)下最優(yōu)的決策橱野，其它決策都拋棄朽缴，它是通過每一步的最優(yōu)來達成最終的最優(yōu)。貪心算法不是萬能的水援，有些場景下使用它并不能得到最優(yōu)解不铆。
動態(tài)規(guī)劃則是每個步驟都把合法的狀態(tài)列出來，動態(tài)地向目標(biāo)推進裹唆，這樣就不會漏掉全局最優(yōu)解誓斥。但并不是所有問題都可以使用動態(tài)規(guī)劃的，需要滿足如上的一個模型三個特征才行许帐。
分治算法單獨劃分為一類劳坑，它不是用來解決多階段決策最優(yōu)解問題的，比較適合解決大規(guī)模數(shù)據(jù)求解的問題成畦，它能通過分解問題距芬，合并答案從而達到大數(shù)據(jù)量問題求解高效的目的。
