topcoder算法教程翻譯系列之動態規劃

本文翻譯自topcoder的算法教程http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/dynamic-programming-from-novice-to-advanced/

有相當一部分問題可以用動態規劃（dynamic programing）來解決，下面用DP來表示。如果能夠很好地掌握這類問題，那么對于編程能力將會是一個很大的提升。

本文將會教給大家如何用DP來解決問題，由于干枯的理論不便于理解，因此文章中舉了很多例子來輔助對于DP的講解。

引入

什么是動態規劃？應該怎樣描述它？

DP是一種算法設計技術，它是基于一個遞推式和一些初始狀態的。子問題的最優解是取決于子子問題的最優解的，并且子子問題的最優解是在求解子問題的最優解之前就已經算好的。

DP的時間復雜度是多項式的，這就使得它比回溯和暴力解法等算法要快得多。

接下來我們通過一個例子來看看DP的一些基本的東西。

現在有N種硬幣，每種硬幣的面值為（V₁, V₂, …, V_N）。現在需要用最少的硬幣湊成總和S。

接下來我們構造一個動態規劃的解法。

首先，我們必須要定義一個狀態，并且找到該狀態的最優解，通過該狀態的最優解，我們進而可以找到下一個狀態的最優解。

那么什么是狀態？

狀態是用來描述子問題的一種方式。對于上面硬幣的例子，狀態i就表示對于總和i（i <= S），需要的最少硬幣數。對于一個比狀態i更小的狀態j，它表示需要最少的硬幣湊成總和j。為了找到狀態i，我們需要找到所有的小于i的狀態j。一旦找到了湊成總和i的最少硬幣，我們就能夠很容易找到下一個狀態，即狀態i+1。

那么怎樣求得狀態i？

對于每一種面值小于等于i的硬幣j，我們查看湊成總和i-V_j的最少硬幣數（狀態i-V_j是比狀態i更小的狀態，之前已經求出，此時只需查表即可得到），假設湊成總和i-V_j的最少硬幣數為m，如果m+1比湊成總和為i的最小硬幣數的當前值要小，那么將m+1賦值給狀態i。

為了更好地理解上面的表述，我們來看個例子。現在有3種硬幣，每種的面值為1,3和5，總和S為11。

首先，對于狀態i=0，我們認為需要的最少硬幣數為0枚。緊接著，我們看S=1，由于我們沒有求解過該狀態的值，因此它的初始值可以設為無窮大。接下來，我們發現只有第一種硬幣的面值小于等于目前的S，因此，由S-V₁我們找到之前的狀態0，由于狀態0已經求出，我們就用狀態0的最優值加上1，就得到了狀態1的最優值并且保存。

接下來，我們求解狀態2，同樣，我們發現只有第一種硬幣的面值小于等于目前的S，由于S-V₁=1，問題歸約為狀態1，而狀態1已經求出，因此狀態2的最優值等于狀態1的最優值加上1，也就是說，當S=2時，需要的最少硬幣數為2。

同樣，我們求解狀態3，這次，第一種硬幣的面值和第二種硬幣的面值都小于等于3，因此我們得分別考察對應的情況。對于第一種硬幣，問題歸約為狀態2（3-1），因此狀態3為狀態2的最優值加上1，即2+1=3；對于第二種硬幣，問題歸約為狀態0（3-3），因此狀態3為狀態0的最優值加上1，即0+1=1。通過比較這兩種情況，顯然后者要優于前者，因此狀態3等于1。

后面狀態的求解以此類推。

偽碼如下：

下面的列表展示了所有狀態的求解。

其中第一列表示各個狀態；第二列表示狀態的最優值；第三列表示狀態的轉移，第一個數字表示湊成當前總和要加上的硬幣的面值，括號內為得到當前狀態的上一個狀態。

最后，我們得到了湊成總和為11需要最少的硬幣數為3。

另外，通過回溯，可以追蹤我們是如何通過之前的狀態得到當前狀態的，從而可以得知最優解中用到了哪些硬幣。比如說，為了得到狀態11，我們把面值為1的硬幣加到了狀態10，為了得到狀態10，我們把面值為5的硬幣加到了狀態5，為了得到狀態5，我們把面值為5的硬幣加到狀態0。這樣一來，我們找出了構成最終最優解的硬幣為：1, 5, 5。

在了解了DP的基本使用方式后，我們來看一個稍微不同的方式，主要涉及到對于最優解的更新，不論何時發現了更好的解，都要進行更新。在這種情況下，狀態的更新就不是連續進行的了。

繼續考慮上面那個例子。初始時，狀態0依然等于0。現在，我們把第一種硬幣（面值為1）加入所有已經求得的狀態，如果結果值t小于當前的狀態值，那么就更新狀態的值。剩下的硬幣同樣如上做法。

比如說，我們首先把面值為1的硬幣加入狀態0（因為目前只有狀態0被求出），得到狀態1。由于我們目前還沒找到別的方式來湊成1，因此這就是目前找到的最優的狀態1，S[1] = 1。接著把面值為1的硬幣加入狀態1，我們得到狀態2，S[2] = 2。以此類推，直到得到狀態11。

接著，把第二種硬幣（面值為3）加入到已經求出的各個狀態。把它加到狀態0，我們得到狀態3，此時得到了狀態3等于1，這比之前的S[3] = 3更優，因此更新S[3] = 1。把它加到狀態1，我們得到狀態4等于2。由于之前S[4] = 4，因此更新S[4] = 2。

以此類推，每當一個更優的解被找到，就更新狀態原先的值。

初階

以上，我們介紹了一個簡單的例子來說明動態規劃，接下來，我們看看對于稍微難的問題，怎樣找到一個方式來處理狀態的轉移。介于此，我們要引進一個新的術語，叫做遞推關系，它在較小狀態和較大狀態之間建立了聯系。

我們來看看其如何工作的。

給定一個含有N個元素的數組，A[1], A[2] ,…,A[N]。找出最長遞增子序列的長度。

首先，我們要定義狀態，它代表一個子問題。接著，我們要為這個狀態找出一個最優解。需要注意的是，在大多數情況下，當前狀態只和之前的較小的狀態有關，和之后的較大狀態無關。

我們將本例的狀態定義如下：狀態i表示數組前i個數中必須包含第i個數的最長遞增子序列的長度。注意，對于i < j，狀態i和狀態j無關，也就是說在計算狀態j時，狀態i不會改變。接下來我們來看這些狀態是怎么聯系在一起的。在求出了所有比i小的狀態之后，我們緊接著就可以求狀態i。每個狀態的初始值都為1，表示只有它自己。現在，對于每一個小于i的狀態，我們逐個檢查，看是否能由它轉化到狀態i，即能否用它構造狀態i。由于我們是要構造遞增的序列，因此只有A[j] <= A[i]的狀態j才有可能構造出狀態i。因此，如果S[j]（狀態j的最優值）+1（A[i]）比狀態i的當前值要更優（S[j] + 1 > S[i]），那么用它替換當前值（S[i] = S[j] + 1）。如此，我們可以找到狀態N的值。

我們來看個例子：找出序列5, 3, 4, 8, 6, 7的最長遞增子序列。

表中左邊一列表示狀態，從1到6，中間一列表示狀態的最優值，右邊一列表示得到當前狀態的上一個狀態。

以下是topcoder的題目：

·        ZigZag -2003 TCCC Semifinals 3

·        BadNeighbors -2004 TCCC Round 4

·        FlowerGarden -2004 TCCC Round 1

中階

我們接下來看如何處理二元動態規劃問題。

現有一個由N*M的格子組成的表，N代表行數，M代表每行的格子數，每個格子里面有固定數量的蘋果。假設一個人從左上角的格子出發，每一步只能向下或者向右走一個格子，每到一個格子就可以得到格子里的所有蘋果，如何走到右下角，才能使得獲得的蘋果最多。

這個問題的解答和其它DP問題的解答沒有區別。

同樣地，我們首先定義狀態。我們首先注意到，要走到一個格子可以從兩個方向來，第一個是從左邊（第一列除外），第二個是從上面（第一行除外）。因此，為了找到到達該格子時的最大蘋果數量，我們一定要先找到到達它左邊和它上邊的格子時所獲得的最大蘋果數量。因此，本題的狀態是S[i][j]，表示到達格子(i, j)時所獲得的最大蘋果數量。

由以上的分析可以得到狀態之間的遞推關系。

S[i][j] = A[i][j] + max(S[i-1][j], S[i][j-1])，上式中i代表行，j代表列，左上角的坐標為{0, 0}。A[i][j]表示在格子(i, j)里的蘋果數。注意，當格子處于第一行或是第一列的時候，上面的遞推式不一定成立，因為i-1或者j-1會為負數，為了處理這種邊界情況，可以先對它們進行初始化。

以下是偽碼：

For i = 0 to N - 1

   For j = 0 to M - 1

   S[i][j] = A[i][j] +

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

Output S[n-1][m-1]

下面是topcoder的相關題目

·        AvoidRoads -2003 TCO Semifinals 4

·        ChessMetric -2003 TCCC Round 4

中高階

這一部分將會討論帶有限制條件的DP問題。

來看一個例子。

給定一個含有N個節點的帶正權的無向圖G。某人有M元錢，對于每一個節點i，通過它需要支付S[i]元，如果錢不夠，那么就不能通過這個節點。要求解的問題是：在錢的限制條件下，找到從節點1到節點N的最短路徑，如果沒有這樣的路徑，則說明不存在。如果存在多條最短路徑，那么找出花錢最少的那條。約束條件為：1 < N <= 100；0 <= M <= 100；對于每一個節點i，0 <= S[i] <= 100。

我們能夠很容易地發現，如果沒有限制條件，這就是一個dijkstra問題（找出源點到某點的最短距離）。

在dijkstra問題里，我們只需要一個一維數組Min[i]來保存到點i的最短路徑距離。

但在本例中，我們需要考慮錢數的限制。因此，可以將一維數組Min[i]擴展成為二維數組Min[i][j]，它的含義是到節點i的最短路徑并剩下了j元錢。這里Min[i][j]就是本例的DP狀態。

算法的每一步都會找一個未被處理過的狀態(i, j)來求解，并且將它標記為訪問過，以免后續重復訪問，對于該節點i的鄰居節點，算法也會檢查并且更新。

重復上述過程，直到所有狀態(i, j)被求出。

算法最后比較Min[N-1][j]的所有j，取最優。

以下是偽碼：

Set states(i,j) as unvisited for all (i,j)

Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]

is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is

less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.

   If (l-S[p]>=0 AND

    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])

      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]

   i.e.

If for state(i,j) there are enough money left for

going to vertex p (l-S[p] represents the money that

will remain after passing to vertex p), and the

shortest path found for state(p,l-S[p]) is bigger

than [the shortest path found for

state(k,l)] + [distance from vertex k to vertex p)],

then set the shortest path for state(i,j) to be equal

to this sum.

End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);

if there are more than one such states, then take the one with greater

j. If there are no states(N-1,j) with value less than Infinity - then

such a path doesn't exist.

以下是一些topcoder題目：

·        Jewelry -2003 TCO Online Round 4

·        StripePainter -SRM 150 Div 1

·        QuickSums -SRM 197 Div 2

·        ShortPalindromes -SRM 165 Div 2

高階

具體請見原文。

注意事項

當要解決一個問題的時候我們首先看看限制條件，如果要求多項式時間解決問題，那么多半要想到用DP。在這種情況下，我們需要定義狀態，并且通過該狀態可以求出下一個狀態，在找到狀態之后，接下來需要考慮如何從較小的狀態轉移到較大的狀態，即狀態之間的遞推關系。如果要求解的問題看上去是個DP的問題，但是又無法找出相應的狀態，那么就把要求解的問題轉化成另外一個可求解的DP問題。

注：本文的部分習題代碼可以參見https://github.com/ChenML/topcoder_dp

來自： http://blog.csdn.net//henryczj/article/details/40924167