動态規劃 Dynamic Programming

March 26, 2013

作者：Hawstein

聲明：本文采用以下協定進行授權： 自由轉載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ，轉載請注明作者及出處。

前言

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

我們遇到的問題中，有很大一部分可以用動态規劃(簡稱DP)來解。 解決這類問題可以很大地提升你的能力與技巧，我會試着幫助你了解如何使用DP來解題。 這篇文章是基于執行個體展開來講的，因為幹巴巴的理論實在不好了解。

注意：如果你對于其中某一節已經了解并且不想閱讀它，沒關系，直接跳過它即可。

簡介(入門)

什麼是動态規劃，我們要如何描述它?

動态規劃算法通常基于一個遞推公式及一個或多個初始狀态。 目前子問題的解将由上一次子問題的解推出。使用動态規劃來解題隻需要多項式時間複雜度， 是以它比回溯法、暴力法等要快許多。

現在讓我們通過一個例子來了解一下DP的基本原理。

首先，我們要找到某個狀态的最優解，然後在它的幫助下，找到下一個狀态的最優解。

“狀态”代表什麼及如何找到它?

“狀态”用來描述該問題的子問題的解。原文中有兩段作者闡述得不太清楚，跳過直接上例子。

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

首先我們思考一個問題，如何用最少的硬币湊夠i元(i<11)？為什麼要這麼問呢？ 兩個原因：1.當我們遇到一個大問題時，總是習慣把問題的規模變小，這樣便于分析讨論。 2.這個規模變小後的問題和原來的問題是同質的，除了規模變小，其它的都是一樣的， 本質上它還是同一個問題(規模變小後的問題其實是原問題的子問題)。

好了，讓我們從最小的i開始吧。當i=0，即我們需要多少個硬币來湊夠0元。 由于1，3，5都大于0，即沒有比0小的币值，是以湊夠0元我們最少需要0個硬币。 (這個分析很傻是不是？别着急，這個思路有利于我們理清動态規劃究竟在做些什麼。) 這時候我們發現用一個标記來表示這句“湊夠0元我們最少需要0個硬币。”會比較友善， 如果一直用純文字來表述，不出一會兒你就會覺得很繞了。那麼， 我們用d(i)=j來表示湊夠i元最少需要j個硬币。于是我們已經得到了d(0)=0， 表示湊夠0元最小需要0個硬币。當i=1時，隻有面值為1元的硬币可用， 是以我們拿起一個面值為1的硬币，接下來隻需要湊夠0元即可，而這個是已經知道答案的， 即d(0)=0。是以，d(1)=d(1-1)+1=d(0)+1=0+1=1。當i=2時， 仍然隻有面值為1的硬币可用，于是我拿起一個面值為1的硬币， 接下來我隻需要再湊夠2-1=1元即可(記得要用最小的硬币數量)，而這個答案也已經知道了。 是以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到這裡，你都可能會覺得，好無聊， 感覺像做國小生的題目似的。因為我們一直都隻能操作面值為1的硬币！耐心點， 讓我們看看i=3時的情況。當i=3時，我們能用的硬币就有兩種了：1元的和3元的( 5元的仍然沒用，因為你需要湊的數目是3元！5元太多了親)。 既然能用的硬币有兩種，我就有兩種方案。如果我拿了一個1元的硬币，我的目标就變為了： 湊夠3-1=2元需要的最少硬币數量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。 這個方案說的是，我拿3個1元的硬币；第二種方案是我拿起一個3元的硬币， 我的目标就變成：湊夠3-3=0元需要的最少硬币數量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個方案說的是，我拿1個3元的硬币。好了，這兩種方案哪種更優呢？ 記得我們可是要用最少的硬币數量來湊夠3元的。是以， 選擇d(3)=1，怎麼來的呢？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。

OK，碼了這麼多字講具體的東西，讓我們來點抽象的。從以上的文字中， 我們要抽出動态規劃裡非常重要的兩個概念：狀态和狀态轉移方程。

上文中d(i)表示湊夠i元需要的最少硬币數量，我們将它定義為該問題的”狀态”， 這個狀态是怎麼找出來的呢？我在另一篇文章 動态規劃之背包問題(一)中寫過： 根據子問題定義狀态。你找到子問題，狀态也就浮出水面了。 最終我們要求解的問題，可以用這個狀态來表示：d(11)，即湊夠11元最少需要多少個硬币。 那狀态轉移方程是什麼呢？既然我們用d(i)表示狀态，那麼狀态轉移方程自然包含d(i)， 上文中包含狀态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。沒錯， 它就是狀态轉移方程，描述狀态之間是如何轉移的。當然，我們要對它抽象一下，

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

有了狀态和狀态轉移方程，這個問題基本上也就解決了。當然了，Talk is cheap,show me the code!

僞代碼如下：

下圖是當i從0到11時的解：

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

此外，通過追蹤我們是如何從前一個狀态值得到目前狀态值的， 可以找到每一次我們用的是什麼面值的硬币。比如，從上面的圖我們可以看出， 最終結果d(11)=d(10)+1(面值為1)，而d(10)=d(5)+1(面值為5)，最後d(5)=d(0)+1 (面值為5)。是以我們湊夠11元最少需要的3枚硬币是：1元、5元、5元。

注意：原文中這裡本來還有一段的，但我反反複複讀了幾遍， 大概的意思我已經在上文從i=0到i=3的分析中有所展現了。作者本來想講的通俗一些， 結果沒寫好，反而更不好懂，是以這段不翻譯了。

初級

上面讨論了一個非常簡單的例子。現在讓我們來看看對于更複雜的問題， 如何找到狀态之間的轉移方式(即找到狀态轉移方程)。 為此我們要引入一個新詞叫遞推關系來将狀态聯系起來(說的還是狀态轉移方程)

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

一個序列有N個數：A[1],A[2],…,A[N]，求出最長非降子序列的長度。 (講DP基本都會講到的一個問題LIS：longest increasing subsequence)

正如上面我們講的，面對這樣一個問題，我們首先要定義一個“狀态”來代表它的子問題， 并且找到它的解。注意，大部分情況下，某個狀态隻與它前面出現的狀态有關， 而獨立于後面的狀态。

讓我們沿用“入門”一節裡那道簡單題的思路來一步步找到“狀态”和“狀态轉移方程”。 假如我們考慮求A[1],A[2],…,A[i]的最長非降子序列的長度，其中i<N， 那麼上面的問題變成了原問題的一個子問題(問題規模變小了，你可以讓i=1,2,3等來分析) 然後我們定義d(i)，表示前i個數中以A[i]結尾的最長非降子序列的長度。OK， 對照“入門”中的簡單題，你應該可以估計到這個d(i)就是我們要找的狀态。 如果我們把d(1)到d(N)都計算出來，那麼最終我們要找的答案就是這裡面最大的那個。 狀态找到了，下一步找出狀态轉移方程。

為了友善了解我們是如何找到狀态轉移方程的，我先把下面的例子提到前面來講。 如果我們要求的這N個數的序列是：

5，3，4，8，6，7
           

根據上面找到的狀态，我們可以得到：（下文的最長非降子序列都用LIS表示）

• 前1個數的LIS長度d(1)=1(序列：5)
• 前2個數的LIS長度d(2)=1(序列：3；3前面沒有比3小的)
• 前3個數的LIS長度d(3)=2(序列：3，4；4前面有個比它小的3，是以d(3)=d(2)+1)
• 前4個數的LIS長度d(4)=3(序列：3，4，8；8前面比它小的有3個數，是以 d(4)=max{d(1),d(2),d(3)}+1=3)

OK，分析到這，我覺得狀态轉移方程已經很明顯了，如果我們已經求出了d(1)到d(i-1)， 那麼d(i)可以用下面的狀态轉移方程得到：

d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
           

用大白話解釋就是，想要求d(i)，就把i前面的各個子序列中， 最後一個數不大于A[i]的序列長度加1，然後取出最大的長度即為d(i)。 當然了，有可能i前面的各個子序列中最後一個數都大于A[i]，那麼d(i)=1， 即它自身成為一個長度為1的子序列。

分析完了，上圖：(第二清單示前i個數中LIS的長度， 第三清單示，LIS中到達目前這個數的上一個數的下标，根據這個可以求出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;
}
           

該算法的時間複雜度是O(n^2 )，并不是最優的解法。 還有一種很巧妙的算法可以将時間複雜度降到O(nlogn)，網上已經有各種文章介紹它， 這裡就不再贅述。傳送門： LIS的O(nlogn)解法。 此題還可以用“排序+LCS”來解，感興趣的話可自行Google。

練習題

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

提示：在每一步中，對于那些沒有計算過的結點， 及那些已經計算出從結點1到它的最短路徑的結點，如果它們間有邊， 則計算從結點1到未計算結點的最短路徑。

嘗試解決以下來自topcoder競賽的問題：

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

中級

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

平面上有N*M個格子，每個格子中放着一定數量的蘋果。你從左上角的格子開始， 每一步隻能向下走或是向右走，每次走到一個格子上就把格子裡的蘋果收集起來， 這樣下去，你最多能收集到多少個蘋果。

解這個問題與解其它的DP問題幾乎沒有什麼兩樣。第一步找到問題的“狀态”， 第二步找到“狀态轉移方程”，然後基本上問題就解決了。

首先，我們要找到這個問題中的“狀态”是什麼？我們必須注意到的一點是， 到達一個格子的方式最多隻有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。 是以為了求出到達目前格子後最多能收集到多少個蘋果， 我們就要先去考察那些能到達目前這個格子的格子，到達它們最多能收集到多少個蘋果。 (是不是有點繞，但這句話的本質其實是DP的關鍵：欲求問題的解，先要去求子問題的解)

經過上面的分析，很容易可以得出問題的狀态和狀态轉移方程。 狀态S[i][j]表示我們走到(i, j)這個格子時，最多能收集到多少個蘋果。那麼， 狀态轉移方程如下：

S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)
           

其中i代表行，j代表列，下标均從0開始；A[i][j]代表格子(i, j)處的蘋果數量。

S[i][j]有兩種計算方式：1.對于每一行，從左向右計算，然後從上到下逐行處理；2. 對于每一列，從上到下計算，然後從左向右逐列處理。 這樣做的目的是為了在計算S[i][j]時，S[i-1][j]和S[i][j-1]都已經計算出來了。

以下兩道題來自topcoder，練習用的。

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

中進階

這一節要讨論的是帶有額外條件的DP問題。

以下的這個問題是個很好的例子。

無向圖G有N個結點，它的邊上帶有正的權重值。

你從結點1開始走，并且一開始的時候你身上帶有M元錢。如果你經過結點i， 那麼你就要花掉S[i]元(可以把這想象為收過路費)。如果你沒有足夠的錢， 就不能從那個結點經過。在這樣的限制條件下，找到從結點1到結點N的最短路徑。 或者輸出該路徑不存在。如果存在多條最短路徑，那麼輸出花錢數量最少的那條。 限制：1<N<=100 ; 0<=M<=100 ; 對于每個i，0<=S[i]<=100；正如我們所看到的， 如果沒有額外的限制條件(在結點處要收費，費用不足還不給過)，那麼， 這個問題就和經典的迪傑斯特拉問題一樣了(找到兩結點間的最短路徑)。 在經典的迪傑斯特拉問題中， 我們使用一個一維數組來儲存從開始結點到每個結點的最短路徑的長度， 即M[i]表示從開始結點到結點i的最短路徑的長度。然而在這個問題中， 我們還要儲存我們身上剩餘多少錢這個資訊。是以，很自然的， 我們将一維數組擴充為二維數組。M[i][j]表示從開始結點到結點i的最短路徑長度， 且剩餘j元。通過這種方式，我們将這個問題規約到原始的路徑尋找問題。 在每一步中，對于已經找到的最短路徑，我們找到它所能到達的下一個未标記狀态(i,j)， 将它标記為已通路(之後不再通路這個結點)，并且在能到達這個結點的各個最短路徑中， 找到加上目前邊權重值後最小值對應的路徑，即為該結點的最短路徑。 (寫起來真是繞，建議畫個圖就會明了很多)。不斷重複上面的步驟， 直到所有的結點都通路到為止(這裡的通路并不是要求我們要經過它， 比如有個結點收費很高，你沒有足夠的錢去經過它，但你已經通路過它) 最後Min[N-1][j]中的最小值即是問題的答案(如果有多個最小值， 即有多條最短路徑，那麼選擇j最大的那條路徑，即，使你剩餘錢數最多的最短路徑)。

僞代碼：

下面有幾道topcoder上的題以供練習：

• Jewelry - 2003 TCO Online Round 4
• StripePainter - SRM 150 Div 1
• QuickSums - SRM 197 Div 2
• ShortPalindromes - SRM 165 Div 2

進階

以下問題需要仔細的揣摩才能将其規約為可用DP解的問題。

問題：StarAdventure - SRM 208 Div 1:

給定一個M行N列的矩陣(M*N個格子)，每個格子中放着一定數量的蘋果。 你從左上角的格子開始，隻能向下或向右走，目的地是右下角的格子。 你每走過一個格子，就把格子上的蘋果都收集起來。然後你從右下角走回左上角的格子， 每次隻能向左或是向上走，同樣的，走過一個格子就把裡面的蘋果都收集起來。 最後，你再一次從左上角走到右下角，每過一個格子同樣要收集起裡面的蘋果 (如果格子裡的蘋果數為0，就不用收集)。求你最多能收集到多少蘋果。

注意：當你經過一個格子時，你要一次性把格子裡的蘋果都拿走。

限制條件：1 < N, M <= 50；每個格子裡的蘋果數量是0到1000(包含0和1000)。

如果我們隻需要從左上角的格子走到右下角的格子一次，并且收集最大數量的蘋果， 那麼問題就退化為“中級”一節裡的那個問題。将這裡的問題規約為“中級”裡的簡單題， 這樣一來會比較好解。讓我們來分析一下這個問題，要如何規約或是修改才能用上DP。 首先，對于第二次從右下角走到左上角得出的這條路徑， 我們可以将它視為從左上角走到右下角得出的路徑，沒有任何的差别。 (即從B走到A的最優路徑和從A走到B的最優路徑是一樣的)通過這種方式， 我們得到了三條從頂走到底的路徑。對于這一點的了解可以稍微減小問題的難度。 于是，我們可以将這3條路徑記為左，中，右路徑。對于兩條相交路徑(如下圖)：

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

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

• MiniPaint - SRM 178 Div 1

其它

後記