前言

本文以一道常見的算法面試題開篇，引入動態規劃的基礎概念， 介紹其思考過程。

正文

一、常見的一道算法面試題——上臺階

有一個樓梯總共n個臺階，只能往上走，每次只能上1個、2個臺階，總共有多少種走法。

解決方案：

1、排列組合；

枚舉2的個數，再枚舉2具體放的位置；

計算復雜，容易遺漏。

2、動態規劃；

dp[n] 表示n個臺階的走法，那么有：

dp[n]=dp[n-1]+dp[n-2]；

思路清晰，代碼簡單。

二、動態規劃基礎概念

1、動態規劃；

動態規劃（Dynamic Programming）指的是解最優化問題的一種方法。

2、最優子結構性質；

問題的最優解可以分解為若干子問題，且子問題的解也是最優的；

以上臺階為例，到第i層的最多走法，可以分解為第i-1層和第i-2層的走法之和，且第i-1層和第i-2層的走法也是最多的；

3、 無后效性；

現階段的決策不會影響未來的決策；

以上臺階為例，走到第i-2層的最多走法，不會因為增加第i-1層而改變；

三、動態規劃思考過程

動態規劃的思考過程可以總結為：大事化小，小事化了。

大事化小：

一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題，也稱為狀態轉移；

小事化了：

小問題的解決通常是通過初始化，直接計算結果得到；

具體的步驟

1、將大問題分解為子問題

2、確定狀態表示

3、確定狀態轉移

4、考慮初始狀態和邊界情況

四、另一個經典的例子——數塔

有如圖所示的數塔，要求從頂層走到底層，若每一步只能走到相鄰的結點，則經過的結點的數字之和最大是多少？

解決思路：

1、大事化小。要到達第i層，先要到達第i-1層。并且第i層的第j個節點，只能由i-1層的第j個和第j-1個節點到達。

我們用dp[i][j]表示，走到第i層第j個位置的數字最大和。

那么有dp[i][j]=max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];

2、小事化了。第1層的第1個節點，初始值為dp[1][1]=a[1][1]。（a[x][y]表示第x層，第y個的值）

五、數塔例子的變形——收集蘋果

平面上有N*M個格子，每個格子中放著一定數量的蘋果。

你從左上角的格子開始，每一步只能向下走或是向右走，每次走到一個格子上就把格子里的蘋果收集起來。這樣下去，你最多能收集到多少個蘋果。

解決思路：

1、只能向右走或者向下走，要到達第i行第j列的格子的時候，可以由第i-1行第j列或者第i行第j-1列到達，我們用dp[i][j]表示，走到第i行第j列的最多蘋果數，那么有：

dp[i][j]=max(dp[i-1][j], dp[i][j-1]) + a[i][j];

2、第1行第1列，初始值為dp[1][1]=a[1][1]，注意事項是邊界條件的處理。

六、動態規劃經典——01背包問題

給定n件物品和一個容量為m的背包，每件物品都會消耗背包的一定容積c[i]，并帶來一定價值v[i]，要求如何選取裝入背包中的物品，使得背包內的物品價值最大。

解決思路：

把n件物品放入背包，可以分解為“將前i件物品放入容量為m的背包中”問題。

若只考慮第i件物品的選擇，那么問題可以分為兩種情況：

1、如果不放第i件物品，問題就轉化為“前i-1件物品放入容量為v的背包中”；

2、如果放第i件物品，問題就轉化為“前i-1件物品放入剩下的容量為m-c[i]的背包中”；

我們用f[i][j]表示前i個物品，放入容量為j的背包的最大價值，上面的兩種情況可以表示為

f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+v[i]);

初始化條件memset(dp, 0, sizeof(dp));和dp[1][c[1]]=v[1]。

最后遍歷f[n][1~m]可以得到最大值。

總結

如果還不能完全理解01背包，那么還需要再仔細理解最優子結構、狀態表示和狀態轉移。

算法能擴展思考方向，完善思維能力。學會“上臺階”、“數塔”、“01背包”這三個題目，能解決算法面試的動態規劃部分。

參考及引用

程序員算法基礎——動態規劃