1、動(dòng)態(tài)規(guī)劃：從新手到專家March 26, 2013作者：Hawstein出處： HYPERLINK /posts/dp-novice-to-advanced.html /posts/dp-novice-to-advanced.html聲明：本文采用以下協(xié)議進(jìn)行授權(quán)：自由轉(zhuǎn)載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0，轉(zhuǎn)載請(qǐng)注明作者及出處。刖言本文翻譯自TopCoder上的一篇文章：Dynamic Programming: Fromnovice to advanced，并非嚴(yán)格逐字逐句翻譯，其中加入了自己的一些理解。水平有限，還望指摘。刖言我們遇到的問

2、題中，有很大一部分可以用動(dòng)態(tài)規(guī)劃（簡(jiǎn)稱DP）來解。解決這 類問題可以很大地提升你的能力與技巧，我會(huì)試著幫助你理解如何使用DP 來解題。這篇文章是基于實(shí)例展開來講的，因?yàn)楦砂桶偷睦碚搶?shí)在不好理 解。注意：如果你對(duì)于其中某一節(jié)已經(jīng)了解并且不想閱讀它，沒關(guān)系，直接跳 過它即可。簡(jiǎn)介（入門）什么是動(dòng)態(tài)規(guī)劃，我們要如何描述它？動(dòng)態(tài)規(guī)劃算法通常基于一個(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)。當(dāng)前子問題 的解將由上一次子問題的解推出。使用動(dòng)態(tài)規(guī)劃來解題只需要多項(xiàng)式時(shí)間 復(fù)雜度，因此它比回溯法、暴力法等要快許多。現(xiàn)在讓我們通過一個(gè)例子來了解一下DP的基本原理。首先，我們要找到某個(gè)狀態(tài)的最優(yōu)解，然后在它的幫助下，找到下一

3、個(gè)狀 態(tài)的最優(yōu)解。“狀態(tài)”代表什么及如何找到它？狀態(tài)用來描述該問題的子問題的解。原文中有兩段作者闡述得不太清楚， 跳過直接上例子。如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠 11元？（表面上這道題可以用貪心算法，但貪心算法無法保證可以求出解， 比如1元換成2元的時(shí)候）首先我們思考一個(gè)問題，如何用最少的硬幣湊夠1元（i=0，vj表示狗個(gè)硬幣的面值;有了狀態(tài)和狀態(tài)轉(zhuǎn)移方程，這個(gè)問題基本上也就解決了。當(dāng)然了，Talk is cheap,show me the code!偽代碼如下：Set Min ： i eqj己I to infinity far 己 11 of Mir0：=

4、0For i = 1 to SF二 = 0 to N - _If (Yj = i AND Mini-V-LMin i) Ther. Hir. 1 =Mi?. i-V-1Output Min.S下圖是當(dāng)i從0到11時(shí)的解:SumMin. nr. of coins.Coin value added fo a smaller sum to obtain this sum (R Is. display&d In brackets)D011221313(0)421向515(0)623(3)73件）a2押9311025(5)1131 (10)從上圖可以得出，要湊夠11元至少需要3枚硬幣。此外，通過追蹤我們

5、是如何從前一個(gè)狀態(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é)果沒寫好，反而更不好懂，所以這段不翻譯了。初級(jí)上面討論了一個(gè)非常簡(jiǎn)單的例子。現(xiàn)在讓我們來看看對(duì)于更復(fù)雜的問題， 如何找到狀態(tài)之間的轉(zhuǎn)移方式(即找到狀態(tài)轉(zhuǎn)

6、移方程)。為此我們要引入一 個(gè)新詞叫遞推關(guān)系來將狀態(tài)聯(lián)系起來(說的還是狀態(tài)轉(zhuǎn)移方程)OK，上例子，看看它是如何工作的。一個(gè)序列有N個(gè)數(shù)：A1,A2,.,AN，求出最長(zhǎng)非降子序列的長(zhǎng)度。(講DP基本都會(huì)講到的一個(gè)問題LIS： longest increasing subsequence)正如上面我們講的，面對(duì)這樣一個(gè)問題，我們首先要定義一個(gè)狀態(tài)來代 表它的子問題，并且找到它的解。注意，大部分情況下，某個(gè)狀態(tài)只與它 前面出現(xiàn)的狀態(tài)有關(guān)，而獨(dú)立于后面的狀態(tài)。讓我們沿用入門一節(jié)里那道簡(jiǎn)單題的思路來一步步找到狀態(tài)和狀態(tài)轉(zhuǎn) 移方程”。假如我們考慮求A1,A2,.,Ai的最長(zhǎng)非降子序列的長(zhǎng)度，其中 iN，那

7、么上面的問題變成了原問題的一個(gè)子問題(問題規(guī)模變小了，你可 以讓i = 1,2,3等來分析)然后我們定義d(i)，表示前i個(gè)數(shù)中以Ai結(jié)尾的最長(zhǎng) 非降子序列的長(zhǎng)度。OK，對(duì)照入門中的簡(jiǎn)單題，你應(yīng)該可以估計(jì)到這個(gè) d(i)就是我們要找的狀態(tài)。如果我們把d(1)到d(N)都計(jì)算出來，那么最終我 們要找的答案就是這里面最大的那個(gè)。狀態(tài)找到了，下一步找出狀態(tài)轉(zhuǎn)移 方程。為了方便理解我們是如何找到狀態(tài)轉(zhuǎn)移方程的，我先把下面的例子提到前 面來講。如果我們要求的這N個(gè)數(shù)的序列是：5，3，4，8，6，7根據(jù)上面找到的狀態(tài)，我們可以得到：(下文的最長(zhǎng)非降子序列都用LIS 表示)前1個(gè)數(shù)的LIS長(zhǎng)度d(1) 二

8、1(序列：5)前2個(gè)數(shù)的LIS長(zhǎng)度d(2) 二 1(序列：3； 3前面沒有比3小的)前3個(gè)數(shù)的LIS長(zhǎng)度d(3)二2(序列：3, 4； 4前面有個(gè)比它小的3,所以 d(3)=d(2) + 1)前4個(gè)數(shù)的LIS長(zhǎng)度d(4) 二 3(序列：3, 4, 8； 8前面比它小的有3個(gè)數(shù)，所 以 d(4)=maxd(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) = max1, d(j)+1,其中 ji,Aj=Ai 用大白話解釋就是，想要求d(i),就把i前面的各個(gè)子序列中，最

9、后一個(gè)數(shù) 不大于Ai的序列長(zhǎng)度加1，然后取出最大的長(zhǎng)度即為d(i)。當(dāng)然了，有可 能i前面的各個(gè)子序列中最后一個(gè)數(shù)都大于Ai，那么d(i)=1，即它自身成 為一個(gè)長(zhǎng)度為1的子序列。分析完了，上圖：(第二列表示前i個(gè)數(shù)中LIS的長(zhǎng)度，第三列表示，LIS中到 達(dá)當(dāng)前這個(gè)數(shù)的上一個(gè)數(shù)的下標(biāo)，根據(jù)這個(gè)可以求出LIS序列)1Th& length of th& long&st non-d&creasing sequence of first I numb&raThe l&st &qu&nc& I from which w& arrived to this one111 (lirat number itse

10、lf)212 (second number itself)322433533&45Talk is cheap, show me the code:#include usingnamespacestd;intlis(int A, int n) int *d = newintn;intlen = 1;for(inti=0; in; +i) di = 1;for(int j=0; ji; +j) if(Ajdi) di = dj + 1;if(dilen) len = di;delete d;returnlen;int main()int A = 5, 3, 4, 8, 6, 7;coutlis(A

11、, 6)endl;return0;該算法的時(shí)間復(fù)雜度是O(n2 )，并不是最優(yōu)的解法。還有一種很巧妙的 算法可以將時(shí)間復(fù)雜度降到O(nlogn)，網(wǎng)上已經(jīng)有各種文章介紹它，這里 就不再贅述。傳送門：LIS的O(nlogn)解法。此題還可以用排序+ LCS”來解， 感興趣的話可自行Google。練習(xí)題無向圖G有N個(gè)結(jié)點(diǎn)(1N0 ; Sij-1, if j0)其中i代表行，j代表列，下標(biāo)均從0開始；Aij代表格子(i, j)處的蘋果數(shù)量。Sij 有兩種計(jì)算方式：1.對(duì)于每一行，從左向右計(jì)算，然后從上到下逐行 處理；2.對(duì)于每一列，從上到下計(jì)算，然后從左向右逐列處理。這樣做的 目的是為了在計(jì)算Sij

12、時(shí)，Si-1j和Sij-1 都已經(jīng)計(jì)算出來了。偽代碼如下：For i = 0 to N - 1Far J = 0 to M - 1S 二二二=A：二-naSU： ：j-l if -0 ; S 二-二 JL : f i0 ; 0）Output S n-1以下兩道題來自topcoder，練習(xí)用的。AvoidRoads - 2003 TCO Semifinals 4ChessMetric - 2003 TCCC Round 4中高級(jí)這一節(jié)要討論的是帶有額外條件的DP問題。以下的這個(gè)問題是個(gè)很好的例子。無向圖G有N個(gè)結(jié)點(diǎn)，它的邊上帶有正的權(quán)重值。你從結(jié)點(diǎn)1開始走，并且一開始的時(shí)候你身上帶有M元錢。如果

13、你經(jīng)過結(jié) 點(diǎn)i，那么你就要花掉Si元（可以把這想象為收過路費(fèi)）。如果你沒有足夠的 錢，就不能從那個(gè)結(jié)點(diǎn)經(jīng)過。在這樣的限制條件下，找到從結(jié)點(diǎn)1到結(jié)點(diǎn)N 的最短路徑。或者輸出該路徑不存在。如果存在多條最短路徑，那么輸出 花錢數(shù)量最少的那條。限制：1N = 100 ; 0 = M = 100 ;對(duì)于每個(gè)i，0=Si = 0 ANEMir：pi ：l-SpJNi：k ：lE：St ：k) p：J Then Mip ：1-Sp： ：=MirkJ ：1：-Distk： :p：i. e.If for state (i, there are enauglh naney left for going to ve

14、rtex p tl-Sp LeprEseti- ths money thdt will renain aftei passina to vertex p) t and the shortest pat?, f口亳nd for state pr 1-S :pH is biggei than the shoTtest path found for state(k,Ij - distance fion vertex k to vertex p), ther set the Ehoitest path for state (l,j) to be eqal to this sjn.End ForEnd

15、WhileFid the Emallest njuiber among Mi二:N-二:for all ; t ()= =M); if there are nore th己打 one such己tesr then take the one with gieaterj. If there aie no states(K-lrj| with value less than Infinity - then sjch 己 path daesnexist.下面有幾道topcoder上的題以供練習(xí)：Jewelry - 2003 TCO Online Round 4StripePainter - SRM 1

16、50 Div 1 QuickSums - SRM 197 Div 2 ShortPalindromes - SRM 165 Div 2高級(jí)以下問題需要仔細(xì)的揣摩才能將其規(guī)約為可用DP解的問題。問題：StarAdventure - SRM 208 Div 1:給定一個(gè)M行N列的矩陣（M*N個(gè)格子），每個(gè)格子中放著一定數(shù)量的蘋果。 你從左上角的格子開始，只能向下或向右走，目的地是右下角的格子。你 每走過一個(gè)格子，就把格子上的蘋果都收集起來。然后你從右下角走回左 上角的格子，每次只能向左或是向上走，同樣的，走過一個(gè)格子就把里面 的蘋果都收集起來。最后，你再一次從左上角走到右下角，每過一個(gè)格子 同樣要

17、收集起里面的蘋果（如果格子里的蘋果數(shù)為0，就不用收集）。求你 最多能收集到多少蘋果。注意：當(dāng)你經(jīng)過一個(gè)格子時(shí)，你要一次性把格子里的蘋果都拿走。限制條件：1 N, M = 50；每個(gè)格子里的蘋果數(shù)量是0到1000（包含0和 1000）。如果我們只需要從左上角的格子走到右下角的格子一次，并且收集最大數(shù) 量的蘋果，那么問題就退化為中級(jí)一節(jié)里的那個(gè)問題。將這里的問題規(guī) 約為中級(jí)里的簡(jiǎn)單題，這樣一來會(huì)比較好解。讓我們來分析一下這個(gè)問 題，要如何規(guī)約或是修改才能用上DP。首先，對(duì)于第二次從右下角走到左 上角得出的這條路徑，我們可以將它視為從左上角走到右下角得出的路徑， 沒有任何的差別。（即從B走到A的最優(yōu)

18、路徑和從A走到B的最優(yōu)路徑是一樣 的）通過這種方式，我們得到了三條從頂走到底的路徑。對(duì)于這一點(diǎn)的理解 可以稍微減小問題的難度。于是，我們可以將這3條路徑記為左，中，右 路徑。對(duì)于兩條相交路徑（如下圖）: 在不影響結(jié)果的情況下，我們可以將它們視為兩條不相交的路徑: 這樣一來，我們將得到左，中，右3條路徑。此外，如果我們要得到最優(yōu) 解，路徑之間不能相交（除了左上角和右下角必然會(huì)相交的格子）。因此對(duì) 于每一行貝除了第一行和最后一行），三條路徑對(duì)應(yīng)的x坐標(biāo)要滿足：x1y x2y x3y。經(jīng)過這一步的分析，問題的DP解法就進(jìn)一步地清晰了。 讓我們考慮行y，對(duì)于每一個(gè)x1y-1, x2y-1和x3y-1，我們已經(jīng)找到了 能收集到最多蘋果數(shù)量的路徑。根據(jù)它們，我們能求出行y的最優(yōu)解。現(xiàn) 在我們要做的就是找到從一行移動(dòng)到下一行的方式。令Maxijk 表示到 第y-