建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

這一節可以看到《算法導論》學習總結 — 16.第15章 動態規劃(1) 基本入門的補充。

采用動態規劃的最優化問題的兩個要素：最優子結構和重疊子問題。

先看看最優子結構：

在第17篇總結時，裝配線調度問題中，已經設計到了最優子結構，證明最優子結構問題可以用書上說的“剪貼技術”，即假設存在更優的解，來反正最優解矛盾。

再看看重疊子問題：

當一個遞歸算法不斷的調用同一個問題時，我們說該最有問題包含“重疊子問題”。

上面這句話不好理解？

看看下面這個比較：

遞歸算法：自頂而下，對在遞歸樹中重復出現的每個子問題都要重復解一次。

動態規劃：自下而上，對每個只解一次。

結合第16篇總結的三角形求值例子，可以看得到，自下而上導致每個子問題只求解一次。

以上理論性有點強，我最開始學DP看的是HDOJ的課件，有興趣的可以去看看。

在那里面，主要講到了是找狀態轉移方程，在第16篇的三角形求值例子和第17篇的裝配線調度例子，那些遞歸公式都是狀態轉移方程。

下面這段話好好理解：

——————————————————————–

動態規劃的幾個概念: 
階段：據空間順序或時間順序對問題的求解劃分階段。 
狀態：描述事物的性質，不同事物有不同的性質，因而用不同的狀態來刻畫。對問題的求解狀態的描述是分階段的。 
決策：根據題意要求，對每個階段所做出的某種選擇性操作。 
狀態轉移方程：用數學公式描述與階段相關的狀態間的演變規律。

動態規劃是運籌學的一個重要分支，是解決多階段決策過程最優化的一種方法。

所謂多階段決策過程，是將所研究的過程劃分為若干個相互聯系的階段，在求解時，對每一個階段都要做出決策，前一個決策確定以后，常常會影響下一個階段的決策。

動態規劃所依據的是“最優性原理”。 
“最優性原理”可陳述為：不論初始狀態和第一步決策是什么，余下的決策相對于前一次決策所產生的新狀態，構成一個最優決策序列。

最優決策序列的子序列，一定是局部最優決策子序列。 
包含有非局部最優的決策子序列，一定不是最優決策序列。

動態規劃的指導思想是：

在做每一步決策時，列出各種可能的局部解，之后依據某種判定條件，舍棄那些肯定不能得到最優解的局部解。這樣，在每一步都經過篩選，以每一步都是最優的來保證全局是最優的。篩選相當于最大限度地有效剪枝（從搜索角度看），效率會十分高。但它又不同于貪心法。貪心法只能做到局部最優，不能保證全局最優，因為有些問題不符合最優性原理。

——————————————————————–

看見有人說遞歸就是DFS，而DP就是BFS，感覺有那么一點意思，對于DP，就是從底層一層層的計算，然后在當層中選取最優，逐層最優以至總體最優。

其實這個還是多做一些題就好了(⊙ｏ⊙)，大家別認為我是做題控，其實說實在話，看N遍不如做一題，說白了，算法數學本一家，算法就是數學，走過高中的，都知道數學題得多做，尤其壓軸題，看N遍不如做一遍，這個也是一樣做幾題就知道DP是神馬東東了！