動態規劃我們在工作中會經常用到，有時候你會有這個意識，而且我相信你在項目中肯定使用過，只是你不了解這種方式是“動態規劃”而已。它最大的特點就是“空間換時間“。

 

　　如果你想大致了解下，你可以直接略過細節，直接看“使用動態規劃方法求解最優鋼條切割問題”這一部分。細節部分，只是使用案例和數學公式教大家怎么去思考問題。

 

      

 

假設n=4，窮舉所有的切割方式，找到最佳的切割方案。

不切（0刀）：最高9元

1刀：最高10元

 

2刀：最高7元

 

3刀：最高4元

 

 

 從上面的圖分析得出

　　1） n米的鋼條共有2 ^n-1種切割方案。

　　2）最優策略方案為：將鋼條切割為兩段長度均為2米的鋼條，總價值為10。

 

用數學符號開始演練：（我們用加法符號表示切割，如  7 = 2 + 2 + 3，表示為長度7米的鋼條切割段數為3段，每段分別為：2米、2米、3米。）

 

k為最優切割鋼條方案中的段數，p _i為i米鋼條的價格，鋼條切割的最大收益為γ _n：

 

 

 

根據價格表樣例，尋找到所有最優收益值及對應的最優切個方案：

 

 

對于每個i=1、2、...、n-1，方案步驟如下：

　　1）將鋼條切割為長度為i和n-i的兩段；

　　2）求解這兩段的最優切割收益γ_i和γ_n-i?！糠N方案的最優收益為兩段的最優收益之和。

由于無法預知那種方案會獲得最優收益，我們必須考察所有可能的i，選取其中收益最大者。

 

　　 最優子結構：為了求解規模為n的原問題，我們先求解形式完全一樣，規模更小的子問題。通過組合兩個相關子問題的最優解，并在所有可能的兩段切割方案中選取組合收益最大者，構成原問題的最優解。

 

　　我們稱鋼條切割問題滿足 最優子結構性質：問題的最優解由相關子問題的最優解組合而成，而這些子問題可以獨立求解。

 

 

 

原有方式：

簡化版本：鋼條從左邊切割下長度為i的一段，對左邊的一段i不再進行切割，只對右邊剩下的長度為n-i的一段繼續進行切割（采用了一種自頂向下的遞歸方式）

 

遞歸方法CUT-ROD如下：

 

 

分析CUT-ROD：實際運行中，你會發現CUT-ROD的效率很差。因為CUT-ROD反復地用相同的參數值對自身進行遞歸調用，即它反復求解相同的子問題，如下圖所示：

 

CUT-ROD的運行時間為n的指數，時間復雜度如下：

 

 

　　動態規劃方法的核心思想是：對每個子問題只求解一次，并將結果保存下來。如果隨后再次需要此子問題的解，只需查找保存的結果，而不必重新計算。因此，動態規劃方法是付出額外的內存空間來節省計算時間，是典型的時空權衡的例子。

 

　　方法1：帶備忘的自頂向下法。此方法扔按自然的遞歸形式編寫，但過程會保存每個子問題的解（通常保存在數組或散列中）。當需要一個子問題解時，過程首先檢查是否已保存過此解，無則計算，有則返回。

 

　　方法2：自底向上法。將子問題按規模排序，按由小至大順序求解。當求解某個子問題時，它所依賴的那些更小的子問題都已求解完畢，結果已保存。每個子問題只需求解一次，當我們求解它時，它的所有前提子問題都已經求解完成。

 

 

 

 

 　　當思考一個動態規劃問題時，我們應該弄清所涉及的子問題及子問題之間的依賴關系。

　　

　　上面舉得n=4時，鋼條切割問題的子問題圖如下：這是遞歸調用樹的簡化版，樹中標號相同的節點收縮為圖中的單一頂點，所有邊均從父節點指向子節點。

　　

上面的圖中，我們可以把每個頂點向量化，標記為(x,y)。這個表示求解x的問題時候，我們需要子問題y的解。