原文出處：https://blog.csdn.net/u013309870/article/details/75193592
前言
最近在判炷疲客網(wǎng)上做了幾套公司的真題皿桑，發(fā)現(xiàn)有關(guān)動態(tài)規(guī)劃（Dynamic Programming）算法的題目很多下面。相對于我來說钦购，算法里面遇到的問題里面感覺最難的也就是動態(tài)規(guī)劃（Dynamic Programming）算法了舟扎，于是花了好長時間粮呢，查找了相關(guān)的文獻和資料準備徹底的理解動態(tài)規(guī)劃（Dynamic Programming）算法伍玖。一是幫助自己總結(jié)知識點嫩痰，二是也能夠幫助他人更好的理解這個算法。后面的參考文獻只是我看到的文獻的一部分窍箍。
動態(tài)規(guī)劃算法的核心
理解一個算法就要理解一個算法的核心串纺，動態(tài)規(guī)劃算法的核心是下面的一張圖片和一個小故事。
A * "1+1+1+1+1+1+1+1 =椰棘？" *
A : "上面等式的值是多少"
B : *計算* "8!"
A *在上面等式的左邊寫上 "1+" *
A : "此時等式的值為多少"
B : *quickly* "9!"
A : "你怎么這么快就知道答案了"
A : "只要在8的基礎(chǔ)上加1就行了"
A : "所以你不用重新計算因為你記住了第一個等式的值為8!動態(tài)規(guī)劃算法也可以說是 '記住求過的解來節(jié)省時間'"
由上面的圖片和小故事可以知道動態(tài)規(guī)劃算法的核心就是記住已經(jīng)解決過的子問題的解纺棺。
動態(tài)規(guī)劃算法的兩種形式
上面已經(jīng)知道動態(tài)規(guī)劃算法的核心是記住已經(jīng)求過的解，記住求解的方式有兩種：①自頂向下的備忘錄法 ②自底向上邪狞。
為了說明動態(tài)規(guī)劃的這兩種方法祷蝌，舉一個最簡單的例子：求斐波拉契數(shù)列Fibonacci 。先看一下這個問題：
Fibonacci (n) = 1; n = 0
Fibonacci (n) = 1; n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)
以前學(xué)c語言的時候?qū)戇^這個算法使用遞歸十分的簡單帆卓。先使用遞歸版本來實現(xiàn)這個算法：
public int fib(int n)
{
if(n<=0)
return 0;
if(n==1)
return 1;
return fib( n-1)+fib(n-2);
}
//輸入6
//輸出：8
先來分析一下遞歸算法的執(zhí)行流程巨朦，假如輸入6，那么執(zhí)行的遞歸樹如下：
上面的遞歸樹中的每一個子節(jié)點都會執(zhí)行一次剑令，很多重復(fù)的節(jié)點被執(zhí)行糊啡，fib(2)被重復(fù)執(zhí)行了5次。由于調(diào)用每一個函數(shù)的時候都要保留上下文吁津，所以空間上開銷也不小棚蓄。這么多的子節(jié)點被重復(fù)執(zhí)行，如果在執(zhí)行的時候把執(zhí)行過的子節(jié)點保存起來碍脏，后面要用到的時候直接查表調(diào)用的話可以節(jié)約大量的時間梭依。下面就看看動態(tài)規(guī)劃的兩種方法怎樣來解決斐波拉契數(shù)列Fibonacci 數(shù)列問題。
①自頂向下的備忘錄法
public static int Fibonacci(int n)
{
if(n<=0)
return n;
int []Memo=new int[n+1];
for(int i=0;i<=n;i++)
Memo[i]=-1;
return fib(n, Memo);
}
public static int fib(int n,int []Memo)
{
if(Memo[n]!=-1)
return Memo[n];
//如果已經(jīng)求出了fib（n）的值直接返回典尾，否則將求出的值保存在Memo備忘錄中役拴。
if(n<=2)
Memo[n]=1;
else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);
return Memo[n];
}
備忘錄法也是比較好理解的，創(chuàng)建了一個n+1大小的數(shù)組來保存求出的斐波拉契數(shù)列中的每一個值急黎，在遞歸的時候如果發(fā)現(xiàn)前面fib（n）的值計算出來了就不再計算扎狱，如果未計算出來侧到，則計算出來后保存在Memo數(shù)組中，下次在調(diào)用fib（n）的時候就不會重新遞歸了淤击。比如上面的遞歸樹中在計算fib（6）的時候先計算fib（5）匠抗，調(diào)用fib（5）算出了fib（4）后，fib（6）再調(diào)用fib（4）就不會在遞歸fib（4）的子樹了污抬，因為fib（4）的值已經(jīng)保存在Memo[4]中汞贸。
②自底向上的動態(tài)規(guī)劃
備忘錄法還是利用了遞歸印机，上面算法不管怎樣矢腻，計算fib（6）的時候最后還是要計算出fib（1），fib（2）射赛，fib（3）……,那么何不先計算出fib（1）多柑，fib（2），fib（3）……,呢楣责？這也就是動態(tài)規(guī)劃的核心竣灌，先計算子問題，再由子問題計算父問題秆麸。
public static int fib(int n)
{
if(n<=0)
return n;
int []Memo=new int[n+1];
Memo[0]=0;
Memo[1]=1;
for(int i=2;i<=n;i++)
{
Memo[i]=Memo[i-1]+Memo[i-2];
}
return Memo[n];
}
自底向上方法也是利用數(shù)組保存了先計算的值初嘹，為后面的調(diào)用服務(wù)。觀察參與循環(huán)的只有 i沮趣，i-1 , i-2三項屯烦，因此該方法的空間可以進一步的壓縮如下。
public static int fib(int n)
{
if(n<=1)
return n;
int Memo_i_2=0;
int Memo_i_1=1;
int Memo_i=1;
for(int i=2;i<=n;i++)
{
Memo_i=Memo_i_2+Memo_i_1;
Memo_i_2=Memo_i_1;
Memo_i_1=Memo_i;
}
return Memo_i;
}
一般來說由于備忘錄方式的動態(tài)規(guī)劃方法使用了遞歸房铭，遞歸的時候會產(chǎn)生額外的開銷驻龟，使用自底向上的動態(tài)規(guī)劃方法要比備忘錄方法好。
你以為看懂了上面的例子就懂得了動態(tài)規(guī)劃嗎缸匪？那就too young too simple了迅脐。動態(tài)規(guī)劃遠遠不止如此簡單，下面先給出一個例子看看能否獨立完成豪嗽。然后再對動態(tài)規(guī)劃的其他特性進行分析。
動態(tài)規(guī)劃小試牛刀
例題：鋼條切割
上面的例題來自于算法導(dǎo)論
關(guān)于題目的講解就直接截圖算法導(dǎo)論書上了這里就不展開講⊥憧ィ現(xiàn)在使用一下前面講到三種方法來來實現(xiàn)一下龟梦。
①遞歸版本
public static int cut(int []p,int n)
{
if(n==0)
return 0;
int q=Integer.MIN_VALUE;
for(int i=1;i<=n;i++)
{
q=Math.max(q, p[i-1]+cut(p, n-i));
}
return q;
}
遞歸很好理解，如果不懂可以看上面的講解窃躲，遞歸的思路其實和回溯法是一樣的计贰，遍歷所有解空間但這里和上面斐波拉契數(shù)列的不同之處在于，在每一層上都進行了一次最優(yōu)解的選擇蒂窒，q=Math.max(q, p[i-1]+cut(p, n-i));這個段語句就是最優(yōu)解選擇躁倒，這里上一層的最優(yōu)解與下一層的最優(yōu)解相關(guān)荞怒。
②備忘錄版本
public static int cutMemo(int []p)
{
int []r=new int[p.length+1];
for(int i=0;i<=p.length;i++)
r[i]=-1;
return cut(p, p.length, r);
}
public static int cut(int []p,int n,int []r)
{
int q=-1;
if(r[n]>=0)
return r[n];
if(n==0)
q=0;
else {
for(int i=1;i<=n;i++)
q=Math.max(q, cut(p, n-i,r)+p[i-1]);
}
r[n]=q;
return q;
}
有了上面求斐波拉契數(shù)列的基礎(chǔ)，理解備忘錄方法也就不難了秧秉。備忘錄方法無非是在遞歸的時候記錄下已經(jīng)調(diào)用過的子函數(shù)的值褐桌。這道鋼條切割問題的經(jīng)典之處在于自底向上的動態(tài)規(guī)劃問題的處理，理解了這個也就理解了動態(tài)規(guī)劃的精髓象迎。
③自底向上的動態(tài)規(guī)劃
public static int buttom_up_cut(int []p)
{
int []r=new int[p.length+1];
for(int i=1;i<=p.length;i++)
{
int q=-1;
//①
for(int j=1;j<=i;j++)
q=Math.max(q, p[j-1]+r[i-j]);
r[i]=q;
}
return r[p.length];
}
自底向上的動態(tài)規(guī)劃問題中最重要的是理解注釋①處的循環(huán)荧嵌，這里外面的循環(huán)是求r[1],r[2]……，里面的循環(huán)是求出r[1],r[2]……的最優(yōu)解砾淌，也就是說r[i]中保存的是鋼條長度為i時劃分的最優(yōu)解啦撮，這里面涉及到了最優(yōu)子結(jié)構(gòu)問題，也就是一個問題取最優(yōu)解的時候汪厨，它的子問題也一定要取得最優(yōu)解赃春。下面是長度為4的鋼條劃分的結(jié)構(gòu)圖。我就偷懶截了個圖劫乱。
動態(tài)規(guī)劃原理
雖然已經(jīng)用動態(tài)規(guī)劃方法解決了上面兩個問題织中，但是大家可能還跟我一樣并不知道什么時候要用到動態(tài)規(guī)劃∫鳎總結(jié)一下上面的斐波拉契數(shù)列和鋼條切割問題抠璃，發(fā)現(xiàn)兩個問題都涉及到了重疊子問題，和最優(yōu)子結(jié)構(gòu)脱惰。
①最優(yōu)子結(jié)構(gòu)
用動態(tài)規(guī)劃求解最優(yōu)化問題的第一步就是刻畫最優(yōu)解的結(jié)構(gòu)搏嗡，如果一個問題的解結(jié)構(gòu)包含其子問題的最優(yōu)解，就稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)拉一。因此采盒，某個問題是否適合應(yīng)用動態(tài)規(guī)劃算法，它是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)是一個很好的線索蔚润。使用動態(tài)規(guī)劃算法時磅氨，用子問題的最優(yōu)解來構(gòu)造原問題的最優(yōu)解。因此必須考查最優(yōu)解中用到的所有子問題嫡纠。
②重疊子問題
在斐波拉契數(shù)列和鋼條切割結(jié)構(gòu)圖中烦租，可以看到大量的重疊子問題，比如說在求fib（6）的時候除盏，fib（2）被調(diào)用了5次叉橱，在求cut（4）的時候cut（0）被調(diào)用了4次。如果使用遞歸算法的時候會反復(fù)的求解相同的子問題者蠕，不停的調(diào)用函數(shù)窃祝，而不是生成新的子問題。如果遞歸算法反復(fù)求解相同的子問題踱侣，就稱為具有重疊子問題（overlapping subproblems）性質(zhì)粪小。在動態(tài)規(guī)劃算法中使用數(shù)組來保存子問題的解大磺，這樣子問題多次求解的時候可以直接查表不用調(diào)用函數(shù)遞歸。
動態(tài)規(guī)劃的經(jīng)典模型
線性模型
線性模型的是動態(tài)規(guī)劃中最常用的模型探膊，上文講到的鋼條切割問題就是經(jīng)典的線性模型杠愧，這里的線性指的是狀態(tài)的排布是呈線性的⊥幌耄【例題1】是一個經(jīng)典的面試題殴蹄，我們將它作為線性模型的敲門磚。
【例題1】在一個夜黑風(fēng)高的晚上猾担，有n（n <= 50）個小朋友在橋的這邊袭灯，現(xiàn)在他們需要過橋，但是由于橋很窄绑嘹，每次只允許不大于兩人通過稽荧，他們只有一個手電筒，所以每次過橋的兩個人需要把手電筒帶回來工腋，i號小朋友過橋的時間為T[i]姨丈，兩個人過橋的總時間為二者中時間長者。問所有小朋友過橋的總時間最短是多少擅腰。
每次過橋的時候最多兩個人蟋恬，如果橋這邊還有人，那么還得回來一個人（送手電筒）趁冈，也就是說N個人過橋的次數(shù)為2*N-3（倒推歼争，當(dāng)橋這邊只剩兩個人時只需要一次，三個人的情況為來回一次后加上兩個人的情況…）渗勘。有一個人需要來回跑沐绒，將手電筒送回來（也許不是同一個人，realy旺坠？Ｇ钦凇）這個回來的時間是沒辦法省去的，并且回來的次數(shù)也是確定的取刃，為N-2蹋肮，如果是我，我會選擇讓跑的最快的人來干這件事情璧疗，但是我錯了…如果總是跑得最快的人跑回來的話括尸，那么他在每次別人過橋的時候一定得跟過去，于是就變成就是很簡單的問題了病毡，花費的總時間：
T = minPTime * (N-2) + (totalSum-minPTime)
來看一組數(shù)據(jù) 四個人過橋花費的時間分別為 1 2 5 10，按照上面的公式答案是19屁柏，但是實際答案應(yīng)該是17啦膜。
具體步驟是這樣的：
第一步：1和2過去有送，花費時間2，然后1回來（花費時間1）僧家；
第二歩：3和4過去雀摘，花費時間10，然后2回來（花費時間2）八拱；
第三部：1和2過去阵赠，花費時間2，總耗時17肌稻。
所以之前的貪心想法是不對的清蚀。我們先將所有人按花費時間遞增進行排序，假設(shè)前i個人過河花費的最少時間為opt[i]爹谭，那么考慮前i-1個人過河的情況枷邪，即河這邊還有1個人，河那邊有i-1個人诺凡，并且這時候手電筒肯定在對岸东揣，所以opt[i] = opt[i-1] + a[1] + a[i] (讓花費時間最少的人把手電筒送過來，然后和第i個人一起過河)如果河這邊還有兩個人腹泌，一個是第i號嘶卧，另外一個無所謂，河那邊有i-2個人凉袱，并且手電筒肯定在對岸芥吟，所以opt[i] = opt[i-2] + a[1] + a[i] + 2a[2] (讓花費時間最少的人把電筒送過來，然后第i個人和另外一個人一起過河绑蔫，由于花費時間最少的人在這邊运沦，所以下一次送手電筒過來的一定是花費次少的，送過來后花費最少的和花費次少的一起過河配深，解決問題)
所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2a[2] }
區(qū)間模型
區(qū)間模型的狀態(tài)表示一般為d[i][j]携添，表示區(qū)間[i, j]上的最優(yōu)解，然后通過狀態(tài)轉(zhuǎn)移計算出[i+1, j]或者[i, j+1]上的最優(yōu)解篓叶，逐步擴大區(qū)間的范圍烈掠，最終求得[1, len]的最優(yōu)解。
【例題2】給定一個長度為n（n <= 1000）的字符串A缸托，求插入最少多少個字符使得它變成一個回文串左敌。
典型的區(qū)間模型，回文串擁有很明顯的子結(jié)構(gòu)特征俐镐，即當(dāng)字符串X是一個回文串時矫限，在X兩邊各添加一個字符’a’后，aXa仍然是一個回文串，我們用d[i][j]來表示A[i…j]這個子串變成回文串所需要添加的最少的字符數(shù)叼风，那么對于A[i] == A[j]的情況取董，很明顯有 d[i][j] = d[i+1][j-1] （這里需要明確一點，當(dāng)i+1 > j-1時也是有意義的无宿，它代表的是空串茵汰，空串也是一個回文串，所以這種情況下d[i+1][j-1] = 0）孽鸡；當(dāng)A[i] != A[j]時蹂午，我們將它變成更小的子問題求解，我們有兩種決策：
1彬碱、在A[j]后面添加一個字符A[i]豆胸；
2、在A[i]前面添加一個字符A[j]堡妒；
根據(jù)兩種決策列出狀態(tài)轉(zhuǎn)移方程為：
d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; (每次狀態(tài)轉(zhuǎn)移配乱，區(qū)間長度增加1)
空間復(fù)雜度O(n2)，時間復(fù)雜度O(n2)皮迟， 下文會提到將空間復(fù)雜度降為O(n)的優(yōu)化算法搬泥。
背包模型
背包問題是動態(tài)規(guī)劃中一個最典型的問題之一。由于網(wǎng)上有非常詳盡的背包講解伏尼，這里只將常用部分抽出來忿檩。
【例題3】有N種物品（每種物品1件）和一個容量為V的背包。放入第 i 種物品耗費的空間是Ci爆阶，得到的價值是Wi燥透。求解將哪些物品裝入背包可使價值總和最大。f[i][v]表示前i種物品恰好放入一個容量為v的背包可以獲得的最大價值辨图。決策為第i個物品在前i-1個物品放置完畢后班套，是選擇放還是不放，狀態(tài)轉(zhuǎn)移方程為：
f[i][v] = max{ f[i-1][v], f[i-1][v – Ci] +Wi }
時間復(fù)雜度O(VN)故河，空間復(fù)雜度O(VN) （空間復(fù)雜度可利用滾動數(shù)組進行優(yōu)化達到O(V) ）吱韭。
動態(tài)規(guī)劃題集整理
1、最長單調(diào)子序列
Constructing Roads In JG Kingdom★★☆☆☆
Stock Exchange ★★☆☆☆
2鱼的、最大M子段和
Max Sum ★☆☆☆☆
最長公共子串 ★★☆☆☆
3理盆、線性模型
Skiing ★☆☆☆☆
總結(jié)
弄懂動態(tài)規(guī)劃問題的基本原理和動態(tài)規(guī)劃問題的幾個常見的模型，對于解決大部分的問題已經(jīng)足夠了凑阶。希望能對大家有所幫助猿规，轉(zhuǎn)載請標明出處http://write.blog.csdn.net/mdeditor#!postId=75193592，創(chuàng)作實在不容易宙橱，這篇博客花了我將近一個星期的時間姨俩。
參考文獻
1.算法導(dǎo)論
