動態規劃的深入探討

一、引言

動態規劃是一種重要的程序設計思想，具有廣泛的應用價值。使用動態規劃思想來設計算法，對于不少問題往往具有高時效，因而，對于能夠使用動態規劃思想來解決的問題，使用動態規劃是比較明智的選擇。

能夠用動態規劃解決的問題，往往是最優化問題，且問題的最優解(或特定解)的局部往往是局部問題在相應條件下的最優解，而且問題的最優解與其子問題的最優解要有一定的關聯，要能建立遞推關系。如果這種關系難以建立，即問題的特定解不僅依賴于子問題的特定解，而且與子問題的一般解相關，那么，一方面難以記錄下那么多的“一般解”，另一方面，遞推的效率也將是很低的；此外，為了體現動態規劃的高時效，子問題應當是互相重疊的，即很多不同的問題共享相同的子問題。(如果子問題不重疊，則宜使用其它方法，如分治法等。)

動態規劃一般可以通過兩種手段比較高效地實現，其一是通過自頂向下記憶化的方法，即通過遞歸或不遞歸的手段，將對問題最優解的求解，歸結為求其子問題的最優解，并將計算過的結果記錄下來，從而實現結果的共享；另一種手段，也就是最主要的手段，通過自底向上的遞推的方式，由于這種方式代價要比前一種方式小，因而被普遍采用，下面的討論均采用這種方式實現。動態規劃之所以具有高時效，是因為它在將問題規模不斷減小的同時，有效地把解記錄下來，從而避免了反復解同一個子問題的現象，因而只要運用得當，較之搜索而言，效率就會有很大的提高。

動態規劃的思想，為我們解決與重疊子問題相關的最優化問題提供了一個思考方向：通過迭-慮子問題，將問題規模減小而最終解決問題。適于用動態規劃解決的問題，是十分廣泛的。動態規劃的思想本身是重要的，但更重要的是面對具體問題的具體分析。要分析問題是否具備使用動態規劃的條件，確定使用動態規劃解題的子問題空間和遞推關系式等，以及在(常規)內存有限的計算機上實現這些算法。下面分別就構思和實現兩個方面進一步探討動態規劃這一思想。

二、動態規劃解題的構思

當我們面對一個問題考慮用動態規劃時，十分重要的一點就是判斷這個問題能否用動態規劃高效地解決。用動態規劃構思算法時，往往要考慮到這個問題所涉及到的子問題(子問題空間)，以及如何建立遞推式，并最終實現算法。其實，這些過程往往是交織在一起的，子問題空間與遞推關系本身就是緊密相聯的，為了有效地建立起遞推關系，有時就要調整子問題空間；而根據大致確定的子問題空間又可以啟發我們建立遞推關系式。而能否最終用一個遞推關系式來聯系問題與其子問題又成了判斷一個問題能否使用動態規劃思想解決的主要依據。因而孤立地來看這其中的每一部分，硬把思考過程人為地分成幾個部分，是困難的，也是不必要的。而且動態規劃這種思想方法，沒有固定的數學模型，要因題而異，因而也就不可能歸納出一種“萬能”的方法。但是對大多數問題而言，還是能夠有一個基本的思考方向的。

首先，要大致分析一個問題是否可能用動態規劃解決。如果一個問題難以確定子問題，或問題與其子問題的特殊解之間毫無關系，就要考慮使用其它方法來解決(如搜索或其它方法等)。做一個大概的判斷是有必要的，可以防止在這上面白花時間。通常一個可以有效使用動態規劃解決的問題基本上滿足以下幾方面的特性：

子問題的最優解僅與起點和終點(或有相應代表意義的量)有關而與到達起點、終點的路徑無關。

大量子問題是重疊的，否則難以體現動態規劃的優越性。

下面以“字符識別”問題為例進行分析一般情況下動態規劃思路的建立。

字符識別問題，題目大意是：在FONT.DAT中是對o(空格)、A—Z這27個符號的字形說明。對每一個符號的字符點陣，用20行每行20個“0”或者“1”表示。在另一個輸入文件中，描述了一串字符的點陣圖象(共N行)，但字符可能是“破損的”，即有些0變成了1，而有些1變成了0。每行固定也為20個“0”或“1”，但每一個字符對應的行可能出現如下情形：

仍為20行，此時沒有丟失的行也沒有被復制的行；

為19行，此時有一行被丟失了；

為21行，此時有一行被復制了，復制兩行可能出現不同的破損。

要求輸出，在一個假定的行的分割情況下，使得“0”與“1”的反相最少的方案所對應的識別結果(字符串)。

在初步確定這個問題可以用動態規劃思想解決之后，我認為可以考慮用數學的方法(或觀點)來刻劃這個問題，比如通常的最優化問題(這也是動態規劃解決的主要問題)，總會有一個最優化的標準，動態規劃要通過遞推來實現，就要求分析確定這個狀態所需要的量。比如字符識別問題，在問題規模下相當于求N行的一種分割與對應方法，因而很自然地，考慮前幾行就成了一個確定狀態的量。最優的標準題中已經給出，即在某種假設(包括分割方法與對應識別方法)下，使得“0”與“1”反相數最少。如果把這個度量標準看作一個函數，這實際上就是一個最優化函數(指標函數)，最優化函數的值依賴于自變量，即確定狀態的量。自變量的個數(這里是一個，即行數，考慮前幾行之意)，要因題而異，關鍵是要有效地確定狀態，在這種狀態下，因保證靠這些量已經能夠確定最優化函數的值，即最優化函數在這些量確定的時候理論上應有確定的值，否則量是不夠的或要使用其它量來刻劃，而即使能夠完全確定，但在建立遞推關系式時發生困難，也要根據困難相應調整確定最優化函數值的自變量。而反過來，如果設定了過多的量來確定最優化函數值，那么，動態規劃的效率將會大大下降，或者解了許多不必要解的子問題，或者將重疊子問題變成了在這種自變量條件下的非重疊子問題，從而大大降低效率，甚至完全失去動態規劃的高效。在這個例子中，對于前L行，此最優化函數顯然有確定的值。

動態規劃的遞推的一種重要思想是將復雜的問題分解為其子問題。因而確定子問題空間及建立遞推關系式是十分重要的。根據確定最優化函數值的自變量，往往對子問題空間有著暗示的作用。通常，通過對最接近問題的這步進行倒推，可以得到這個問題規模減小一些的子問題，不斷這樣迭-慮，就往往能夠體會到問題的子問題空間。而在這個過程中，通過這種倒推分析，也比較容易得出這種遞推關系。需要指出，這僅僅是對一些題目解題思考過程的總結，不同的題目原則上仍應區別對待。比如字符識別問題，考慮n行該最優化函數值時，注意到最終一定是按照字符分割與識別的，因而最后一個字符或者是19行，或者是20行，再或者是21行，僅這樣三種可能情況，依次考慮這三種分割方法，對于切割下來的這一段對應于一個字符，對于每一種切割方案，當然應該選擇最匹配的字符(否則，如果不使用反相情況最少的字符作為匹配結果而導致全局的最優，那么只要在這一步換成反相情況最少的字符，就得到比假定的“最優”更優的結果，從而導致矛盾)。在去除一個字符后，行數有所減少，而這些行去匹配字符顯然也應當使用最優的匹配(可以用反證法證明，與前述類似)，于是得到一個與原問題相似(同確定變量，同最優化標準)但規模較小的子問題，與此同時子問題與原問題的遞推關系事實上也得到了建立：

f[i]:=min{Compare19[i-19+1]+f[i-19],Compare20[i-20+1]+f[i-20], Compare21[i-21+1]+f[i-21]}

f[i]表示對前i行進行匹配的最優化函數值；

Compare19[i]、Compare20[i]、Compare21[i]分別表示從i行開始的19行、20行、21行與這三種匹配方式下最接近的字符的反相的“0”與“1”的個數。

初始情況，f[0]=0，對于不可能匹配的行數，用一個特殊的大數表示即可。當然，本題的問題主要還不在于動態規劃的基本思考上(這里只是通過這個例子，講一下對于不少動態規劃問題的一種基本的思考方向)，還有數學建模(用2進制表示0、1串)等

有時雖然按上述思路得出的確定狀態的量已經能夠使最優化函數具有確定的值，但是在建立遞推關系時發生困難，通過引入新的變量或調整已有變量，也是一條克服困難的途徑。比如，NOI’97的一題“積木游戲”，題目大意是：

積木是一個長方體，已知N個有編號的積木的三邊(a、b、c邊)長，要求出用N塊中的若干塊堆成M(1≤M≤N≤100)堆，使總高度最大的高度值，且滿足：

第K堆中任意一塊的編號大于第K+1堆中任意一塊積木的編號；

任意相鄰兩塊，下面的塊的上表面要能包含上面的那塊的下表面，且下面的塊的編號要小于上面積木的編號。

因為題目要求編號小的堆的積木編號較大，這不太自然，在不改變結果的前提下，把題目改作編號小的堆的積木編號較小，這顯然不會影響到最終的高度和，而且，此時每一種合理的堆放方法可看作，按編號遞增的順序選擇若干積木，按堆編號遞增的順序逐堆放置，每堆中積木依次在前一個上面堆放而最終形成一種堆放方案。使用上面一般的分析方法，很容易看出，考慮前i個木塊放置成前j堆，這樣，i、j兩個量顯然能夠確定最優函數的值，然而遞推關系卻不易直接建立，稍作分析就會發現，問題主要出在第i塊到底能否堆放到其子問題(i-1,j作變量確定的狀態)的最優解方案的最后一堆上。如果考慮增加該序列最后一塊的頂部的長與寬的(最小)限制這兩個變量，建立遞推關系并不困難，然而，很明顯，遞推過程中大量結果并未被用到，這就人為地擴大了子問題空間，不僅給存儲帶來麻煩，而且效率也很低。其實，建立遞推需要的僅僅是在子問題解最后一堆頂部能否容納當前積木塊，而題中可能產生的這種限制性的面最多僅有3*100+1(無限制)=301種情況，這樣在多引入一個“最后一堆頂部能夠容納下第k種面的要求”這個量后，遞推關系只要分當前塊另起一堆、當前塊加在前一堆上(如果可能的話)和當前塊不使用這三種情況就可以了。

此外，有些問題可能會出現僅靠這種調整遞推關系仍難以建立，這時，通過增加其它量或函數來建立遞推關系式也是一種思考方向(類似于數學歸納法證明時的“加強命題”)。因為，用動態規劃解題的一個重要特征是通過遞推，而遞推是利用原有結果得到新結果的過程。如果在理論上可以證明，一個難以直接實現遞推的問題可以通過引入新的遞推關系，同時將兩者解決，這看起來把問題復雜化了，而實際上由于對于每一步遞推，在增加了解決的問題的同時也增加了條件（以前解決的值），反而使遞推容易進行。舉例說明，“多邊形”一題，大意如下：

有一個多邊形（N邊形），頂點上放整數，邊上放“+”或“*”，要尋找一種逐次運算合并的順序，通過N-1次運算，使最后結果最大。

如果單純考慮用MAX[I,L]，從I開始進行L個運算所得的最大值，則難以實現遞推，而根據數學知識，引入了MIN[I,L]為從I開始進行L個運算所得的最小值，在進行遞推時，卻能夠有效地用較小的I，L來得到較大時的結果，從而事實上同時解決了最小值與最大值兩個問題。

遞推關系式如下：(考慮I從1到N,L從1到N-1)

考慮t(最后一步運算位置)從0到L-1：

如果最后一步運算為“+”則：

min(i,L)=最小值{min(i,t)+min((i+t+1-1) mod N+1,L-t-1)}

max(i,L)=最大值{max(i,t)+max((i+t+1-1) mod N+1,L-t-1)}

如果最后一步運算為“*”則：

min(i,L)=最小值{min(i,t)*min((i+t+1-1) mod N+1,L-t-1),

min(i,t)*max((i+t+1-1) mod N+1,L-t-1),

max(i,t)*min((i+t+1-1) mod N+1,L-t-1),

max(i,t)*max((i+t+1-1) mod N+1,L-t-1)}

max(i,L)=最大值{min(i,t)*min((i+t+1-1) mod N+1,L-t-1),

min(i,t)*max((i+t+1-1) mod N+1,L-T-1)

max(i,t)*min((i+t+1-1) mod N+1,L-t-1),

max(i,t)*max((i+t+1-1) mod N+1,L-t-1)}

此外，動態規劃通過遞推來實現，因而問題與子問題越相似，越有規律就越容易進行操作。因而對于某些自身的階段和規律不怎么明顯的問題，可以通過一個預處理，使其變得更整齊，更易于實現。例如，ACM’97亞洲賽區/上海區競賽一題“正則表達式(Regular Expression)的匹配”問題，題目大意是：

正則表達式是含有通配符的表達式，題目定義的廣義符有：

.?????? 表示任何字符

[c1-c2]? 表示字符c1與c2間的任一字符

[^c1-c2] 表示不在字符c1與c2間的任一字符

*?????? 表示它前面的字符可出現0或多次

+?????? 表示它前面的字符可出現一次或多次

\??????? 表示它后面的字符以一個一般字符對待。

對一個輸入串，尋找最左邊的與正則表達式匹配的串(相同條件下要最長的)。這里如果不作預處理，則有時一個廣義符可對應多個字符，有時又是多個廣義符僅對應一個字符，給系統化處理帶來很多麻煩。因而有必要對正則表達式進行標準化，使得或者某個結點僅對應一個字符，或者用一特殊標記表明它可以重復多次。定義記錄類型：

NodeType=Record

StartChar: Char; {開始字符}

EndChar: Char;? {結束字符}

Belong:? Boolean {是否屬于}

Times:? Boolean; {False: 必須一次; True:可以多次，也可以不出現}

End;

對輸入數據預處理之后，建立遞推關系就不太困難了。用Pro[i,j]表示前i

個正則表達式結點對以第j個字符為終點的子串的匹配情況(True/False)，對于為True的情況，同時指明此條件下最先的開始位置。如果第i個正則表達式結點是僅出現一次的，那么，如果它與第j個字符不匹配，則該值為False，否則，它與Pro[i-1,j-1]相同。(初始時Pro[0,x]=True)。如果它是可重復多次的，那么它可以被解釋成0個或多個字符。在它自身與相應位置的0個或多個字符匹配的條件下依次考慮這些可能情況，只要其中含True，則Pro[i,j]為True，同時記錄下這些達到True的情況中起點最先的。按此遞推，直到i達到結點個數。

三、動態規劃實現中的問題

動態規劃解決問題在有了基本的思路之后，一般來說，算法實現是比較好考慮的，但有時也會遇到一些問題，而使算法難以實現。動態規劃思想設計的算法從整體上來看基本都是按照得出的遞推關系式進行遞推，這種遞推，相對于計算機來說，只要設計得當，效率往往是比較高的，這樣在時間上溢出的可能性不大，而相反地，動態規劃需要很大的空間以存儲中間產生的結果，這樣可以使包含同一個子問題的所有問題共用一個子問題解，從而體現動態規劃的優越性，但這是以犧牲空間為代價的，為了有效地訪問已有結果，數據也不易壓縮存儲，因而空間矛盾是比較突出的。另一方面，動態規劃的高時效性往往要通過大的測試數據體現出來（以與搜索作比較），因而，對于大規模的問題如何在基本不影響運行速度的條件下，解決空間溢出的問題，是動態規劃解決問題時一個普遍會遇到的問題。

對于這個問題，我認為，可以考慮從以下一些方面去嘗試：

一個思考方向是盡可能少占用空間。如從結點的數據結構上考慮，僅僅存儲必不可少的內容，以及數據存儲范圍上精打細算(按位存儲、壓縮存儲等)。當然這要因題而異，進行分析。另外，在實現動態規劃時，一個我們經常采用的方法是用一個與結點數一樣多的數組來存儲每一步的決策，這對于倒推求得一種實現最優解的方法是十分方便的，而且處理速度也有一些提高。但是在內存空間緊張的情況下，我們就應該抓住問題的主要矛盾。省去這個存儲決策的數組，而改成在從最優解逐級倒推時，再計算一次，選擇某個可能達到這個值的上一階段的狀態，直到推出結果為止。這樣做，在程序編寫上比上一種做法稍微多花一點時間，運行的時效也可能會有一些(但往往很小)的下降，但卻換來了很多的空間。因而這種思想在處理某些問題時，是很有意義的。

但有時，即使采用這樣的方法也會發現空間溢出的問題。這時就要分析，這些保留下來的數據是否有必要同時存在于內存之中。因為有很多問題，動態規劃遞推在處理后面的內容時，前面比較遠處的內容實際上是用不著的。對于這類問題，在已經確信不會再被使用的數據上覆蓋數據，從而使空間得以重復利用，如果能有效地使用這一手段，對于相當大規模的問題，空間也不至于溢出。（為了求出最優方案，保留每一步的決策仍是必要的，這同樣需要空間。）一般地說，這種方法可以通過兩種思路來實現。一種是遞推結果僅使用Data1和Data2這樣兩個數組，每次將Data1作為上一階段，推得Data2數組，然后，將Data2通過復制覆蓋到Data1之上，如此反復，即可推得最終結果。這種做法有一個局限性，就是對于遞推與前面若干階段相關的問題，這種做法就比較麻煩；而且，每遞推一級，就需要復制很多的內容，與前面多個階段相關的問題影響更大。另外一種實現方法是，對于一個可能與上N階段相關的問題，建立數組Data[0..N]，其中各項即為與原Data1/Data2相同的內容。這樣不采用這種內存節約方式時對于下標K的訪問只要對應成對下標K mod (N+1)的訪問，就可以了。與不作這種處理的方法相比，對于程序修改的代碼很少，速度幾乎不受影響(用電腦做MOD運算是很快的)，而且需要保留不同的階段數也都能很容易實現。這種手段對不少題目都適用，比如：NOI’98的“免費餡餅”，題目大意是：

有一個舞臺，寬度W格(1≤W≤99的奇數),高度H格(1≤H≤100)，游戲者在時刻0時位于舞臺正中，每個單位時間可以從當時位置向左移2格、向左移1格、保持不動、向右移1格或者向右移2格，每個餡餅會告知初始下落的時間和位置以及下落速度(1秒內下移的格子數)和分值。僅在某1秒末與游戲者位于同一格內的餡餅才被認為是接住的。求一種移動方案，使得分最大。注意：餡餅已按初始下落時間排序。

從問題來看，想到動態規劃并不是很困難的。但是，題中規定初始下落時間從0到1000，而且考慮下落到最后可能時間要到1100左右,而寬度可達99，以時間-位置作為狀態決定因素進行遞推，速度不會慢，但如果采用初始數據經預處理后的結果(即在何時到何地可得多少分的描述數組)用一個數組，動態規劃遞推用一個數組，記錄每步決策用一個數組，因得分題中未指出可能的大小，如果采用前兩個Longint型，最后一個Shortint型，所須內存約為1100*99*9字節，即約957KB，這顯然是不可能存得下的。但是注意到在進行遞推時，一旦某一個(時間，位置)對應的最大分值一確定，這個位置的原始數據就不再有用，因而兩者可以合二為一，從而只要1100*99*5字節，即約532KB。這樣對于題目規模的問題就勉強可以解決了。 當然，如果更進一步思考，其實這個問題中遞推是僅與上一個時間有關的，而餡餅實際上僅使用了當前位置的值。由于初始下落時間已經排序，那么當讀到初始下落時間晚于當前處理時間時，就不必馬上讀入。為了避免重復和無規律地讀盤和內存開銷過大，只要記錄下當前之后約100個時間單位內的情況就可以了，使用前面所說的循環使用內存的方法，只要101*99*4+99*2*2=40392字節，不到40KB，而對于每一個時間僅需99個shortint存儲決策即可,就算把問題規模提高到3000或者4000個時間單位也能順利出解。 (源程序見附錄中的程序5)

當采用以上方法仍無法解決內存問題時，也可以采用對內存的動態申請來使絕大多數測試點能有效出解(而且，使用動態內存還有一點好處，就是在重復使用內存而進行交換時，可以只對指針進行交換，而不復制數據)，這在競賽中也是十分有效的。

四、總結

動態規劃是一種重要的程序設計思想。但是，由于它沒有確定的算法形式，因而也就有較大的靈活性，但它的本質卻具有高度的相似性。所以，學習和使用這一思想方法，關鍵在于在理解和把握其本質的基礎上靈活運用。本文雖然談到了一些思想方法，但這些僅是對一些較普遍問題的討論，針對具體問題進行具體分析建立數學模型才是最重要而關鍵之處。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。