動(dòng)態(tài)規(guī)劃解決的問題

1、【關(guān)鍵字】動(dòng)態(tài)規(guī)劃 構(gòu)思實(shí)現(xiàn)【摘要】本文討論了動(dòng)態(tài)規(guī)劃這一思想的核心內(nèi)容和其基本特點(diǎn)，探討了動(dòng)態(tài)規(guī)劃思想的適用范圍， 動(dòng)態(tài)規(guī)劃子問題空間和遞推關(guān)系式確立的一般思路。通過例子說明在子問題確立過程中的一些問題的解決 辦法：通過加強(qiáng)命題或適當(dāng)調(diào)節(jié)確定狀態(tài)的變量等手段幫助建立動(dòng)態(tài)規(guī)劃方程，通過預(yù)處理使動(dòng)態(tài)規(guī)劃的 過程容易實(shí)現(xiàn)等。接著，分析動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)中可能出現(xiàn)的空間溢出問題及一些解決辦法?？偨Y(jié)指出，動(dòng)態(tài) 規(guī)劃這一思想，關(guān)鍵還在于對(duì)不同的問題建立有效的數(shù)學(xué)模型，在把握本質(zhì)的基礎(chǔ)上靈活運(yùn)用。一、引言動(dòng)態(tài)規(guī)劃是一種重要的程序設(shè)計(jì)思想，具有廣泛的應(yīng)用價(jià)值。使用動(dòng)態(tài)規(guī)劃思想來設(shè)計(jì)算法，對(duì)于不 少問題往往具有高時(shí)

2、效，因而，對(duì)于能夠使用動(dòng)態(tài)規(guī)劃思想來解決的問題，使用動(dòng)態(tài)規(guī)劃是比較明智的選 擇。能夠用動(dòng)態(tài)規(guī)劃解決的問題，往往是最優(yōu)化問題，且問題的最優(yōu)解（或特定解）的局部往往是局部問題 在相應(yīng)條件下的最優(yōu)解，而且問題的最優(yōu)解與其子問題的最優(yōu)解要有一定的關(guān)聯(lián)，要能建立遞推關(guān)系。如 果這種關(guān)系難以建立，即問題的特定解不僅依賴于子問題的特定解，而且與子問題的一般解相關(guān)，那么， 一方面難以記錄下那么多的“一般解”，另一方面，遞推的效率也將是很低的；此外，為了體現(xiàn)動(dòng)態(tài)規(guī)劃的 高時(shí)效，子問題應(yīng)當(dāng)是互相重疊的，即很多不同的問題共享相同的子問題。（如果子問題不重疊，則宜使用 其它方法，如分治法等。）動(dòng)態(tài)規(guī)劃一般可以通過兩種

3、手段比較高效地實(shí)現(xiàn)，其一是通過自頂向下記憶化的方法，即通過遞歸或 不遞歸的手段，將對(duì)問題最優(yōu)解的求解，歸結(jié)為求其子問題的最優(yōu)解，并將計(jì)算過的結(jié)果記錄下來，從而 實(shí)現(xiàn)結(jié)果的共享；另一種手段，也就是最主要的手段，通過自底向上的遞推的方式，由于這種方式代價(jià)要 比前一種方式小，因而被普遍采用，下面的討論均采用這種方式實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃之所以具有高時(shí)效，是因 為它在將問題規(guī)模不斷減小的同時(shí)，有效地把解記錄下來，從而避免了反復(fù)解同一個(gè)子問題的現(xiàn)象，因而 只要運(yùn)用得當(dāng)，較之搜索而言，效率就會(huì)有很大的提高。動(dòng)態(tài)規(guī)劃的思想，為我們解決與重疊子問題相關(guān)的最優(yōu)化問題提供了一個(gè)思考方向：通過迭代考慮子 問題，將問題規(guī)模減

4、小而最終解決問題。適于用動(dòng)態(tài)規(guī)劃解決的問題，是十分廣泛的。動(dòng)態(tài)規(guī)劃的思想本 身是重要的，但更重要的是面對(duì)具體問題的具體分析。要分析問題是否具備使用動(dòng)態(tài)規(guī)劃的條件，確定使 用動(dòng)態(tài)規(guī)劃解題的子問題空間和遞推關(guān)系式等，以及在（常規(guī)）內(nèi)存有限的計(jì)算機(jī)上實(shí)現(xiàn)這些算法。下面分 別就構(gòu)思和實(shí)現(xiàn)兩個(gè)方面進(jìn)一步探討動(dòng)態(tài)規(guī)劃這一思想。二、動(dòng)態(tài)規(guī)劃解題的構(gòu)思當(dāng)我們面對(duì)一個(gè)問題考慮用動(dòng)態(tài)規(guī)劃時(shí)，十分重要的一點(diǎn)就是判斷這個(gè)問題能否用動(dòng)態(tài)規(guī)劃高效地解 決。用動(dòng)態(tài)規(guī)劃構(gòu)思算法時(shí)，往往要考慮到這個(gè)問題所涉及到的子問題（子問題空間），以及如何建立遞推 式，并最終實(shí)現(xiàn)算法。其實(shí)，這些過程往往是交織在一起的，子問題空間與遞推關(guān)系本

5、身就是緊密相聯(lián)的， 為了有效地建立起遞推關(guān)系，有時(shí)就要調(diào)整子問題空間；而根據(jù)大致確定的子問題空間又可以啟發(fā)我們建 立遞推關(guān)系式。而能否最終用一個(gè)遞推關(guān)系式來聯(lián)系問題與其子問題又成了判斷一個(gè)問題能否使用動(dòng)態(tài)規(guī) 劃思想解決的主要依據(jù)。因而孤立地來看這其中的每一部分，硬把思考過程人為地分成幾個(gè)部分，是困難 的，也是不必要的。而且動(dòng)態(tài)規(guī)劃這種思想方法，沒有固定的數(shù)學(xué)模型，要因題而異，因而也就不可能歸 納出一種“萬能”的方法。但是對(duì)大多數(shù)問題而言，還是能夠有一個(gè)基本的思考方向的。首先，要大致分析一個(gè)問題是否可能用動(dòng)態(tài)規(guī)劃解決。如果一個(gè)問題難以確定子問題，或問題與其子 問題的特殊解之間毫無關(guān)系，就要考慮使

6、用其它方法來解決（如搜索或其它方法等）。做一個(gè)大概的判斷是 有必要的，可以防止在這上面白花時(shí)間。通常一個(gè)可以有效使用動(dòng)態(tài)規(guī)劃解決的問題基本上滿足以下幾方 面的特性：1、子問題的最優(yōu)解僅與起點(diǎn)和終點(diǎn)（或有相應(yīng)代表意義的量）有關(guān)而與到達(dá)起點(diǎn)、終點(diǎn)的路徑無關(guān)。2、大量子問題是重疊的，否則難以體現(xiàn)動(dòng)態(tài)規(guī)劃的優(yōu)越性。下面以IOI97的“字符識(shí)別”問題為例進(jìn)行分析一般情況下動(dòng)態(tài)規(guī)劃思路的建立。IOI97的字符識(shí)別問題，題目大意是：在FONT.DAT中是對(duì)?（空格）、AZ這27個(gè)符號(hào)的字形說明。 對(duì)每一個(gè)符號(hào)的字符點(diǎn)陣，用20行每行20個(gè)“0”或者“1”表示。在另一個(gè)輸入文件中，描述了一串字符的 點(diǎn)陣圖象（

7、共N行），但字符可能是“破損的”，即有些0變成了 1，而有些1變成了 0。每行固定也為20個(gè)“0” 或“1”，但每一個(gè)字符對(duì)應(yīng)的行可能出現(xiàn)如下情形：?仍為20行，此時(shí)沒有丟失的行也沒有被復(fù)制的行；?為19行，此時(shí)有一行被丟失了；?為21行，此時(shí)有一行被復(fù)制了，復(fù)制兩行可能出現(xiàn)不同的破損。要求輸出，在一個(gè)假定的行的分割情況下，使得“0”與“1”的反相最少的方案所對(duì)應(yīng)的識(shí)別結(jié)果（字符串）。在初步確定這個(gè)問題可以用動(dòng)態(tài)規(guī)劃思想解決之后，我認(rèn)為可以考慮用數(shù)學(xué)的方法（或觀點(diǎn)）來刻劃這 個(gè)問題，比如通常的最優(yōu)化問題（這也是動(dòng)態(tài)規(guī)劃解決的主要問題），總會(huì)有一個(gè)最優(yōu)化的標(biāo)準(zhǔn)，動(dòng)態(tài)規(guī)劃 要通過遞推來實(shí)現(xiàn)，就要求

8、分析確定這個(gè)狀態(tài)所需要的量。比如字符識(shí)別問題，在問題規(guī)模下相當(dāng)于求N 行的一種分割與對(duì)應(yīng)方法，因而很自然地，考慮前幾行就成了一個(gè)確定狀態(tài)的量。最優(yōu)的標(biāo)準(zhǔn)題中已經(jīng)給 出，即在某種假設(shè)（包括分割方法與對(duì)應(yīng)識(shí)別方法）下，使得“0”與“1”反相數(shù)最少。如果把這個(gè)度量標(biāo)準(zhǔn)看作 一個(gè)函數(shù)，這實(shí)際上就是一個(gè)最優(yōu)化函數(shù)（指標(biāo)函數(shù)），最優(yōu)化函數(shù)的值依賴于自變量，即確定狀態(tài)的量。 自變量的個(gè)數(shù)（這里是一個(gè)，即行數(shù)，考慮前幾行之意），要因題而異，關(guān)鍵是要有效地確定狀態(tài)，在這種 狀態(tài)下，因保證靠這些量已經(jīng)能夠確定最優(yōu)化函數(shù)的值，即最優(yōu)化函數(shù)在這些量確定的時(shí)候理論上應(yīng)有確 定的值，否則量是不夠的或要使用其它量來刻劃，而

9、即使能夠完全確定，但在建立遞推關(guān)系式時(shí)發(fā)生困難， 也要根據(jù)困難相應(yīng)調(diào)整確定最優(yōu)化函數(shù)值的自變量。而反過來，如果設(shè)定了過多的量來確定最優(yōu)化函數(shù)值， 那么，動(dòng)態(tài)規(guī)劃的效率將會(huì)大大下降，或者解了許多不必要解的子問題，或者將重疊子問題變成了在這種 自變量條件下的非重疊子問題，從而大大降低效率，甚至完全失去動(dòng)態(tài)規(guī)劃的高效。在這個(gè)例子中，對(duì)于 前L行，此最優(yōu)化函數(shù)顯然有確定的值。動(dòng)態(tài)規(guī)劃的遞推的一種重要思想是將復(fù)雜的問題分解為其子問題。因而確定子問題空間及建立遞推關(guān) 系式是十分重要的。根據(jù)確定最優(yōu)化函數(shù)值的自變量，往往對(duì)子問題空間有著暗示的作用。通常，通過對(duì) 最接近問題的這步進(jìn)行倒推，可以得到這個(gè)問題規(guī)模

10、減小一些的子問題，不斷這樣迭代考慮，就往往能夠 體會(huì)到問題的子問題空間。而在這個(gè)過程中，通過這種倒推分析，也比較容易得出這種遞推關(guān)系。需要指 出，這僅僅是對(duì)一些題目解題思考過程的總結(jié)，不同的題目原則上仍應(yīng)區(qū)別對(duì)待。比如字符識(shí)別問題，考 慮n行該最優(yōu)化函數(shù)值時(shí)，注意到最終一定是按照字符分割與識(shí)別的，因而最后一個(gè)字符或者是19行，或 者是20行，再或者是21行，僅這樣三種可能情況，依次考慮這三種分割方法，對(duì)于切割下來的這一段對(duì) 應(yīng)于一個(gè)字符，對(duì)于每一種切割方案，當(dāng)然應(yīng)該選擇最匹配的字符（否則，如果不使用反相情況最少的字符 作為匹配結(jié)果而導(dǎo)致全局的最優(yōu)，那么只要在這一步換成反相情況最少的字符，就得到

11、比假定的“最優(yōu)”更 優(yōu)的結(jié)果，從而導(dǎo)致矛盾）。在去除一個(gè)字符后，行數(shù)有所減少，而這些行去匹配字符顯然也應(yīng)當(dāng)使用最優(yōu) 的匹配（可以用反證法證明，與前述類似），于是得到一個(gè)與原問題相似（同確定變量，同最優(yōu)化標(biāo)準(zhǔn)）但規(guī)模 較小的子問題，與此同時(shí)子問題與原問題的遞推關(guān)系事實(shí)上也得到了建立：fi:=minCompare19i-19+1+fi-19,Compare20i-20+1+fi-20, Compare21i-21+1+fi-21fi表示對(duì)前i行進(jìn)行匹配的最優(yōu)化函數(shù)值；Compare19i、Compare20i、Compare21i分別表示從i行開始的19行、20行、21行與這三種匹配方 式下最接近

12、的字符的反相的“0 ”與“1”的個(gè)數(shù)。初始情況，f0=0，對(duì)于不可能匹配的行數(shù)，用一個(gè)特殊的大數(shù)表示即可。當(dāng)然，本題的問題主要還不 在于動(dòng)態(tài)規(guī)劃的基本思考上（這里只是通過這個(gè)例子，講一下對(duì)于不少動(dòng)態(tài)規(guī)劃問題的一種基本的思考方 向），還有數(shù)學(xué)建模（用2進(jìn)制表示0、1串）等（源程序見附錄中的程序1）。有時(shí)雖然按上述思路得出的確定狀態(tài)的量已經(jīng)能夠使最優(yōu)化函數(shù)具有確定的值，但是在建立遞推關(guān)系 時(shí)發(fā)生困難，通過引入新的變量或調(diào)整已有變量，也是一條克服困難的途徑。比如，NOI97的一題“積木 游戲”，題目大意是：積木是一個(gè)長方體，已知N個(gè)有編號(hào)的積木的三邊（a、b、c邊）長，要求出用N塊中的若干塊堆成 M

13、（1MN100）堆，使總高度最大的高度值，且滿足：?第K堆中任意一塊的編號(hào)大于第K+1堆中任意一塊積木的編號(hào)；?任意相鄰兩塊，下面的塊的上表面要能包含上面的那塊的下表面，且下面的塊的編號(hào)要小于上面積 木的編號(hào)。因?yàn)轭}目要求編號(hào)小的堆的積木編號(hào)較大，這不太自然，在不改變結(jié)果的前提下，把題目改作編號(hào)小 的堆的積木編號(hào)較小，這顯然不會(huì)影響到最終的高度和，而且，此時(shí)每一種合理的堆放方法可看作，按編 號(hào)遞增的順序選擇若干積木，按堆編號(hào)遞增的順序逐堆放置，每堆中積木依次在前一個(gè)上面堆放而最終形 成一種堆放方案。使用上面一般的分析方法，很容易看出，考慮前i個(gè)木塊放置成前j堆，這樣，i、j兩個(gè) 量顯然能夠確定

14、最優(yōu)函數(shù)的值，然而遞推關(guān)系卻不易直接建立，稍作分析就會(huì)發(fā)現(xiàn)，問題主要出在第i塊 到底能否堆放到其子問題(i-1,j作變量確定的狀態(tài))的最優(yōu)解方案的最后一堆上。如果考慮增加該序列最后一 塊的頂部的長與寬的(最小)限制這兩個(gè)變量，建立遞推關(guān)系并不困難，然而，很明顯，遞推過程中大量結(jié) 果并未被用到，這就人為地?cái)U(kuò)大了子問題空間，不僅給存儲(chǔ)帶來麻煩，而且效率也很低。其實(shí)，建立遞推 需要的僅僅是在子問題解最后一堆頂部能否容納當(dāng)前積木塊，而題中可能產(chǎn)生的這種限制性的面最多僅有 3*100+1 (無限制)=301種情況，這樣在多引入一個(gè)“最后一堆頂部能夠容納下第k種面的要求”這個(gè)量后，遞 推關(guān)系只要分當(dāng)前塊另

15、起一堆、當(dāng)前塊加在前一堆上(如果可能的話)和當(dāng)前塊不使用這三種情況就可以了。 (源程序參見所附程序2)此外，有些問題可能會(huì)出現(xiàn)僅靠這種調(diào)整遞推關(guān)系仍難以建立，這時(shí)，通過增加其它量或函數(shù)來建立 遞推關(guān)系式也是一種思考方向(類似于數(shù)學(xué)歸納法證明時(shí)的“加強(qiáng)命題”)。因?yàn)?，用?dòng)態(tài)規(guī)劃解題的一個(gè)重要 特征是通過遞推，而遞推是利用原有結(jié)果得到新結(jié)果的過程。如果在理論上可以證明，一個(gè)難以直接實(shí)現(xiàn) 遞推的問題可以通過引入新的遞推關(guān)系，同時(shí)將兩者解決，這看起來把問題復(fù)雜化了，而實(shí)際上由于對(duì)于 每一步遞推，在增加了解決的問題的同時(shí)也增加了條件(以前解決的值)，反而使遞推容易進(jìn)行。舉例說明， IOI98中的“多邊形

16、”一題，大意如下：有一個(gè)多邊形(N邊形)，頂點(diǎn)上放整數(shù)，邊上放“+”或“*”，要尋找一種逐次運(yùn)算合并的順序，通過 N-1次運(yùn)算，使最后結(jié)果最大。如果單純考慮用MAXI,L，從I開始進(jìn)行L個(gè)運(yùn)算所得的最大值，則難以實(shí)現(xiàn)遞推，而根據(jù)數(shù)學(xué)知識(shí)， 引入了 MINI,L為從I開始進(jìn)行L個(gè)運(yùn)算所得的最小值，在進(jìn)行遞推時(shí)，卻能夠有效地用較小的I，L來得 到較大時(shí)的結(jié)果，從而事實(shí)上同時(shí)解決了最小值與最大值兩個(gè)問題。遞推關(guān)系式如下：(考慮I從1到N,L從1到N-1)考慮t(最后一步運(yùn)算位置)從0到L-1：如果最后一步運(yùn)算為“+”則：min(i,L)=最小值min(i,t)+min(i+t+1-1) mod N+

17、1,L-t-1)max(i,L)=最大值max(i,t)+max(i+t+1-1) mod N+1,L-t-1)如果最后一步運(yùn)算為“*”則：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)

18、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)(源程序見附錄中的程序3)此外，動(dòng)態(tài)規(guī)劃通過遞推來實(shí)現(xiàn)，因而問題與子問題越相似，越有規(guī)律就越容易進(jìn)行操作。因而對(duì)于 某些自身的階段和規(guī)律不怎么明顯的問題，可以通過一個(gè)預(yù)處理，使其變得更整齊，更易于實(shí)現(xiàn)。例如， ACM97亞洲賽區(qū)/上海區(qū)競(jìng)賽一題“正則表達(dá)式(Regular Expression)的匹配”問題，題目大意是：正則表達(dá)式是含有通配符的表達(dá)式，題目定義的廣義符有：?.表示任何字符? c1-c2表示字符cl與c2間的

19、任一字符? Ac1-c2表示不在字符cl與c2間的任一字符?*表示它前面的字符可出現(xiàn)0或多次?+表示它前面的字符可出現(xiàn)一次或多次?表示它后面的字符以一個(gè)一般字符對(duì)待。對(duì)一個(gè)輸入串，尋找最左邊的與正則表達(dá)式匹配的串（相同條件下要最長的）。這里如果不作預(yù)處理， 則有時(shí)一個(gè)廣義符可對(duì)應(yīng)多個(gè)字符，有時(shí)又是多個(gè)廣義符僅對(duì)應(yīng)一個(gè)字符，給系統(tǒng)化處理帶來很多麻煩。 因而有必要對(duì)正則表達(dá)式進(jìn)行標(biāo)準(zhǔn)化，使得或者某個(gè)結(jié)點(diǎn)僅對(duì)應(yīng)一個(gè)字符，或者用一特殊標(biāo)記表明它可以 重復(fù)多次。定義記錄類型：NodeType=RecordStartChar: Char; 開始字符EndChar: Char; 結(jié)束字符Belong: Bo

20、olean 是否屬于Times: Boolean; False:必須一次;True:可以多次，也可以不出現(xiàn)End;對(duì)輸入數(shù)據(jù)預(yù)處理之后，建立遞推關(guān)系就不太困難了。用Proi,j表示前i個(gè)正則表達(dá)式結(jié)點(diǎn)對(duì)以第j個(gè)字符為終點(diǎn)的子串的匹配情況（True/False），對(duì)于為True的情況，同時(shí)指 明此條件下最先的開始位置。如果第i個(gè)正則表達(dá)式結(jié)點(diǎn)是僅出現(xiàn)一次的，那么，如果它與第j個(gè)字符不匹 配，則該值為False，否則，它與Proi-1,j-1相同。（初始時(shí)Pro0,x=True）。如果它是可重復(fù)多次的，那么 它可以被解釋成0個(gè)或多個(gè)字符。在它自身與相應(yīng)位置的0個(gè)或多個(gè)字符匹配的條件下依次考慮這些可

21、能 情況，只要其中含True，則Proi,j為True，同時(shí)記錄下這些達(dá)到True的情況中起點(diǎn)最先的。按此遞推， 直到i達(dá)到結(jié)點(diǎn)個(gè)數(shù)。（源程序見所附程序4）三、動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)中的問題動(dòng)態(tài)規(guī)劃解決問題在有了基本的思路之后，一般來說，算法實(shí)現(xiàn)是比較好考慮的，但有時(shí)也會(huì)遇到一 些問題，而使算法難以實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃思想設(shè)計(jì)的算法從整體上來看基本都是按照得出的遞推關(guān)系式進(jìn)行 遞推，這種遞推，相對(duì)于計(jì)算機(jī)來說，只要設(shè)計(jì)得當(dāng)，效率往往是比較高的，這樣在時(shí)間上溢出的可能性 不大，而相反地，動(dòng)態(tài)規(guī)劃需要很大的空間以存儲(chǔ)中間產(chǎn)生的結(jié)果，這樣可以使包含同一個(gè)子問題的所有 問題共用一個(gè)子問題解，從而體現(xiàn)動(dòng)態(tài)規(guī)劃的優(yōu)越性，

22、但這是以犧牲空間為代價(jià)的，為了有效地訪問已有 結(jié)果，數(shù)據(jù)也不易壓縮存儲(chǔ)，因而空間矛盾是比較突出的。另一方面，動(dòng)態(tài)規(guī)劃的高時(shí)效性往往要通過大 的測(cè)試數(shù)據(jù)體現(xiàn)出來（以與搜索作比較），因而，對(duì)于大規(guī)模的問題如何在基本不影響運(yùn)行速度的條件下， 解決空間溢出的問題，是動(dòng)態(tài)規(guī)劃解決問題時(shí)一個(gè)普遍會(huì)遇到的問題。對(duì)于這個(gè)問題，我認(rèn)為，可以考慮從以下一些方面去嘗試：一個(gè)思考方向是盡可能少占用空間。如從結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)上考慮，僅僅存儲(chǔ)必不可少的內(nèi)容，以及數(shù) 據(jù)存儲(chǔ)范圍上精打細(xì)算（按位存儲(chǔ)、壓縮存儲(chǔ)等）。當(dāng)然這要因題而異，進(jìn)行分析。另外，在實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃 時(shí)，一個(gè)我們經(jīng)常采用的方法是用一個(gè)與結(jié)點(diǎn)數(shù)一樣多的數(shù)組來存儲(chǔ)每一

23、步的決策，這對(duì)于倒推求得一種 實(shí)現(xiàn)最優(yōu)解的方法是十分方便的，而且處理速度也有一些提高。但是在內(nèi)存空間緊張的情況下，我們就應(yīng) 該抓住問題的主要矛盾。省去這個(gè)存儲(chǔ)決策的數(shù)組，而改成在從最優(yōu)解逐級(jí)倒推時(shí)，再計(jì)算一次，選擇某 個(gè)可能達(dá)到這個(gè)值的上一階段的狀態(tài)，直到推出結(jié)果為止。這樣做，在程序編寫上比上一種做法稍微多花 一點(diǎn)時(shí)間，運(yùn)行的時(shí)效也可能會(huì)有一些（但往往很?。┑南陆?，但卻換來了很多的空間。因而這種思想在處 理某些問題時(shí)，是很有意義的。但有時(shí)，即使采用這樣的方法也會(huì)發(fā)現(xiàn)空間溢出的問題。這時(shí)就要分析，這些保留下來的數(shù)據(jù)是否有 必要同時(shí)存在于內(nèi)存之中。因?yàn)橛泻芏鄦栴}，動(dòng)態(tài)規(guī)劃遞推在處理后面的內(nèi)容時(shí)，前

24、面比較遠(yuǎn)處的內(nèi)容實(shí) 際上是用不著的。對(duì)于這類問題，在已經(jīng)確信不會(huì)再被使用的數(shù)據(jù)上覆蓋數(shù)據(jù)，從而使空間得以重復(fù)利用， 如果能有效地使用這一手段，對(duì)于相當(dāng)大規(guī)模的問題，空間也不至于溢出。（為了求出最優(yōu)方案，保留每一 步的決策仍是必要的，這同樣需要空間。）一般地說，這種方法可以通過兩種思路來實(shí)現(xiàn)。一種是遞推結(jié)果 僅使用Datal和Data2這樣兩個(gè)數(shù)組，每次將Datal作為上一階段，推得Data2數(shù)組，然后，將Data2通過 復(fù)制覆蓋到Datal之上，如此反復(fù)，即可推得最終結(jié)果。這種做法有一個(gè)局限性，就是對(duì)于遞推與前面若 干階段相關(guān)的問題，這種做法就比較麻煩；而且，每遞推一級(jí)，就需要復(fù)制很多的內(nèi)容，

25、與前面多個(gè)階段 相關(guān)的問題影響更大。另外一種實(shí)現(xiàn)方法是，對(duì)于一個(gè)可能與上N階段相關(guān)的問題，建立數(shù)組Data0.N， 其中各項(xiàng)即為與原Data1/Data2相同的內(nèi)容。這樣不采用這種內(nèi)存節(jié)約方式時(shí)對(duì)于下標(biāo)K的訪問只要對(duì)應(yīng) 成對(duì)下標(biāo)K mod （N+1）的訪問，就可以了。與不作這種處理的方法相比，對(duì)于程序修改的代碼很少，速度 幾乎不受影響（用電腦做MOD運(yùn)算是很快的），而且需要保留不同的階段數(shù)也都能很容易實(shí)現(xiàn)。這種手段對(duì) 不少題目都適用，比如：NOI98的“免費(fèi)餡餅”，題目大意是：有一個(gè)舞臺(tái)，寬度W 格（1Wlongint 轉(zhuǎn)換vari:integer;beginl:=0;for i:=1 to

26、20 doif stri=1 then inc(l,bini);end;function compare0(a,b:longint):byte; 比較a表示的行與b表示的行的反相個(gè)數(shù)vark:byte;i:integer;begina:=a xor b;k:=0;for i:=1 to 20 doif a and bini0 then inc(k);compare0:=kend;function compare20(k:integer; var ff:integer):word; 比較 20 彳亍的最優(yōu)結(jié)果vari,j,t,s:word;best:word; 當(dāng)前最優(yōu)beginff:=0;be

27、st:=maxint;for t:=1 to 27 do 考慮 27 個(gè)字符beginj:=0;for i:=1 to 20 dobegins:=compare0(font(t-1)*20+i,ddi+k-1); 比較一行inc(j,s); 累計(jì)差別end;if jbest then begin best:=j; ff:=t end; 如果更優(yōu)，記錄之end;compare20:=best;end;function compare19(k:integer; var ff:integer):word; 返回與 k 開始 19 行最接近的字符與差別值vari,j,t,s:word;best:wor

28、d;l1,l2:array 0.20 of word;bb,fx:integer;beginff:=0;best:=maxint;for t:=1 to 27 do 考慮 27 個(gè)字符beginj:=0;fillchar(l1,sizeof(l1),0);fillchar(l2,sizeof(l2),0);for i:=1 to 19 dofor j:=0 to 1 dopfi,j:=compare0(font(t-1)*20+i+j,ddk+i-1);記錄19行中第i行與對(duì)應(yīng)字形中第i行、第i+1行的差別l11:=pf1,0; l1i為破損字形前i行與標(biāo)準(zhǔn)字形前i行匹配的差別 for i:=

29、2 to 19 dol1i:=l1i-1+pfi,0;l219:=pf19,1; l2i為破損字第i行之后與標(biāo)準(zhǔn)字形第i+1行之后的字形匹配的差別for i:=18 downto 1 dol2i:=l2i+1+pfi,1;bb:=maxint;for i:=1 to 20 do 20 種缺少方式if l1i-1+l2ibb then bb:=l1i-1+l2i; 記錄最少的if bbbest then begin best:=bb; ff:=t end; 如果該字符較匹配，改進(jìn) BESTend;compare19:=bestend;function compare21(k:integer; v

30、ar ff:integer):word;返回與第k行開始的21行最匹配的字形與差別vari,j,t,s:word;best:word;l1,l2:array 0.22 of word;bb,fx:integer;beginff:=0;best:=maxint;for t:=1 to 27 do 考慮 27 個(gè)字形beginj:=0;fillchar(l1,sizeof(l1),0);fillchar(l2,sizeof(l2),0);fillchar(pf,sizeof(pf),0);for i:=1 to 21 dofor j:=0 to 1 doif not (i=21) and (j=0

31、) and not (i=1) and (j=1) then pfi,j:=compare0(font(t-1)*20+i-j,ddk+i-1);用破損字形第i行與標(biāo)準(zhǔn)字形第i行、第i-1行比較，記錄差別l11:=pf1,0; l1i為前i行與標(biāo)準(zhǔn)前i行匹配的差別for i:=2 to 20 dol1i:=l1i-1+pfi,0;l222:=0; l2i為第i行開始的內(nèi)容與標(biāo)準(zhǔn)從i-1行開始的內(nèi)容進(jìn)行匹配的差別for i:=21 downto 2 dol2i:=l2i+1+pfi,1;bb:=maxint;for i:=1 to 20 do 比較 20 種方式if l1i-1+l2i+1+pf

32、i,0bb then bb:=l1i-1+l2i+1+pfi,0;if bblongint 轉(zhuǎn)換end;read(f1,n); 讀入分析文件的各行for i:=1 to n dobeginreadln(f1,str);getnum(ddi); string-longint 轉(zhuǎn)換end;fillchar(pro,sizeof(pro),255); 初值 65535fillchar(sta,sizeof(sta),0); 每步分析出的最優(yōu)字符fillchar(bf,sizeof(bf),255); 每步分析出的最優(yōu)切割pro0:=0;sta0:=0;bf0:=0;for i:=19 to n do

33、 考慮 19 行至 n 行beginif (i=19) and (proi-1965535) then 如果切去一個(gè)19行字符后的情況可能begint:=compare19(i-19+1,ff); 比較從i-19+1起19行與標(biāo)準(zhǔn)結(jié)果最接近的結(jié)果與差別if t+proi-19=20) and (proi-2065535) then 如果切去一個(gè)20行字符后的情況可能 begint:=compare20(i-20+1,ff); 比較從i-20+1起20行與標(biāo)準(zhǔn)結(jié)果最接近的結(jié)果與差別if t+proi-20=21) and (proi-2165535) then 如果切去一個(gè)21行字符后的情況可能

34、 begint:=compare21(i-21+1,ff); 比較從i-21+1起21行與標(biāo)準(zhǔn)結(jié)果最接近的結(jié)果與差別if t+proi-21proi then 如果更優(yōu)，更新動(dòng)態(tài)規(guī)劃數(shù)組beginproi:=t+proi-21;stai:=ff;bfi:=i-21;end;end;end;str:=;i:=n;if pron=65535 then begin writeln(f2,No answer.); close(f1); close(f2); halt end; 如果無解while i0 do 倒推求解beginstr:=ccstai+str;i:=bfi;end;writeln(f2,

35、str); 輸出close(f1);close(f2)end.程序2 NOI97積木游戲說明：為防止出現(xiàn)內(nèi)存溢出，程序采用逐級(jí)遞推的方式。program Toy_Bricks_Game; 積木游戲typejmtype=array 0.100 of Anode;動(dòng)態(tài)規(guī)劃過程中僅保留與當(dāng)前最接近的一個(gè)階段的情況這是存儲(chǔ)一個(gè)階段的量的指針類型node=array 0.300 of longint;varf1,f2:text; 文件變量size:array 0.300,1.2 of word; 各個(gè)出現(xiàn)的面的記錄,0對(duì)應(yīng)無面積要求num:integer; 記錄的不同面數(shù)n,m:integer; 積木數(shù)

36、、堆成的堆數(shù)i,j,k,t:integer; 輔助變量p,q,r:jmtype; 遞推階段指針數(shù)組，每個(gè)保留一個(gè)階段(K值)，從p到q，r用于交換 aa:array 1.100,1.3 of word; 邊長數(shù)據(jù)ss:array 1.100,1.3 of word; 3個(gè)面對(duì)應(yīng)的面序號(hào)，對(duì)同樣長、寬的面作了優(yōu)化 procedure sort(i:integer); 對(duì)第i個(gè)長方體的三邊長排序varj,k,t:integer;beginfor j:=1 to 2 dofor k:=j+1 to 3 doif aai,jaai,k thenbegint:=aai,j;aai,j:=aai,k;aa

37、i,k:=tend;end;function add(a1,a2:integer):integer; 在面標(biāo)記中增添當(dāng)前面，并返回相應(yīng)的序號(hào)vari,j:integer;beginfor i:=1 to num doif (a1=sizei,1) and (a2=sizei,2) then begin add:=i; exit end;inc(num);sizenum,1:=a1;sizenum,2:=a2;add:=num;end;procedure preprocess; 預(yù)處理，將要處理的面記入vari,j,k:integer;beginnum:=0;for i:=1 to n dobe

38、ginsort(i);ssi,1:=add(aai,1,aai,2);ssi,2:=add(aai,1,aai,3);ssi,3:=add(aai,2,aai,3);end;end;procedure check(ii,nn,hh:integer); 檢查用ii積木的nn放置方式，是否有效varg,h:integer;beginif (pii-1A0=0) and (pii-1A0+hh=qiiAj) then qiiAj:=pii-1A0+hh; 考慮另成一堆if (pii-1Assii,nn=0) and (qii-1Assii,nn+hh=qiiAj) then qiiAj:=qii-1

39、Assii,nn+hh;考慮放在前一堆上end;beginassign(f1,ToyBrick.in);reset(f1);assign(f2,ToyBrick.out);rewrite(f2); 文件關(guān)聯(lián)、打開readln(f1,n,m); 讀入 N、M 值for i:=1 to n do 讀入邊長readln(f1,aai,1,aai,2,aai,3);size0,1:=0;size0,2:=0;preprocess; 生成各種待處理的面for i:=0 to n do 動(dòng)態(tài)內(nèi)存初始化beginnew(pi);new(qi);fillchar(qiA,sizeof(qiA),0);end;

40、for t:=1 to m do 連續(xù)遞推M階段，分成T堆beginr：=q;q：=p;p：=r; 交換 P、Qfor i:=0 to n do fillchar(qiA,sizeof(qiA),255); Q 初始化for i:=t to n do 考慮T個(gè)到N個(gè)積木beginfor j:=0 to num do 考慮最后“輸出”的面的約束條件beginqiAj：=qi-1Aj; 當(dāng)前積木不用if (aai,1=sizej,1) and (aai,2=sizej,2) then check(i,1,aai,3);if (aai,1=sizej,1) and (aai,3=sizej,2) t

41、hen check(i,2,aai,2);if (aai,2=sizej,1) and (aai,3=sizej,2) then check(i,3,aai,1);如果當(dāng)前積木的某方向放置可以滿足此要求，考慮按此方向放置該塊作為新的一堆的底或加在前一堆 上(如果可能)end;end;end;writeln(f2,qnA0); 輸出答案close(f1);close(f2)end.程序3 IOI98多邊形program Polygon; “多邊形”程序varf1,f2:text; 輸入、輸出文件變量n:integer; 頂點(diǎn)個(gè)數(shù)data:array 1.,50 of integer; 原始數(shù)據(jù)-

42、頂點(diǎn)sign:array 1.,50 of char; 原始數(shù)據(jù)-運(yùn)算符i,j,k,l:integer; 輔助變量t,s,p:integer; 輔助變量ans:set of 1.50; 可能達(dá)到最大值的第一次移動(dòng)的邊的序號(hào)best:integer; 當(dāng)前最優(yōu)解min,max:array 1.50,0.50 of integer;動(dòng)態(tài)規(guī)劃表格，mini,l表示從第i個(gè)頂點(diǎn)開始，經(jīng)過l個(gè)符號(hào)按合理運(yùn)算所得的結(jié)果的最小值；max 與之類似，但為最大值first:boolean; 首次輸出標(biāo)志procedure init; 初始化，讀入原始數(shù)據(jù)vari:integer;ch:char;beginrea

43、dln(f1,n);for i:=1 to n dobeginrepeatread(f1,ch);until ch ;signi:=ch; signi位于 datai與其后頂點(diǎn)間read(f1,datai);end;end;begin文件關(guān)聯(lián)、打開assign(f1,Polygon.in);reset(f1);assign(f2,Polygon.out);rewrite(f2);初始化init;賦初值best:=-maxint-1;ans:=;fillchar(max,sizeof(max),0);fillchar(min,sizeof(min),0); 數(shù)組初始化for j:=1 to n

44、dobeginmaxj,0:=dataj;minj,0:=dataj;end; 初值是不經(jīng)過運(yùn)算(l=0)的值for l:=1 to n-1 do 考慮長度由 1 到 n-1for k:=1 to n do 考慮起始點(diǎn)從1到nbeginmaxk,l:=-maxint-1;mink,l:=maxint;for t:=0 to l-1 do 考慮分開前半部分經(jīng)過的運(yùn)算數(shù)begincase sign(k+t+1-1) mod n+1 of 考慮分開處的符號(hào)t: 為加法beginif maxk,t+max(k+t+1-1) mod n+1,l-t-1maxk,l then maxk,l:=maxk,t

45、+max(k+t+1-1) mod n+1,l-t-1;最大值更新if mink,t+min(k+t+1-1) mod n+1,l-t-1maxk,l then maxk,l:=s;if sbest then begin best:=maxi,n-1; ans:=i endelse if maxi,n-1=best then include(ans,i); 更新全局的最大值writeln(f2,best); 輸出最大值first:=true;for i:=1 to n doif i in ans thenbeginif first then first:=falseelse write(f2,

46、);write(f2,i);end;writeln(f2); 輸出首次被移動(dòng)的邊close(f1);close(f2) 關(guān)閉文件end, 結(jié)束程序4 ACM97亞洲區(qū)/上海賽題 正則表達(dá)式匹配program Expression_Match; 正則表達(dá)式匹配程序typedatatype=record 預(yù)處理數(shù)據(jù)類型st,ed:char; 起始、結(jié)束字符md:0.1; 重復(fù)方式0： 一次；1： 0或多次mt:0.1; 匹配方式0：不包含為匹配；1：包含為匹配end;varf1,f2:text; 文件變量s1,s2:string; 正則表達(dá)式串、待匹配串str:string;len:integer

47、; 正則表達(dá)式預(yù)處理后的“長度”dd:array 1.80 of datatype; 預(yù)處理結(jié)果pro:array 0.80,0.80 of boolean; 動(dòng)態(tài)規(guī)劃數(shù)組fr:array 0.80,0.80 of byte;FRi,j表示以第j個(gè)字符為尾的與前i項(xiàng)正則表達(dá)式匹配的最前端的字符位置i,j,k,l:integer; 輔助變量ok:boolean; 找到標(biāo)記ha:boolean;ans:integer;bt,bj:integer; 當(dāng)前最優(yōu)值的開始位置、長度procedure preprocess; 預(yù)處理，生成規(guī)劃的“正則表達(dá)式”表示 vari,j,k:integer;ch,c:

48、char;begini:=0;j:=0;while ifri-1,k) then fri,j:=fri-1,k;如果起點(diǎn)較早，更新之end;if not (ddi.mt=0) xor (s2k in ddi.st.ddi,ed)如果不匹配，則不考慮再退一格的情況then begin ha:=false; break end;end;end;if (i=len) and proi,j and (fri,j=bt) then如果發(fā)現(xiàn)更好的，更新當(dāng)前最優(yōu)值beginok:=true;bt:=fri,j;bj:=j-bt+1;end;end;if ok thenif bj0 then writeln(

49、f2,copy(s2,1,bt-1), (, copy(s2,bt,bj), ), copy(s2,bt+bj,length(s2)-bt-bj+1) 如果找到，輸 出else writeln(f2,(),s2)對(duì)于某些理論上講可以與空串匹配的正則表達(dá)式，應(yīng)看作與第一個(gè)字符前的空串匹配，這里作了專門 處理else writeln(f2,s2); 否則輸出原串end;close(f1);close(f2)end.程序5 NOI98免費(fèi)餡餅說明：動(dòng)態(tài)規(guī)劃方程： anst,j= max ( anst-1,j+k)(其中，k=-2,-1,0,1,2，且相應(yīng)位置可達(dá))program Pizza_For_

50、Free Time Limit:3000;免費(fèi)餡餅 將允許時(shí)間擴(kuò)大到3000秒，分值限制在longint范圍內(nèi)typelink=Alinetype; 指向記錄一個(gè)時(shí)間單位決策數(shù)組的指針類型linetype=array 1.99 of shortint; 記錄一個(gè)時(shí)間單位決策的數(shù)組varf1,f2:text; 輸入、輸出文件變量w,h:integer; 寬度、高度dd:array 0.100 of array 1.99 of longint; 循環(huán)使用的數(shù)組，用于表示對(duì)應(yīng)時(shí)刻、位置的得分值pro:array 0.3100 of link; 記錄決策信息的動(dòng)態(tài)數(shù)組dt:array 0.1,1.99

51、 of longint; 循環(huán)使用的動(dòng)態(tài)規(guī)劃數(shù)組i,j,k,t:integer; 輔助變量bt,bj:integer; 最大狀態(tài)記錄best:longint; 最大值記錄maxt:integer; 最大時(shí)間ans:array 1.3100 of shortint; 倒推答案時(shí)用的暫存區(qū)num:integer;pp:longint;_t,_j,_v:integer; 暫存初始時(shí)間、位置、速度_fz:longint; 暫存分值_saved:boolean; 是否暫存標(biāo)志procedure try_reading; 讀入原始數(shù)據(jù)的過程，其中使用了分段讀取的方法。讀入初始下落時(shí)間不大于t 的餡餅var

52、t0,i,j,v:integer; 初始下落時(shí)間fz:longint; 分值beginfillchar(dd(t+100) mod 101,sizeof(dd(t+100) mod 101),0);t及以后時(shí)間讀入的塊，至遲在t+99時(shí)間即進(jìn)入可接收狀態(tài)，可對(duì)t+100(循環(huán)觀點(diǎn)下)單元清0,以便 下次使用if _saved then 如果上次有預(yù)存beginif _tt then exit; 如果預(yù)存結(jié)果仍不被使用到，則返回，否則用預(yù)存結(jié)果記錄新餡餅_saved:=false;if (h-1) mod _v=0 thenbegininc(dd(_t+(h-1) div _v) mod 101

53、,_j,_fz);if (_t+(h-1) div _v)maxt then maxt:=_t+(h-1) div _v;end;end;if eof(f1) then exit; 文件結(jié)束就返回while true do 不斷讀取，直到初始下落時(shí)間大于當(dāng)前處理時(shí)間beginif eof(f1) then exit;readln(f1,t0,j,v,fz);if t0t thenbegin_v:=v;_t:=t0;_j:=j;_fz:=fz;_saved:=true;exit 暫存返回end;if (h-1) mod v0 then continue; 標(biāo)記時(shí)間-位置與得到的分值inc(dd(

54、t0+(h-1) div v) mod 101,j,fz);if t0+(h-1) div vmaxt then maxt:=t0+(h-1) div v;end;end;begin 主程序assign(f1,INPUT.TXT);reset(f1);assign(f2,OUTPUT.TXT);rewrite(f2); 文件關(guān)聯(lián)、打開readln(f1,w,h); 讀入寬、高for i:=0 to 3100 do 動(dòng)態(tài)內(nèi)存初始化beginnew(proi);fillchar(proiA,sizeof(proiA),0);end;for i:=0 to 1 dofor j:=1 to 99 do

55、dti,j:=-maxlongint-1;賦初值dt0,(1+w) div 2:=0; -maxlongint-1 表示該點(diǎn)不可達(dá)fillchar(dd,sizeof(dd),0);t:=0;maxt:=0;_saved:=false;try_reading;best:=0;bt:=0;bj:=(w+1) div 2;best:=dd0,(w+1) div 2;while true dobegininc(t); 考慮下一個(gè)時(shí)間try_reading; 讀入數(shù)據(jù)if eof(f1) and (tmaxt) and not _saved then break; 如果沒有新的數(shù)據(jù)，跳出 for j:

56、=1 to w do 考慮各個(gè)位置begindtt mod 2,j:=-maxlongint-1;for k:=-2 to 2 do 考慮5種移動(dòng)方式if (j+k0) and (j+k-maxlongint-1) 如果可能and (dt1-t mod 2,j+k+ddt mod 101,jdtt mod 2,j) then 而且有效 begindtt mod 2,j:=dt1-t mod 2,j+k+ddt mod 101,j; 更新當(dāng)前最優(yōu)值 protAj：=k;end;if dtt mod 2,jbest then 如果到目前最優(yōu)，更新之beginbest:=dtt mod 2,j;bt

57、:=t;bj:=j;end;end;end;writeln(f2,best); 輸出最大值num:=0;j:=bj;for t:=bt downto 1 do 倒推求解beginanst:=-protAj;inc(j,prot氣);end;for t:=1 to bt dowriteln(f2,anst);close(fl);close(f2)end.論文附錄：本文所引題目詳細(xì)內(nèi)容1、字符識(shí)別(IOI97)Character RecognitionThis problem requires you to write a program that performs character recog

58、nition.Details:Each ideal character image has 20 lines of 20 digits. Each digit is a 0 or a 1. See Figure 1a for the layout of character images in the file.The file FONT.DAT contains representations of 27 ideal character images in this order:?abcdefghijklmnopqrstuvwxyzwhere ? represents the space ch

59、aracter.The file IMAGE.DAT contains one or more potentially corrupted character images. A character image might be corrupted in these ways:? at most one line might be duplicated (and the duplicate immediately follows)? at most one line might be missing? some 0 might be changed to 1? some 1 might be

60、changed to 0.No character image will have both a duplicated line and a missing line. No more than 30% of the 0 and 1 will be changed in any character image in the evaluation datasets.In the case of a duplicated line, one or both of the resulting lines may have corruptions, and the corruptions may be