? 動態規劃英文名Dynamic Programming，這個名稱總讓人有一種時曾相識的感覺，可能是因為容易和“線性規劃”之類的概念搞混。

? ? ? ? 首先，適用動態規劃的問題十分廣泛和常見——地圖路徑搜索（深度優先、廣度優先、A*），填充容器使價值最大化（例如背包體積固定V，有不同的物體具有各自的體積和價值），文本比較算法（常用的diff工具），以及最短路徑之類的求最優解的問題，幕后都有一只叫做DP的黑手操縱著。

? ? ? ? 一個算法非常常用，說明兩點：這個算法效果較好，時、空復雜度相對較好；.現實中大量問題符合這個算法的適用范圍。前者并無什么特別之處，而后者正是動態規劃可以稱為“算法之王”的原因。

? ? ? ? 不嚴謹的看，世界上的算法問題有三種：特別簡單的，中等的，特別復雜的。

? ? ? ? 特別復雜的問題，很不嚴謹的說就是只有窮舉才能解決的問題。算法理論中被稱為NP問題就是這種，沒有“N的多項式時間內”的解法。這種問題往往不好被人們利用。

? ? ? ? 特別簡單的問題，解決策略往往比較明顯。要么是可以簡單的用貪婪法直接做，要么就是有特定的數學方法可以很快得到結果。其中能用貪婪法的問題是這樣的問題：局部最優解的簡單疊加即為全局最優解。舉兩個例子：

? ? ? ? 1、一個小偷潛入到一個倉庫里，他只能從倉庫里拿三樣東西，問怎樣才能使小偷的利益最大化？（搶答：挑三個價值最大的貨物。）

? ? ? ? 2、你去超市購物花了N元（N為正整數），你的錢包里有1、5、10、50、100五種鈔票足夠多，問怎樣付款能讓付款的鈔票張數最少？（搶答：根據價格，從100元到1元從大到小付清為止。比如128元，付100+10+10+5+1+1+1即可。）

? ? ? ? 你一定會覺得上面兩個例子既白癡又不實際，那么，我們把他們改的實際一點。

? ? ? ? 1、一個小偷潛入到一個倉庫里，他只帶了一個包，包的容量為10公斤，倉庫里有單件1公斤、2公斤、3公斤的貨物價值分別為60元、200元、310元。問怎樣帶使小偷的利益最大化？

? ? ? ? 這個問題變得非常實際了，如果小偷一著急，從3公斤的開始裝，不足的空間用1公斤的補，是310+310+310+60 = 970元，還不錯知足了。但是，其實裝5個2公斤的，就是1000元！白賺30元。

? ? ? ? 如果把它抽象成：包裹容量為V，貨物重量weight = [w1, w2, ..., wn]，貨物價值value = [v1, v2, ..., vn]，請你編程求解，是不是就有點困難了？自古魚和熊掌不可兼得的問題大都符合這種模型。

? ? ? ? 2、為紀念M國成立60周年，政府發行了大量6元和60元紀念鈔票，并可以在市面上用于流通。具有“最少張鈔票”強迫癥的你頭疼了，因為就算你備足了各種整錢和零錢，原來的付款策略也不再奏效。例如，如果付款12元，從大到小，付一張10元和兩張1元就是3張；而其實你付2張6元就可以了。

? ? ? ? 你可能會說這個問題是瞎編的。實際上，正是為了避免這種情況，所以我們的鈔票才被設計成了現在這幾種面值。而現實中如果不是特別設計過，那么不能用貪婪法的問題其實占大多數。

? ? ? ??

? ? ? ? 現實中的問題，要解決的問題往往只有兩、三個限制條件，而往往只要兩、三個限制條件，就讓它變得既不簡單，又不是特別復雜。可喜的是，這樣正好進入了動態規劃的射程。

——————————————————————————————————————————————————————————————————

? ? ? ? 跟我看幾個實例：

? ? ? ? 一片原始森林要開發為野生旅游區，一批考察人員去實地考察，規劃旅游路線。森林里路線非常繁多，根據計劃，從A點出發，中間必須到達中途休息區（BCD三者之一都可以，未來會選擇其中一處建設成休息站）供游客休息購物，然后再出發到達E點結束。

?	B	?
起點A	C	終點E
?	D	?

? ? ? ? 原始森林里，考察人員必須自己行走，然后記錄自己到達每個點用的時間，用以最終確定路線。

? ? ? ? 這個問題很簡單，最終目標是A-E，它們的距離記作Lae，劃分成幾個子問題：

? ? ? ? Lab, Lac, Lad, Lbe, Lce, Lde

? ? ? ? Lae ?= Min( Lab+Lbe, Lac+Lce, Lad+Lde )

? ? ? ? 全局一看，無非是三條路線，選一條最短的即可。

? ? ? ? 就說A-B這一段，也有很多走法，對考察人員來說，他們得把這些小分支都走一遍，才能找到最短的一條作為Lab。

? ? ? ? 推廣開去：

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

A

1

4

7

9

12

B=12+3

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

E

1

26

5

25

8

16

20

21

22

23

24

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

? ? ? ?不管路線多么復雜，總要把所有的路走一遍才能知道最短路線。因為每一個點都有可能是最終路線的一環，要所有點全部算出來才知道。
? ? ? ?搜索策略有很多，可以任意選擇。只需要記住一個關鍵：當一路走來達到某一個點B時，B這一點只需要記錄從起點過來最少需要x步，如果從別的途徑搜索過來用了x+1步，那么這條更慢的搜索路徑也沒用，直接終止。如圖藍色的路線到B時，B已經記錄了15，藍色路線就不需要往上走了，可以往其他沒走過的格子繼續走。

? ? ? ? 可以看出，越到后來，很多搜索途徑會剛開始走就停止并不很浪費，搜索策略得當的話，這個問題的時間復雜度大致就和搜索空間一致，是O（格子數N）。實際上寬度優先搜索放在這里就是最好的方法了（反正我看起來是的）。

? ? ? ? 再看小偷裝東西的問題。

? ? ? ? 如果背包大小是10，我們完全可以看成0、1、2、3、……、9、10 ?一共11個狀態，每往包里放一個貨物，狀態就改變一次。最終達到狀態10。不同的放置策略像不像一條路徑？

? ? ? ? 1、2、3公斤的三種貨物價值分別是60、200、310。 每個狀態的價值記作m，初始狀態的價值 m0 = 0。

? ? ? ? 狀態1只能通過狀態0跳過來。m1 = 60

? ? ? ? 狀態2可以通過狀態1 或者 狀態0 轉移過來。 ?m2 = max( 60+60, 200 ) = 200

? ? ? ? 狀態3有三種跳轉方法，從狀態2來，從狀態1來，從狀態0來。

? ? ? ? 狀態4有三種跳轉方法，從狀態3來，從狀態2來，從狀態1來。

? ? ? ??狀態5有三種跳轉方法，從狀態4來，從狀態3來，從狀態2來。

? ? ? ? 依次類推……就可以得到狀態10的值了，無非是從狀態7、8、9跳轉而來，只需要取max即可。

——————————————————————————————————————————————————————————————————

? ? ? ? 我曾經遇到的最有情趣的一道題：一個N*N的棋盤，螞蟻在左上角第一個格子( 0, 0 )里的位置，棋盤的每個格子里會放0~1粒蔗糖粉末。螞蟻只能往右走或者往下走，問螞蟻怎么走，才能使吃到的糖粉最多？

? ? ? ? 提示：設( 0,0 )格能吃到的最大數量為m(0,0)，螞蟻每次都要從向下和向右中做出選擇：

? ? ? ? ? ? ? ? m(x,y) = 目前這一格上的糖粉 + max( m(x+1,y), m(x,y+1) )

? ? ? ? 這是個遞推式子，可以遞歸來解。當然想明白以后從右下角開始往上算就可以避免遞歸了。

——————————————————————————————————————————————————————————————————

? ? ? ? 大膽的抽象描述一下動態規劃問題特性：

? ? ? ? 動態規劃求解的問題，不易一眼看到明確的特征。

? ? ? ? 問題必須能夠劃分為若干子問題，或者叫做階段。必須給定已知的初始階段。

? ? ? ??每一個階段都必然從之前的某一個階段跳轉而來，每一個階段都要知道自己的最優值的判定方法，以便只保留最優的那個值。

? ? ? ? 初始階段經過一系列的跳轉，每一步跳轉都是最優解，那么達到最終階段的時候也是最優解。（核心條件，只有滿足這一條件的問題才能用動態規劃法。）

反復的討論一下：一個狀態可能是最終最優跳轉路徑的一部分，所以大多數狀態都需要被求解，雖然有可能不是。（后面會說怎么盡可能的減少求解的次數。）

有一類簡單問題：只要每一步是最優解，那么結果肯定是最優解；不需要動態規劃。有一類復雜問題：就算每一個子問題找到了最優解，跳轉之后也不一定能得到最優解；這種問題不適用動態規劃，而且不窮舉的話很難求解。

符合動態規劃的問題和上面二者不同：全局最優解一定是通過一系列局部最優解得來的，但是從某個局部最優解出發不一定能達到全局最優解。（舉例，上面小偷裝東西的問題，最終是通過2+2+2+2+2得來的，從1或者3狀態出發永遠也達不到最優解。）

最后，思考上最難的一點是：狀態空間不僅可以是1維的，還可以是2維、3維、4維……尋找最短路徑是典型的2維問題，裝包是典型的1維問題。只需要修改一下小偷裝東西問題，就可以變成2維的。

問題：小偷的背包容量為V，倉庫里有n種貨物，其價值分別為(v1,v2,...,vn)，重量分別為(w1,w2,...,wn)，剩余數量分別為(u1,u2,...,un)，求小偷獲得最大利益的方法

如果仍然使用1維的狀態空間，很容易造成求得的解超過了貨物的剩余數量，得到錯誤的解。必須使用二維空間，兩個維度分別是 當前容量、當前貨物總種類。最終跳轉到容量為V、種類為n的節點。

——————————————————————————————————————————————————————————————

更深入的探討，慢慢補充：

? ? ? ? 每多一個限制條件，狀態空間增加一維。有時候狀態空間的意義模糊不易理解，是主要的難點所在。

? ? ? ??

? ? ? ? 動態規劃問題往往有兩種解法：正向和反向，正向求解往往需要遞歸，有時候用反向可以避免遞歸。比如小偷裝東西問題，上面說的是反向解法，沒有遞歸。

? ? ? ? 你還可以找到一個遞推式

? ? ? ? ? m10 = max(m9+60,m8+200,m7+310)

? ? ? ? 其中m9、m8、m7都是未知的，直接遞歸來做就可以了。

? ? ? ? 而且，你發現了嗎，隨著遞歸深入，遞歸方式可以跳過一部分完全不需要計算的節點。舉個例子，如果輸入參數里，貨物重量都是偶數，那么在遞歸的時候，奇數狀態就不會被算到啦 ?:) ?

? ? ? ? （我在做diff算法時感覺到能跳過的節點不多，但是反向計算肯定是全都要算出來的。）

? ? ? ? 如果采用遞歸方式，務必記得用數組或者n維數組保存中間結果，不保存中間結果會反復的計算已經計算過的節點，在實際應用中覺得非常可怕。

? ? ? ? 比較惡搞的是，最終狀態不一定能達到，比如小偷裝東西的問題吧，如果貨物重量是4、6、8、10等等，而你的背包容量是21，那么不可能達到21，只能達到20，而且進一步的，某種組合方式可能最大值不是出現在后面的狀態，所以，你得max(狀態1, 狀態2 ..., 狀態n)才能得到真正的極值。網上無數代碼存在此漏洞，包括《編程之美——微軟技術面試心得》這本書。

? ? ? ? 這又牽扯到神奇的數學，不同的數字竟然會對算法造成影響，恐怕這也是數學家的樂趣所在了 = =

總結

以上是生活随笔為你收集整理的DP为王——动态规划法学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。