March 26, 2013
作者：Hawstein
出處：http://hawstein.com/posts/dp-novice-to-advanced.html
聲明：本文采用以下協(xié)議進行授權(quán)：自由轉(zhuǎn)載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0图云，轉(zhuǎn)載請注明作者及出處芳誓。
前言
本文翻譯自TopCoder上的一篇文章：Dynamic Programming: From novice to advanced奄侠，并非嚴(yán)格逐字逐句翻譯熙暴，其中加入了自己的一些理解铃岔。水平有限，還望指摘。
前言_
我們遇到的問題中，有很大一部分可以用動態(tài)規(guī)劃(簡稱DP)來解紧显。 解決這類問題可以很大地提升你的能力與技巧，我會試著幫助你理解如何使用DP來解題缕棵。 這篇文章是基于實例展開來講的孵班，因為干巴巴的理論實在不好理解涉兽。
注意：如果你對于其中某一節(jié)已經(jīng)了解并且不想閱讀它，沒關(guān)系篙程，直接跳過它即可枷畏。
簡介(入門)
什么是動態(tài)規(guī)劃，我們要如何描述它?
動態(tài)規(guī)劃算法通呈觯基于一個遞推公式及一個或多個初始狀態(tài)拥诡。 當(dāng)前子問題的解將由上一次子問題的解推出。使用動態(tài)規(guī)劃來解題只需要多項式時間復(fù)雜度郭厌， 因此它比回溯法、暴力法等要快許多雕蔽。
現(xiàn)在讓我們通過一個例子來了解一下DP的基本原理折柠。
首先，我們要找到某個狀態(tài)的最優(yōu)解批狐，然后在它的幫助下扇售，找到下一個狀態(tài)的最優(yōu)解。
“狀態(tài)”代表什么及如何找到它?
“狀態(tài)"用來描述該問題的子問題的解嚣艇。原文中有兩段作者闡述得不太清楚承冰，跳過直接上例子。
如果我們有面值為1元食零、3元和5元的硬幣若干枚困乒，如何用最少的硬幣湊夠11元？ (表面上這道題可以用貪心算法贰谣，但貪心算法無法保證可以求出解娜搂，比如1元換成2元的時候)
首先我們思考一個問題，如何用最少的硬幣湊夠i元(i<11)吱抚？為什么要這么問呢百宇？ 兩個原因：1.當(dāng)我們遇到一個大問題時，總是習(xí)慣把問題的規(guī)模變小秘豹，這樣便于分析討論携御。 2.這個規(guī)模變小后的問題和原來的問題是同質(zhì)的，除了規(guī)模變小既绕，其它的都是一樣的啄刹， 本質(zhì)上它還是同一個問題(規(guī)模變小后的問題其實是原問題的子問題)。
好了凄贩，讓我們從最小的i開始吧鸵膏。當(dāng)i=0，即我們需要多少個硬幣來湊夠0元怎炊。 由于1谭企，3廓译，5都大于0，即沒有比0小的幣值债查，因此湊夠0元我們最少需要0個硬幣非区。 (這個分析很傻是不是？別著急盹廷，這個思路有利于我們理清動態(tài)規(guī)劃究竟在做些什么征绸。) 這時候我們發(fā)現(xiàn)用一個標(biāo)記來表示這句“湊夠0元我們最少需要0個硬幣《碚迹”會比較方便管怠， 如果一直用純文字來表述，不出一會兒你就會覺得很繞了缸榄。那么渤弛， 我們用d(i)=j來表示湊夠i元最少需要j個硬幣。于是我們已經(jīng)得到了d(0)=0甚带， 表示湊夠0元最小需要0個硬幣她肯。當(dāng)i=1時，只有面值為1元的硬幣可用鹰贵， 因此我們拿起一個面值為1的硬幣晴氨，接下來只需要湊夠0元即可，而這個是已經(jīng)知道答案的碉输， 即d(0)=0籽前。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1敷钾。當(dāng)i=2時聚假， 仍然只有面值為1的硬幣可用，于是我拿起一個面值為1的硬幣闰非， 接下來我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數(shù)量)膘格，而這個答案也已經(jīng)知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2财松。一直到這里瘪贱，你都可能會覺得，好無聊辆毡， 感覺像做小學(xué)生的題目似的菜秦。因為我們一直都只能操作面值為1的硬幣！耐心點舶掖， 讓我們看看i=3時的情況球昨。當(dāng)i=3時，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用眨攘，因為你需要湊的數(shù)目是3元主慰！5元太多了親)嚣州。 既然能用的硬幣有兩種，我就有兩種方案共螺。如果我拿了一個1元的硬幣该肴，我的目標(biāo)就變?yōu)榱耍?湊夠3-1=2元需要的最少硬幣數(shù)量。即d(3)=d(3-1)+1=d(2)+1=2+1=3藐不。 這個方案說的是匀哄，我拿3個1元的硬幣；第二種方案是我拿起一個3元的硬幣雏蛮， 我的目標(biāo)就變成：湊夠3-3=0元需要的最少硬幣數(shù)量涎嚼。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個方案說的是，我拿1個3元的硬幣挑秉。好了法梯，這兩種方案哪種更優(yōu)呢？ 記得我們可是要用最少的硬幣數(shù)量來湊夠3元的衷模。所以鹊汛， 選擇d(3)=1蒲赂，怎么來的呢阱冶？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。
OK滥嘴，碼了這么多字講具體的東西木蹬，讓我們來點抽象的。從以上的文字中若皱， 我們要抽出動態(tài)規(guī)劃里非常重要的兩個概念：狀態(tài)和狀態(tài)轉(zhuǎn)移方程镊叁。
上文中d(i)表示湊夠i元需要的最少硬幣數(shù)量，我們將它定義為該問題的"狀態(tài)"走触， 這個狀態(tài)是怎么找出來的呢晦譬？我在另一篇文章動態(tài)規(guī)劃之背包問題(一)中寫過： 根據(jù)子問題定義狀態(tài)。你找到子問題互广，狀態(tài)也就浮出水面了敛腌。 最終我們要求解的問題，可以用這個狀態(tài)來表示：d(11)惫皱，即湊夠11元最少需要多少個硬幣像樊。 那狀態(tài)轉(zhuǎn)移方程是什么呢？既然我們用d(i)表示狀態(tài)旅敷，那么狀態(tài)轉(zhuǎn)移方程自然包含d(i)生棍， 上文中包含狀態(tài)d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。沒錯媳谁， 它就是狀態(tài)轉(zhuǎn)移方程涂滴，描述狀態(tài)之間是如何轉(zhuǎn)移的友酱。當(dāng)然，我們要對它抽象一下氢妈，
d(i)=min{ d(i-vj)+1 }粹污，其中i-vj>=0，vj表示第j個硬幣的面值;
有了狀態(tài)和狀態(tài)轉(zhuǎn)移方程首量，這個問題基本上也就解決了壮吩。當(dāng)然了，Talk is cheap,show me the code!
偽代碼如下：
下圖是當(dāng)i從0到11時的解：
從上圖可以得出加缘，要湊夠11元至少需要3枚硬幣鸭叙。
此外，通過追蹤我們是如何從前一個狀態(tài)值得到當(dāng)前狀態(tài)值的拣宏， 可以找到每一次我們用的是什么面值的硬幣沈贝。比如，從上面的圖我們可以看出勋乾， 最終結(jié)果d(11)=d(10)+1(面值為1)宋下，而d(10)=d(5)+1(面值為5)，最后d(5)=d(0)+1 (面值為5)辑莫。所以我們湊夠11元最少需要的3枚硬幣是：1元学歧、5元、5元各吨。
注意：原文中這里本來還有一段的枝笨，但我反反復(fù)復(fù)讀了幾遍， 大概的意思我已經(jīng)在上文從i=0到i=3的分析中有所體現(xiàn)了揭蜒。作者本來想講的通俗一些横浑， 結(jié)果沒寫好，反而更不好懂屉更，所以這段不翻譯了徙融。
初級
上面討論了一個非常簡單的例子。現(xiàn)在讓我們來看看對于更復(fù)雜的問題瑰谜， 如何找到狀態(tài)之間的轉(zhuǎn)移方式(即找到狀態(tài)轉(zhuǎn)移方程)欺冀。 為此我們要引入一個新詞叫遞推關(guān)系來將狀態(tài)聯(lián)系起來(說的還是狀態(tài)轉(zhuǎn)移方程)
OK，上例子似舵，看看它是如何工作的脚猾。
一個序列有N個數(shù)：A[1],A[2],…,A[N]，求出最長非降子序列的長度砚哗。 (講DP基本都會講到的一個問題LIS：longest increasing subsequence)
正如上面我們講的龙助，面對這樣一個問題，我們首先要定義一個“狀態(tài)”來代表它的子問題， 并且找到它的解提鸟。注意军援，大部分情況下，某個狀態(tài)只與它前面出現(xiàn)的狀態(tài)有關(guān)称勋， 而獨立于后面的狀態(tài)胸哥。
讓我們沿用“入門”一節(jié)里那道簡單題的思路來一步步找到“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”。 假如我們考慮求A[1],A[2],…,A[i]的最長非降子序列的長度赡鲜，其中i
為了方便理解我們是如何找到狀態(tài)轉(zhuǎn)移方程的空厌，我先把下面的例子提到前面來講。 如果我們要求的這N個數(shù)的序列是：
5银酬，3嘲更，4，8揩瞪，6赋朦，7
根據(jù)上面找到的狀態(tài)，我們可以得到：（下文的最長非降子序列都用LIS表示）
前1個數(shù)的LIS長度d(1)=1(序列：5)
前2個數(shù)的LIS長度d(2)=1(序列：3李破；3前面沒有比3小的)
前3個數(shù)的LIS長度d(3)=2(序列：3楞遏，4蔽挠；4前面有個比它小的3陆淀，所以d(3)=d(2)+1)
前4個數(shù)的LIS長度d(4)=3(序列：3彼哼，4劈彪，8奠衔；8前面比它小的有3個數(shù)抄谐，所以 d(4)=max{d(1),d(2),d(3)}+1=3)
OK宁赤，分析到這惊畏，我覺得狀態(tài)轉(zhuǎn)移方程已經(jīng)很明顯了恶耽，如果我們已經(jīng)求出了d(1)到d(i-1)， 那么d(i)可以用下面的狀態(tài)轉(zhuǎn)移方程得到：
d(i) = max{1, d(j)+1},其中j
用大白話解釋就是颜启，想要求d(i)偷俭，就把i前面的各個子序列中， 最后一個數(shù)不大于A[i]的序列長度加1缰盏，然后取出最大的長度即為d(i)涌萤。 當(dāng)然了，有可能i前面的各個子序列中最后一個數(shù)都大于A[i]口猜，那么d(i)=1负溪， 即它自身成為一個長度為1的子序列。
分析完了济炎，上圖：(第二列表示前i個數(shù)中LIS的長度川抡， 第三列表示，LIS中到達(dá)當(dāng)前這個數(shù)的上一個數(shù)的下標(biāo)须尚，根據(jù)這個可以求出LIS序列)
Talk is cheap, show me the code:
#include usingnamespacestd;intlis(intA[],intn){int*d=newint[n];intlen=1;for(inti=0;id[i])d[i]=d[j]+1;if(d[i]>len)len=d[i];}delete[]d;returnlen;}intmain(){intA[]={5,3,4,8,6,7};cout<
該算法的時間復(fù)雜度是O(n2)崖堤，并不是最優(yōu)的解法侍咱。 還有一種很巧妙的算法可以將時間復(fù)雜度降到O(nlogn)，網(wǎng)上已經(jīng)有各種文章介紹它密幔， 這里就不再贅述楔脯。傳送門：LIS的O(nlogn)解法。 此題還可以用“排序+LCS”來解胯甩，感興趣的話可自行Google昧廷。
練習(xí)題
無向圖G有N個結(jié)點(1
提示：在每一步中，對于那些沒有計算過的結(jié)點偎箫， 及那些已經(jīng)計算出從結(jié)點1到它的最短路徑的結(jié)點麸粮，如果它們間有邊， 則計算從結(jié)點1到未計算結(jié)點的最短路徑镜廉。
嘗試解決以下來自topcoder競賽的問題：
ZigZag- 2003 TCCC Semifinals 3
BadNeighbors- 2004 TCCC Round 4
FlowerGarden- 2004 TCCC Round 1
中級
接下來弄诲，讓我們來看看如何解決二維的DP問題。
平面上有N*M個格子娇唯，每個格子中放著一定數(shù)量的蘋果齐遵。你從左上角的格子開始， 每一步只能向下走或是向右走塔插，每次走到一個格子上就把格子里的蘋果收集起來梗摇， 這樣下去，你最多能收集到多少個蘋果想许。
解這個問題與解其它的DP問題幾乎沒有什么兩樣伶授。第一步找到問題的“狀態(tài)”， 第二步找到“狀態(tài)轉(zhuǎn)移方程”流纹，然后基本上問題就解決了糜烹。
首先，我們要找到這個問題中的“狀態(tài)”是什么漱凝？我們必須注意到的一點是疮蹦， 到達(dá)一個格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。 因此為了求出到達(dá)當(dāng)前格子后最多能收集到多少個蘋果茸炒， 我們就要先去考察那些能到達(dá)當(dāng)前這個格子的格子愕乎，到達(dá)它們最多能收集到多少個蘋果。 (是不是有點繞壁公，但這句話的本質(zhì)其實是DP的關(guān)鍵：欲求問題的解感论，先要去求子問題的解)
經(jīng)過上面的分析，很容易可以得出問題的狀態(tài)和狀態(tài)轉(zhuǎn)移方程紊册。 狀態(tài)S[i][j]表示我們走到(i, j)這個格子時比肄，最多能收集到多少個蘋果。那么， 狀態(tài)轉(zhuǎn)移方程如下：
S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)
其中i代表行薪前，j代表列润努，下標(biāo)均從0開始；A[i][j]代表格子(i, j)處的蘋果數(shù)量示括。
S[i][j]有兩種計算方式：1.對于每一行铺浇，從左向右計算，然后從上到下逐行處理垛膝；2. 對于每一列鳍侣，從上到下計算，然后從左向右逐列處理吼拥。 這樣做的目的是為了在計算S[i][j]時倚聚，S[i-1][j]和S[i][j-1]都已經(jīng)計算出來了。
偽代碼如下：
以下兩道題來自topcoder凿可，練習(xí)用的惑折。
AvoidRoads- 2003 TCO Semifinals 4
ChessMetric- 2003 TCCC Round 4
中高級
這一節(jié)要討論的是帶有額外條件的DP問題。
以下的這個問題是個很好的例子枯跑。
無向圖G有N個結(jié)點惨驶，它的邊上帶有正的權(quán)重值。
你從結(jié)點1開始走敛助，并且一開始的時候你身上帶有M元錢粗卜。如果你經(jīng)過結(jié)點i， 那么你就要花掉S[i]元(可以把這想象為收過路費)纳击。如果你沒有足夠的錢续扔， 就不能從那個結(jié)點經(jīng)過。在這樣的限制條件下焕数，找到從結(jié)點1到結(jié)點N的最短路徑纱昧。 或者輸出該路徑不存在。如果存在多條最短路徑百匆，那么輸出花錢數(shù)量最少的那條砌些。 限制：1
偽代碼：
下面有幾道topcoder上的題以供練習(xí)：
Jewelry- 2003 TCO Online Round 4
StripePainter- SRM 150 Div 1
QuickSums- SRM 197 Div 2
ShortPalindromes- SRM 165 Div 2
高級
以下問題需要仔細(xì)的揣摩才能將其規(guī)約為可用DP解的問題呜投。
問題：StarAdventure- SRM 208 Div 1:
給定一個M行N列的矩陣(M*N個格子)加匈，每個格子中放著一定數(shù)量的蘋果。 你從左上角的格子開始仑荐，只能向下或向右走雕拼，目的地是右下角的格子。 你每走過一個格子粘招，就把格子上的蘋果都收集起來啥寇。然后你從右下角走回左上角的格子， 每次只能向左或是向上走，同樣的辑甜，走過一個格子就把里面的蘋果都收集起來衰絮。 最后，你再一次從左上角走到右下角磷醋，每過一個格子同樣要收集起里面的蘋果 (如果格子里的蘋果數(shù)為0猫牡，就不用收集)。求你最多能收集到多少蘋果邓线。
注意：當(dāng)你經(jīng)過一個格子時淌友，你要一次性把格子里的蘋果都拿走。
限制條件：1 < N, M <= 50骇陈；每個格子里的蘋果數(shù)量是0到1000(包含0和1000)震庭。
如果我們只需要從左上角的格子走到右下角的格子一次，并且收集最大數(shù)量的蘋果你雌， 那么問題就退化為“中級”一節(jié)里的那個問題器联。將這里的問題規(guī)約為“中級”里的簡單題， 這樣一來會比較好解婿崭。讓我們來分析一下這個問題主籍，要如何規(guī)約或是修改才能用上DP。 首先逛球，對于第二次從右下角走到左上角得出的這條路徑千元， 我們可以將它視為從左上角走到右下角得出的路徑，沒有任何的差別颤绕。 (即從B走到A的最優(yōu)路徑和從A走到B的最優(yōu)路徑是一樣的)通過這種方式幸海， 我們得到了三條從頂走到底的路徑。對于這一點的理解可以稍微減小問題的難度奥务。 于是物独，我們可以將這3條路徑記為左，中氯葬，右路徑挡篓。對于兩條相交路徑(如下圖)：
在不影響結(jié)果的情況下，我們可以將它們視為兩條不相交的路徑：
這樣一來帚称，我們將得到左官研，中，右3條路徑闯睹。此外戏羽，如果我們要得到最優(yōu)解， 路徑之間不能相交(除了左上角和右下角必然會相交的格子)楼吃。因此對于每一行y( 除了第一行和最后一行)始花，三條路徑對應(yīng)的x坐標(biāo)要滿足：x1[y] < x2[y] < x3[y]妄讯。 經(jīng)過這一步的分析，問題的DP解法就進一步地清晰了酷宵。讓我們考慮行y亥贸， 對于每一個x1[y-1]，x2[y-1]和x3[y-1]浇垦，我們已經(jīng)找到了能收集到最多蘋果數(shù)量的路徑砌函。 根據(jù)它們，我們能求出行y的最優(yōu)解×镒澹現(xiàn)在我們要做的就是找到從一行移動到下一行的方式讹俊。 令Max[i][j][k]表示到第y-1行為止收集到蘋果的最大數(shù)量， 其中3條路徑分別止于第i,j,k列煌抒。對于下一行y仍劈，對每個Max[i][j][k] 都加上格子(y,i)，(y,j)和(y,k)內(nèi)的蘋果數(shù)量寡壮。因此贩疙，每一步我們都向下移動。 我們做了這一步移動之后况既，還要考慮到这溅，一條路徑是有可能向右移動的。 (對于每一個格子棒仍，我們有可能是從它上面向下移動到它悲靴， 也可能是從它左邊向右移動到它)。為了保證3條路徑互不相交莫其， 我們首先要考慮左邊的路徑向右移動的情況癞尚，然后是中間，最后是右邊的路徑乱陡。 為了更好的理解浇揩，讓我們來考慮左邊的路徑向右移動的情況，對于每一個可能的j,k對(j
用于練習(xí)的topcoder題目：
MiniPaint- SRM 178 Div 1
其它
當(dāng)閱讀一個題目并且開始嘗試解決它時憨颠，首先看一下它的限制胳徽。 如果要求在多項式時間內(nèi)解決，那么該問題就很可能要用DP來解爽彤。遇到這種情況养盗， 最重要的就是找到問題的“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”。(狀態(tài)不是隨便定義的淫茵， 一般定義完狀態(tài)爪瓜，你要找到當(dāng)前狀態(tài)是如何從前面的狀態(tài)得到的， 即找到狀態(tài)轉(zhuǎn)移方程)如果看起來是個DP問題匙瘪，但你卻無法定義出狀態(tài)铆铆， 那么試著將問題規(guī)約到一個已知的DP問題(正如“高級”一節(jié)中的例子一樣)。
后記
看完這教程離DP專家還差得遠(yuǎn)丹喻，好好coding才是王道薄货。
