1. 導(dǎo)入

2. DP可解

??確認(rèn)一個(gè)問(wèn)題是否DP可解是使用DP算法前最重要的一步。

2.1 相關(guān)概念

??狀態(tài)：內(nèi)存中存儲(chǔ)的變量構(gòu)成了計(jì)算機(jī)當(dāng)前的狀態(tài)。
??狀態(tài)轉(zhuǎn)移：如何由當(dāng)前狀態(tài)計(jì)算出下一時(shí)刻的狀態(tài)。
??空間復(fù)雜度：空間復(fù)雜度是由狀態(tài)和狀態(tài)轉(zhuǎn)移計(jì)算所需的變量空間決定的。
??時(shí)間復(fù)雜度：時(shí)間復(fù)雜度由開始的狀態(tài)到最終的狀態(tài)決定的。
??階段：隨著問(wèn)題的解決，在同一個(gè)時(shí)刻可能會(huì)得到的不同狀態(tài)的集合。舉個(gè)例子，假如把你放在一個(gè)圍棋棋盤上的某一點(diǎn)，你每一步只能走一格，因?yàn)槟憧梢詵|南西北隨便走，所以你當(dāng)你同樣走四步可能會(huì)處于很多個(gè)不同的位置。從頭開始走了幾步就是第幾個(gè)階段，走了n步可能處于的位置稱為一個(gè)狀態(tài)，走了這n步所有可能到達(dá)的位置的集合就是這個(gè)階段下所有可能的狀態(tài)。
??后效性：之前的路線會(huì)影響下一步的選擇，這稱為后效性。

2.2 不同階段引出的不同算法

??假如問(wèn)題有n個(gè)階段，每個(gè)階段都有多個(gè)狀態(tài)，不同階段的狀態(tài)數(shù)不必相同，一個(gè)階段的一個(gè)狀態(tài)可以得到下個(gè)階段的所有狀態(tài)中的幾個(gè)。那我們要計(jì)算出最終階段的狀態(tài)數(shù)自然要經(jīng)歷之前每個(gè)階段的某些狀態(tài)。
??一個(gè)問(wèn)題是該用遞推、貪心、搜索還是動(dòng)態(tài)規(guī)劃，完全是由這個(gè)問(wèn)題本身階段間狀態(tài)的轉(zhuǎn)移方式?jīng)Q定的。

2.2.1 遞推：每個(gè)階段只有一個(gè)狀態(tài)

2.2.2 貪心：每個(gè)階段的最優(yōu)狀態(tài)都是由上一個(gè)階段的最優(yōu)狀態(tài)得到的

??貪心算法是動(dòng)態(tài)規(guī)劃的一個(gè)特例。

2.2.3 搜索：每個(gè)階段的最優(yōu)狀態(tài)是由之前所有階段的狀態(tài)的組合得到的

2.2.4 動(dòng)態(tài)規(guī)劃：每個(gè)階段的最優(yōu)狀態(tài)可以從之前某個(gè)階段的某個(gè)或某些狀態(tài)直接得到而不管之前這個(gè)狀態(tài)是如何得到的

??每個(gè)階段的最優(yōu)狀態(tài)可以從之前某個(gè)階段的某個(gè)或某些狀態(tài)直接得到，這個(gè)性質(zhì)叫最優(yōu)子結(jié)構(gòu)，能寫出狀態(tài)轉(zhuǎn)移方程的就說(shuō)明滿足最優(yōu)子結(jié)構(gòu)。
??而不管之前這個(gè)狀態(tài)是如何得到的，這個(gè)性質(zhì)叫無(wú)后效性。
??動(dòng)態(tài)規(guī)劃是最優(yōu)化情況下的分治算法，如何拆分問(wèn)題，定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系，使得問(wèn)題能夠以遞推（或者說(shuō)分治）的方式去解決是動(dòng)態(tài)規(guī)劃的關(guān)鍵。拆分問(wèn)題靠的就是狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的定義。
??狀態(tài)：
??狀態(tài)轉(zhuǎn)移方程：

3. DP經(jīng)典問(wèn)題

3.1 斐波那契數(shù)列

3.2 最大上升子序列

??給定一個(gè)數(shù)列，長(zhǎng)度為N，求這個(gè)數(shù)列的最長(zhǎng)上升（遞增）子數(shù)列（LIS）的長(zhǎng)度.
??以1 7 2 8 3 4為例：
??這個(gè)數(shù)列的最長(zhǎng)遞增子數(shù)列是 1 2 3 4，長(zhǎng)度為4；
??次長(zhǎng)的長(zhǎng)度為3， 包括 1 7 8; 1 2 3 等.

3.3 背包問(wèn)題

??背包問(wèn)題是經(jīng)典的NP完全問(wèn)題，背包容量為不太大的整數(shù)時(shí)可以使用DP算法求解背包問(wèn)題。

3.4 其他問(wèn)題

??背包問(wèn)題. (poj1837,poj1276)
??型如下表的簡(jiǎn)單DP(可參考lrj的書 page149):
??E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
??E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長(zhǎng)公共子序列) (poj3176,poj1080,poj1159)
??C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹問(wèn)題)
??較為復(fù)雜的動(dòng)態(tài)規(guī)劃(如動(dòng)態(tài)規(guī)劃解特別的旅行商TSP問(wèn)題（poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034）
??記錄狀態(tài)的動(dòng)態(tài)規(guī)劃. (POJ3254,poj2411,poj1185)
??樹型動(dòng)態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)
??需要用數(shù)據(jù)結(jié)構(gòu)優(yōu)化的動(dòng)態(tài)規(guī)劃.(poj2754,poj3378,poj3017)
??四邊形不等式理論.較難的狀態(tài)DP(poj3133)

4. 參考資料

https://www.zhihu.com/question/23995189/answer/35429905
https://www.zhihu.com/question/52165201
https://www.zhihu.com/question/38213967/answer/77586917