動態(tài)規(guī)劃程序設計

1、動態(tài)規(guī)劃程序設計青島二中04級李辰動態(tài)規(guī)劃是信息學競賽中的一種利用擴大空間占用而縮短時間消耗的設計方法。現今的幾乎所有程序設計競賽中，隨著空間的限制逐漸減小，時間已經成為極重要的衡量程序優(yōu)劣的標準。因此，動態(tài)規(guī)劃以其靈活性和高效性逐漸為大家的所喜愛。但是由于其概念比較抽象，對剛接觸的人來講理解起來并不容易。本文將結合例題，系統(tǒng)細致地解釋動態(tài)規(guī)劃，同時介紹一些在使用動態(tài)規(guī)劃過程中常運用到的技巧。相信所有程序設計者對搜索算法很熟悉， 而在搜索能解決的題目中，有很大一部分題能利用動態(tài)規(guī)劃解決， 而其效率是搜索所無法比擬的。這類題目的一大特點是在用搜索解決的過程中，不斷重復了一項已經進行過的工作。 動

2、態(tài)規(guī)劃之所以能極大地提高解題效率，是因為它儲存下了這些已經進行過得工作的結果，下次使用時只需將結果調出。 這也是為什么現在很多人把動態(tài)規(guī)劃叫做：記憶化搜索。下面這道題就是一個從搜索轉到記憶化搜索動態(tài)規(guī)劃的很好例子。一個數字三角形 ,形式如下 :12 34 5 678910找出從第一層到最后一層的一條路, 使得所經過的權值之和最大 . 從每層到下面一層只能向左下或右下走。讓我們來模擬一下深度優(yōu)先搜索的過程（走法選擇先選左下，后選右下， <表示無法深入搜索，回溯） ：1247<8<<58<9<<<358<9<<69<10<

3、; < < < 不計回溯總共需要 15 步（因為每層到下一層都有且只有 2 種選擇，所以理論上三角形有n 層就需要 2 的 n 次方 -1 步）仔細觀察不難發(fā)現， 想到達每層中除了最左邊和最右邊的數字都只有兩種選擇（左上或右上）。達任意數字時的最大值是該數字 +到達左上或右上數字時的最大值中的較大值。這樣寫比較難懂，讓我們用數學語言解釋。不妨設va ， b 表示第 a 行第 b 列的數字。fa ，b 表示從頂端到第a 行第 b 列的數字得到的最大值。max(a， b) 表示 a，b 中較大的那一個。則 fa，b=max（ fa-1 ， b-1 ，fa-1，b ）+va ， b

4、這樣就抽象出了動態(tài)規(guī)劃狀態(tài)轉移方程，我們只需要找出實現動態(tài)方程的循環(huán)方法， 該循環(huán)方法要保證在計算到當前所求值時方程右邊的元素已經全部算出。即在計算到fa，b時保證已經計算出了fa-1， b-1和fa-1，b（ va， b為已知值）此題的循環(huán)方法較簡單，設i 表示第i 行， j表示第j列雙重循環(huán)即可實現。For i:=2 to n doFor j:=1 to i do（第i行有i個數字）fi，j=max（fi-1，j-1， fi-1， j）+vi， j（在三角形兩邊需要簡單地特殊處理一下，例如把fi,0和fi,i+1均賦值為0 等很多方法都可以）若三角形有 n 層則此算法的理論計算量為理論效率

5、N=10N=100n 的平方。N=1000搜索2 的n 次方1024次約10 的31約 10的300次方次次方動態(tài)規(guī)劃N的平方100 次10000 次10 的 6 次方按一臺計算機每秒運算1 億次來看，即使 n=10000 用動態(tài)規(guī)劃也可在 1 秒鐘左右出結果。 而搜索的時間代價已經大得無法接受。相信通過上面的例子大家已經對動態(tài)規(guī)劃有了一定認識。但動態(tài)規(guī)劃的思想絕不僅僅是“記憶化搜索”這幾個字能概括的，動態(tài)規(guī)劃還有一個重要的特點是它的目標狀態(tài)是由前面一個狀態(tài)得到的， 而前面一個狀態(tài)又由再前面一個狀態(tài)得到， 有點類似遞推或遞歸， 但又不像遞推和遞歸那樣一步步按部就班， 目的明確。動態(tài)規(guī)劃方程運算

6、結束后， 我們會發(fā)現除了從初始狀態(tài)到目標狀態(tài)的各個狀態(tài)外，我們還對許多其他“多余”的狀態(tài)進行了處理，但在動態(tài)規(guī)劃方程運算結束之前我們并不知道哪些狀態(tài)無法達到目標狀態(tài)，因此無從取舍。拿上面的題舉例子，我們不但找到了到達 10 的最大權值和走法，我們還找到了到達任何一個頂點的最大權值和走法， 這雖然看上去是一種浪費， 但其實我們不得不做，因為在結果得出前我們不知道哪個狀態(tài)是真正必要的，所以所有狀態(tài)都要計算出。 并且往往前一個狀態(tài)都是此時的局部的最優(yōu)解， 后一個狀態(tài)則是由這個局部最優(yōu)解得到的大一點的局部的最優(yōu)解，直到得出目標狀態(tài)，即全局最優(yōu)解。因此可以說動態(tài)規(guī)劃具有最優(yōu)子結構特性。讓我們再看看另一道

7、經典題目。有一個容積為 n 的袋子，又知道 m個貨物各自的體積和價值，要求你將貨物裝到袋子里，使袋子中的貨物價值和最大。假如袋子的容積為10，現有貨物貨物名ABCDE體積44323價值56423很顯然，最優(yōu)解為裝 B,C,E ，價值為 13。這個例子也說明并不是不斷將價值最大的貨物放進袋子就能得到最優(yōu)解。其他與之相似的各類貪心法均可證明是錯誤的。我們的目的是要 “記憶化搜索” 出 x 個貨物，使它們的體積和小于 n，價值和盡可能大。與上一道題目相類似，如果在放入一些貨物后， 再放入一個貨物后能得到最優(yōu)解，那么在放入這個貨物前，所有貨物無論怎么搭配，也不可能出現體積和小于或等于此時袋中物品體積和

8、而價值和大于此時袋中貨物的價值和的情況。即無論貨物怎么搭配裝進袋子，比此時的價值和大，比此時的體積和小這兩種情況不可能同時滿足， 這就可以稱作是最優(yōu)子結構了。由此得出狀態(tài)轉移方程:設 fi,x表示前 i 個貨物，用體積等于x 時的袋子裝能得到的最大價值（最優(yōu)子結構的體現），wi 表示第 i 個貨物的體積， vi表示第 i 個貨物的價值。fi，j=max(fi-1，j-wi+vi, fi-1,j)（i表示當前搜索到第i個貨物，j表示袋中體積和等于j時的情況,fi-1,j-wi+vi表示放i貨物時的最大價值，fi-1,j表示不放 i 貨物時的最大價值）由于 j 的循環(huán)是建立在已經確定i 的基礎上，

9、因此 j 的循環(huán)在 i 循環(huán)的內部。因此具體實現方法為： for i ： =1 to n dofor j:=1 to m do beginfi,j:=fi-1,j;if (j>=wi) thenif (fi-1,j-wi+vi>fi,j) thenfi,j:=fi-1,j-wi+vi;end;這里還有些細節(jié)要處理，比如要預先將f 數組清零等等 .寫到這里我想向大家介紹一種減少空間使用的辦法， 若用二維數組表示狀態(tài)（即狀態(tài)表示為 fi,j 的形式），則我們不妨稱 fi 為一個狀態(tài)層， 每個層中含有若干個狀態(tài)。 細心觀察不難發(fā)現，這道貨物裝袋題與上面一道數字三角形的程序實現中， 要推得

10、下面一個狀態(tài)層只需要當前這個狀態(tài)層而不需要當前狀態(tài)層之前層的狀態(tài)，即要推得 fi ，只需要 fi-1 。這樣說來求出最優(yōu)解我們只需要兩個線性數組， 一個記錄前面的狀態(tài)層另一個記錄后面的狀態(tài)層。以貨物裝袋為例，再來看一道全國信息學奧林匹克原題：某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。 但是這種導彈攔截系統(tǒng)有一個缺陷： 雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以 只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。 輸入導彈依次飛來的高度， 計算這套系統(tǒng)最多能攔截多少導彈。設 hi表示第 i 個導

11、彈的高度，再通過預處理得到導彈數n按先前的思路進行分析，假設fi表示到第i 個導彈時所能擊中的最大導彈數，但是發(fā)現接下來沒法寫出狀態(tài)轉移方程，因為在求fi時還有一個條件是要考慮現在要打的導彈高度不能超過最近打下的一個導彈的高度。所以顯然我們的狀態(tài)轉移方程中要考慮到這一點。因此我們再次假設fi表示在打下第i 個導彈的前提下所能打下的導彈數最大值。因為我們將打下第i 個導彈列為前提，因此也就確定了fi這個狀態(tài)打的下一個導彈高度只需要<=hi。而且打下第i 個導彈數最大的情況一定是打下前面某個導彈最大數情況 , 再打下第i 個導彈，或者該系統(tǒng)打下的第一個導彈就是 i （最優(yōu)子結構明顯的體現）

12、。將 f 數組的所有元素賦值為 1，就是說當以該導彈為第一個打下的導彈時打下了 1 個導彈。For i:=2 to n doFor j:=1 to i-1 doif (hi<=hj) thenfi:=max(fi,fj+1)最后要線性掃描一下f 數組，找到其中的最大值。 （不能簡單的將fn定為答案，因為最優(yōu)解的情況未必會打下最后一顆導彈）讓我們再來看看這道較上面幾道相對另類的題。最長公共子串：已知兩個字符串， 要求求出它們最長的公共子串的長度（子串中的每個字符都能在兩個原串中找到，而且每個字符的順序和原串中的順序一致，子串可不連續(xù)） 。例如： abbbdcdcd 和 abcdaabd的最

13、長公共子串是abcdd, 其長度為 5。這道題看上去很棘手， 怎么做？最直接的方法，從長到短枚舉其中一個字符串的所有子串，在另一個字符串中一一比對，直到在另一個字符串中找到一個和枚舉的子串相符的子串，那么這個子串的長度即為所求答案。假設兩個字符串長度均為 n，枚舉子串時間復雜度為 2 的 n 次方，在另一個字符串中比對是否有相符子串的復雜度為 n*n, 所以理論復雜度為 n*n* （2 的 n 次方），用這種方法只能保證當 n 小于 20 時在 1 秒內出結果。很明顯這不是我們想要的效率。讓我們來觀察一下這道題能否用動態(tài)規(guī)劃解決， 試著利用最優(yōu)子結構的思想分析后得到：設兩個子串分別為串 1 和

14、串 2，若串 1 和串 2 末尾字母相同則所求解即串 1 和串 2 分別去掉末尾字母后的最長公共子串長度 +1，否則所求解即串 1 去掉末尾字母后和串 2 的最長公共子串長度或串 2 去掉末尾字母后和串 1 的最長公共子串長度中較大的一個。 因為去掉末尾字母的字符串又可以看成一個新字符串， 這樣就具有了最優(yōu)子結構， 但是因為遞歸的思想在程序中實現起來編寫難度和時間復雜度都比遞推大，而且這道題遞推的狀態(tài)轉移方法也比較簡單，因此我們就用遞推來實現。用數學語言表示一下， 不妨設，a1,a2 分別表示 2 個字符串，fi,j表示 a1 字符串前 i 個字符與 a2 字符串前 j 個字符的最長公共子串長

15、度，l1,l2分別表示a1,a2字符串的長度。動歸的實現方法：For i:=1 to l1 doFor j:=1 to l2 doIf a1i=a2j then fi,j:=fi-1,j-1+1;Else fi,j:=max(fi-1,j,fi,j-1)這樣時間復雜度n*n的程序可以接受2 個長度為10000 的字符串，幾乎不需要預處理（fi,j中i,j的下界應為 0，數組清零）編寫起來也明顯比搜索簡單得多， 看來動態(tài)規(guī)劃確實是程序設計者一項利器。讓我們最后看看一道題， Tom的煩惱，希望在看完上面文字后，讀者能嘗試著自主完成此題。Tom是一個非常有創(chuàng)業(yè)精神的人，由于大學學的是汽車制造專業(yè)，所

16、以畢業(yè)后他用有限的資金開了一家汽車零件加工廠，專門為汽車制造商制造零件。由于資金有限，他只能先購買一臺加工機器。 現在他卻遇到了麻煩，多家汽車制造商需要他加工一些不同零件（由于廠家和零件不同，所以給的加工費也不同），而且不同廠家對于不同零件的加工時間要求不同（有些加工時間要求甚至是沖突的， 但開始和結束時間相同不算沖突）。Tom當然希望能把所有的零件都加工完，以得到更多的加工費，但當一些零件的加工時間要求有沖突時，在某個時間內他只能選擇某種零件加工（因為他只有一臺機器），為了賺得盡量多的加工費，Tom不知如何進行取舍。設有 n 個廠家，每個廠家要求的起始時間si,結束時間ei，加工費 vi。讀者已經有思路了嗎？讓我們看看分析。做這道題，切入點就在于找出最優(yōu)子結構。先將廠家的任務以結束時間從小到大排序。設fx為到達第x 時間時能獲得的最大利潤 ,i 為第 i 個廠家的任務。因為已經將任務以結束時間排列，而且每個