第一次接觸dp問題覺得超級棘手，短短的幾行代碼竟然把答案描繪的淋漓盡致，卻不讓人懂，在我思考許久未果后開始轉向思考從短短的工業(yè)革命興起的各種思想，代代數學家和科學家總結的這些精華究竟存在哪些共性和異性，如何發(fā)現問題，解決問題，從最本質最易懂的方面下手，從而發(fā)現許多東西首先要翻譯的好，精煉的好。從基本的規(guī)律到總結出常人難懂的定理需要走多遠呢，再難懂的問題時間也可以解決，再易懂的問題也需要時間來解決，就是欠個火候或者稱之為時間之上的感覺，僅此而已。

接下來就是一串繁瑣的定義（神馬是動態(tài)規(guī)劃，額很無語的說，自己看吧）

動態(tài)規(guī)劃理念：

1.最優(yōu)化原理   1951年美國數學家R．Bellman等人，根據一類多階段問題的特點，把多階段決策問題變換為一系列互相聯系的單階段問題，然后逐個加以解決。一些靜態(tài)模型，只要人為地引進“時間”因素，分成時段，就可以轉化成多階段的動態(tài)模型，用動態(tài)規(guī)劃方法去處理。與此同時，他提出了解決這類問題的“最優(yōu)化原理”(PRinciple of optimality)：    “一個過程的最優(yōu)決策具有這樣的性質：即無論其初始狀態(tài)和初始決策如何，其今后諸策略對以第一個決策所形成的狀態(tài)作為初始狀態(tài)的過程而言，必須構成最優(yōu)策略”。簡言之，一個最優(yōu)策略的子策略，對于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。    這個“最優(yōu)化原理”如果用數學化一點的語言來描述的話，就是：假設為了解決某一優(yōu)化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優(yōu)的，對于任何一個整數k，1 < k < n，不論前面k個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當前狀態(tài)，即以后的決策Dk+1，Dk+2，…，Dn也是最優(yōu)的。    最優(yōu)化原理是動態(tài)規(guī)劃的基礎。任何一個問題，如果失去了這個最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。能采用動態(tài)規(guī)劃求解的問題都需要滿足一定的條件：     (1) 問題中的狀態(tài)必須滿足最優(yōu)化原理；    (2) 問題中的狀態(tài)必須滿足無后效性。    所謂的無后效性是指：“下一時刻的狀態(tài)只與當前狀態(tài)有關，而和當前狀態(tài)之前的狀態(tài)無關，當前的狀態(tài)是對以往決策的總結”。

2.問題求解模式     動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優(yōu)的活動路線)。如圖所示。動態(tài)規(guī)劃的設計都有著一定的模式，一般要經歷以下幾個步驟。  初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結束狀態(tài)    圖1 動態(tài)規(guī)劃決策過程示意圖    (1)劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。    (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。    (3)確定決策并寫出狀態(tài)轉移方程：因為決策和狀態(tài)轉移有著天然的聯系，狀態(tài)轉移就是根據上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態(tài)之間的關系來確定決策。    (4)尋找邊界條件：給出的狀態(tài)轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

3.實現   動態(tài)規(guī)劃的主要難點在于理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃三要素：問題的階段,每個階段的狀態(tài)以及從前一個階段轉化到后一個階段之間的遞推關系。遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態(tài)規(guī)劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢，這也是動態(tài)規(guī)劃算法的核心之處。確定了動態(tài)規(guī)劃的這三要素，整個求解過程就可以用一個最優(yōu)決策表來描述，最優(yōu)決策表是一個二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數據一般對應此問題的在某個階段某個狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優(yōu)解。下面分別以求解最大化投資回報問題和最長公共子序列問題為例闡述用動態(tài)規(guī)劃算法求解問題的一般思路。

個人覺得花時間讀這些東西不如給你一串代碼自己體會（自己寫的），其實有時候定義不一定是個好東西，它可以給人以方向也能把人給局限了。（做太多題不如自己自己分析問題）

DP（）

{

 Fomula（動（狀態(tài)）+思想+隨你嘍）；

}

來吧，宏觀看一下你所處的位置，放低姿態(tài)別以為自己懂得很多。

1，簡單dp；

1.遞推2.背包（0-1背包，完全背包，分組背包，多重背包）3.LIS 4.LCS

2，區(qū)間dp；

3，樹形dp；

4，數位dp；

5，概率（期望）dp；

6，狀態(tài)壓縮dp；

7，數據結構優(yōu)化的dp；

寫完之后發(fā)現我現在懂得真是冰山一角，so啥也別說了，謙虛點。