動(dòng)態(tài)規(guī)劃：從新手到專家

前言

本文翻譯自TopCoder上的一篇文章： Dynamic Programming: From novice to advanced ，并非嚴(yán)格逐字逐句翻譯，其中加入了自己的一些理解。水平有限，還望指摘。

前言_

我們遇到的問題中，有很大一部分可以用動(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)解，然后在它的幫助下，找到下一個(gè)狀態(tài)的最優(yōu)解。

“狀態(tài)”代表什么及如何找到它?

“狀態(tài)"用來描述該問題的子問題的解。原文中有兩段作者闡述得不太清楚，跳過直接上例子。

如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠11元？ (表面上這道題可以用貪心算法，但貪心算法無法保證可以求出解，比如1元換成2元的時(shí)候)

首先我們思考一個(gè)問題，如何用最少的硬幣湊夠i元(i<11)？為什么要這么問呢？?jī)蓚€(gè)原因：1.當(dāng)我們遇到一個(gè)大問題時(shí)，總是習(xí)慣把問題的規(guī)模變小，這樣便于分析討論。 2.這個(gè)規(guī)模變小后的問題和原來的問題是同質(zhì)的，除了規(guī)模變小，其它的都是一樣的，本質(zhì)上它還是同一個(gè)問題(規(guī)模變小后的問題其實(shí)是原問題的子問題)。

好了，讓我們從最小的i開始吧。當(dāng)i=0，即我們需要多少個(gè)硬幣來湊夠0元。由于1，3，5都大于0，即沒有比0小的幣值，因此湊夠0元我們最少需要0個(gè)硬幣。 (這個(gè)分析很傻是不是？別著急，這個(gè)思路有利于我們理清動(dòng)態(tài)規(guī)劃究竟在做些什么。) 這時(shí)候我們發(fā)現(xiàn)用一個(gè)標(biāo)記來表示這句“湊夠0元我們最少需要0個(gè)硬幣。”會(huì)比較方便，如果一直用純文字來表述，不出一會(huì)兒你就會(huì)覺得很繞了。那么，我們用d(i)=j來表示湊夠i元最少需要j個(gè)硬幣。于是我們已經(jīng)得到了d(0)=0，表示湊夠0元最小需要0個(gè)硬幣。當(dāng)i=1時(shí)，只有面值為1元的硬幣可用，因此我們拿起一個(gè)面值為1的硬幣，接下來只需要湊夠0元即可，而這個(gè)是已經(jīng)知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。當(dāng)i=2時(shí)，仍然只有面值為1的硬幣可用，于是我拿起一個(gè)面值為1的硬幣，接下來我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數(shù)量)，而這個(gè)答案也已經(jīng)知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到這里，你都可能會(huì)覺得，好無聊，感覺像做小學(xué)生的題目似的。因?yàn)槲覀円恢倍贾荒懿僮髅嬷禐?的硬幣！耐心點(diǎn)，讓我們看看i=3時(shí)的情況。當(dāng)i=3時(shí)，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用，因?yàn)槟阈枰獪惖臄?shù)目是3元！5元太多了親)。既然能用的硬幣有兩種，我就有兩種方案。如果我拿了一個(gè)1元的硬幣，我的目標(biāo)就變?yōu)榱耍簻悏?-1=2元需要的最少硬幣數(shù)量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。這個(gè)方案說的是，我拿3個(gè)1元的硬幣；第二種方案是我拿起一個(gè)3元的硬幣，我的目標(biāo)就變成：湊夠3-3=0元需要的最少硬幣數(shù)量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個(gè)方案說的是，我拿1個(gè)3元的硬幣。好了，這兩種方案哪種更優(yōu)呢？記得我們可是要用最少的硬幣數(shù)量來湊夠3元的。所以，選擇d(3)=1，怎么來的呢？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。

OK，碼了這么多字講具體的東西，讓我們來點(diǎn)抽象的。從以上的文字中，我們要抽出動(dòng)態(tài)規(guī)劃里非常重要的兩個(gè)概念：狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

上文中d(i)表示湊夠i元需要的最少硬幣數(shù)量，我們將它定義為該問題的"狀態(tài)"，這個(gè)狀態(tài)是怎么找出來的呢？我在另一篇文章 動(dòng)態(tài)規(guī)劃之背包問題(一)中寫過：根據(jù)子問題定義狀態(tài)。你找到子問題，狀態(tài)也就浮出水面了。最終我們要求解的問題，可以用這個(gè)狀態(tài)來表示：d(11)，即湊夠11元最少需要多少個(gè)硬幣。那狀態(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}。沒錯(cuò)，它就是狀態(tài)轉(zhuǎn)移方程，描述狀態(tài)之間是如何轉(zhuǎn)移的。當(dāng)然，我們要對(duì)它抽象一下，

d(i)=min{ d(i-v_j)+1 }，其中i-v_j >=0，v_j表示第j個(gè)硬幣的面值;

有了狀態(tài)和狀態(tài)轉(zhuǎn)移方程，這個(gè)問題基本上也就解決了。當(dāng)然了，Talk is cheap,show me the code!

偽代碼如下：

下圖是當(dāng)i從0到11時(shí)的解：

從上圖可以得出，要湊夠11元至少需要3枚硬幣。

此外，通過追蹤我們是如何從前一個(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)單的例子?，F(xiàn)在讓我們來看看對(duì)于更復(fù)雜的問題，如何找到狀態(tài)之間的轉(zhuǎn)移方式(即找到狀態(tài)轉(zhuǎn)移方程)。為此我們要引入一個(gè)新詞叫遞推關(guān)系來將狀態(tài)聯(lián)系起來(說的還是狀態(tài)轉(zhuǎn)移方程)

OK，上例子，看看它是如何工作的。

一個(gè)序列有N個(gè)數(shù)：A[1],A[2],…,A[N]，求出最長(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)移方程”。假如我們考慮求A[1],A[2],…,A[i]的最長(zhǎng)非降子序列的長(zhǎng)度，其中i<N，那么上面的問題變成了原問題的一個(gè)子問題(問題規(guī)模變小了，你可以讓i=1,2,3等來分析) 然后我們定義d(i)，表示前i個(gè)數(shù)中以A[i]結(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)=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)=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<i,A[j]<=A[i]

用大白話解釋就是，想要求d(i)，就把i前面的各個(gè)子序列中，最后一個(gè)數(shù)不大于A[i]的序列長(zhǎng)度加1，然后取出最大的長(zhǎng)度即為d(i)。當(dāng)然了，有可能i前面的各個(gè)子序列中最后一個(gè)數(shù)都大于A[i]，那么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序列)

Talk is cheap, show me the code:

#include <iostream>
using namespace std;

int lis(int A[], int n){
    int *d = new int[n];
    int len = 1;
    for(int i=0; i<n; ++i){
        d[i] = 1;
        for(int j=0; j<i; ++j)
            if(A[j]<=A[i] && d[j]+1>d[i])
                d[i] = d[j] + 1;
        if(d[i]>len) len = d[i];
    }
    delete[] d;
    return len;
}
int main(){
    int A[] = {
        5, 3, 4, 8, 6, 7
    };
    cout<<lis(A, 6)<<endl;
    return 0;
}

該算法的時(shí)間復(fù)雜度是O(n² )，并不是最優(yōu)的解法。還有一種很巧妙的算法可以將時(shí)間復(fù)雜度降到O(nlogn)，網(wǎng)上已經(jīng)有各種文章介紹它，這里就不再贅述。傳送門： LIS的O(nlogn)解法。此題還可以用“排序+LCS”來解，感興趣的話可自行Google。

練習(xí)題

無向圖G有N個(gè)結(jié)點(diǎn)(1<N<=1000)及一些邊，每一條邊上帶有正的權(quán)重值。找到結(jié)點(diǎn)1到結(jié)點(diǎn)N的最短路徑，或者輸出不存在這樣的路徑。

提示：在每一步中，對(duì)于那些沒有計(jì)算過的結(jié)點(diǎn)，及那些已經(jīng)計(jì)算出從結(jié)點(diǎn)1到它的最短路徑的結(jié)點(diǎn)，如果它們間有邊，則計(jì)算從結(jié)點(diǎn)1到未計(jì)算結(jié)點(diǎn)的最短路徑。

嘗試解決以下來自topcoder競(jìng)賽的問題：

• ZigZag – 2003 TCCC Semifinals 3
• BadNeighbors – 2004 TCCC Round 4
• FlowerGarden – 2004 TCCC Round 1

中級(jí)

接下來，讓我們來看看如何解決二維的DP問題。

平面上有N＊M個(gè)格子，每個(gè)格子中放著一定數(shù)量的蘋果。你從左上角的格子開始，每一步只能向下走或是向右走，每次走到一個(gè)格子上就把格子里的蘋果收集起來，這樣下去，你最多能收集到多少個(gè)蘋果。

解這個(gè)問題與解其它的DP問題幾乎沒有什么兩樣。第一步找到問題的“狀態(tài)”，第二步找到“狀態(tài)轉(zhuǎn)移方程”，然后基本上問題就解決了。

首先，我們要找到這個(gè)問題中的“狀態(tài)”是什么？我們必須注意到的一點(diǎn)是，到達(dá)一個(gè)格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。因此為了求出到達(dá)當(dāng)前格子后最多能收集到多少個(gè)蘋果，我們就要先去考察那些能到達(dá)當(dāng)前這個(gè)格子的格子，到達(dá)它們最多能收集到多少個(gè)蘋果。 (是不是有點(diǎn)繞，但這句話的本質(zhì)其實(shí)是DP的關(guān)鍵：欲求問題的解，先要去求子問題的解)

經(jīng)過上面的分析，很容易可以得出問題的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。狀態(tài)S[i][j]表示我們走到(i, j)這個(gè)格子時(shí)，最多能收集到多少個(gè)蘋果。那么，狀態(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]有兩種計(jì)算方式：1.對(duì)于每一行，從左向右計(jì)算，然后從上到下逐行處理；2. 對(duì)于每一列，從上到下計(jì)算，然后從左向右逐列處理。這樣做的目的是為了在計(jì)算S[i][j]時(shí)，S[i-1][j]和S[i][j-1]都已經(jīng)計(jì)算出來了。

偽代碼如下：

以下兩道題來自topcoder，練習(xí)用的。

• AvoidRoads – 2003 TCO Semifinals 4
• ChessMetric – 2003 TCCC Round 4

中高級(jí)

這一節(jié)要討論的是帶有額外條件的DP問題。

以下的這個(gè)問題是個(gè)很好的例子。

無向圖G有N個(gè)結(jié)點(diǎn)，它的邊上帶有正的權(quán)重值。

你從結(jié)點(diǎn)1開始走，并且一開始的時(shí)候你身上帶有M元錢。如果你經(jīng)過結(jié)點(diǎn)i，那么你就要花掉S[i]元(可以把這想象為收過路費(fèi))。如果你沒有足夠的錢，就不能從那個(gè)結(jié)點(diǎn)經(jīng)過。在這樣的限制條件下，找到從結(jié)點(diǎn)1到結(jié)點(diǎn)N的最短路徑。或者輸出該路徑不存在。如果存在多條最短路徑，那么輸出花錢數(shù)量最少的那條。限制：1<N<=100 ; 0<=M<=100 ; 對(duì)于每個(gè)i，0<=S[i]<=100；正如我們所看到的，如果沒有額外的限制條件(在結(jié)點(diǎn)處要收費(fèi)，費(fèi)用不足還不給過)，那么，這個(gè)問題就和經(jīng)典的迪杰斯特拉問題一樣了(找到兩結(jié)點(diǎn)間的最短路徑)。在經(jīng)典的迪杰斯特拉問題中，我們使用一個(gè)一維數(shù)組來保存從開始結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的最短路徑的長(zhǎng)度，即M[i]表示從開始結(jié)點(diǎn)到結(jié)點(diǎn)i的最短路徑的長(zhǎng)度。然而在這個(gè)問題中，我們還要保存我們身上剩余多少錢這個(gè)信息。因此，很自然的，我們將一維數(shù)組擴(kuò)展為二維數(shù)組。M[i][j]表示從開始結(jié)點(diǎn)到結(jié)點(diǎn)i的最短路徑長(zhǎng)度，且剩余j元。通過這種方式，我們將這個(gè)問題規(guī)約到原始的路徑尋找問題。在每一步中，對(duì)于已經(jīng)找到的最短路徑，我們找到它所能到達(dá)的下一個(gè)未標(biāo)記狀態(tài)(i,j)，將它標(biāo)記為已訪問(之后不再訪問這個(gè)結(jié)點(diǎn))，并且在能到達(dá)這個(gè)結(jié)點(diǎn)的各個(gè)最短路徑中，找到加上當(dāng)前邊權(quán)重值后最小值對(duì)應(yīng)的路徑，即為該結(jié)點(diǎn)的最短路徑。 (寫起來真是繞，建議畫個(gè)圖就會(huì)明了很多)。不斷重復(fù)上面的步驟，直到所有的結(jié)點(diǎn)都訪問到為止(這里的訪問并不是要求我們要經(jīng)過它，比如有個(gè)結(jié)點(diǎn)收費(fèi)很高，你沒有足夠的錢去經(jīng)過它，但你已經(jīng)訪問過它) 最后Min[N-1][j]中的最小值即是問題的答案(如果有多個(gè)最小值，即有多條最短路徑，那么選擇j最大的那條路徑，即，使你剩余錢數(shù)最多的最短路徑)。

偽代碼：

下面有幾道topcoder上的題以供練習(xí)：

• Jewelry – 2003 TCO Online Round 4
• StripePainter – SRM 150 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è)格子同樣要收集起里面的蘋果 (如果格子里的蘋果數(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)路徑和從A走到B的最優(yōu)路徑是一樣的)通過這種方式，我們得到了三條從頂走到底的路徑。對(duì)于這一點(diǎn)的理解可以稍微減小問題的難度。于是，我們可以將這3條路徑記為左，中，右路徑。對(duì)于兩條相交路徑(如下圖)：

在不影響結(jié)果的情況下，我們可以將它們視為兩條不相交的路徑：

這樣一來，我們將得到左，中，右3條路徑。此外，如果我們要得到最優(yōu)解，路徑之間不能相交(除了左上角和右下角必然會(huì)相交的格子)。因此對(duì)于每一行y( 除了第一行和最后一行)，三條路徑對(duì)應(yīng)的x坐標(biāo)要滿足：x1[y] < x2[y] < x3[y]。經(jīng)過這一步的分析，問題的DP解法就進(jìn)一步地清晰了。讓我們考慮行y，對(duì)于每一個(gè)x1[y-1]，x2[y-1]和x3[y-1]，我們已經(jīng)找到了能收集到最多蘋果數(shù)量的路徑。根據(jù)它們，我們能求出行y的最優(yōu)解。現(xiàn)在我們要做的就是找到從一行移動(dòng)到下一行的方式。令Max[i][j][k]表示到第y-1行為止收集到蘋果的最大數(shù)量，其中3條路徑分別止于第i,j,k列。對(duì)于下一行y，對(duì)每個(gè)Max[i][j][k] 都加上格子(y,i)，(y,j)和(y,k)內(nèi)的蘋果數(shù)量。因此，每一步我們都向下移動(dòng)。我們做了這一步移動(dòng)之后，還要考慮到，一條路徑是有可能向右移動(dòng)的。 (對(duì)于每一個(gè)格子，我們有可能是從它上面向下移動(dòng)到它，也可能是從它左邊向右移動(dòng)到它)。為了保證3條路徑互不相交，我們首先要考慮左邊的路徑向右移動(dòng)的情況，然后是中間，最后是右邊的路徑。為了更好的理解，讓我們來考慮左邊的路徑向右移動(dòng)的情況，對(duì)于每一個(gè)可能的j,k對(duì)(j<k)，對(duì)每個(gè)i(i<j)，考慮從位置(i-1,j,k)移動(dòng)到位置(i,j,k)。處理完左邊的路徑，再處理中間的路徑，最后處理右邊的路徑。方法都差不多。

用于練習(xí)的topcoder題目：

• MiniPaint – SRM 178 Div 1

其它

當(dāng)閱讀一個(gè)題目并且開始嘗試解決它時(shí)，首先看一下它的限制。如果要求在多項(xiàng)式時(shí)間內(nèi)解決，那么該問題就很可能要用DP來解。遇到這種情況，最重要的就是找到問題的“狀態(tài)”和“狀態(tài)轉(zhuǎn)移方程”。(狀態(tài)不是隨便定義的，一般定義完?duì)顟B(tài)，你要找到當(dāng)前狀態(tài)是如何從前面的狀態(tài)得到的，即找到狀態(tài)轉(zhuǎn)移方程)如果看起來是個(gè)DP問題，但你卻無法定義出狀態(tài)，那么試著將問題規(guī)約到一個(gè)已知的DP問題(正如“高級(jí)”一節(jié)中的例子一樣)。

后記

看完這教程離DP專家還差得遠(yuǎn)，好好coding才是王道。