動態(tài)規(guī)劃案例分析.ppt

1、2020/8/30,1,動態(tài)規(guī)劃 案例分析,數(shù)字三角形,1、問題描述,上圖給出了一個數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個和，和最大的路徑稱為最佳路徑。你的任務(wù)就是求出最佳路徑上的數(shù)字之和。 注意：路徑上的每一步只能從一個數(shù)走到下一層上和它最近的左邊的數(shù)或者右邊的數(shù)。,問題描述,輸入數(shù)據(jù) 輸入的第一行是一個整數(shù)N (1 N = 100)，給出三角形的行數(shù)。下面的N 行給出數(shù)字三角形。數(shù)字三角形上的數(shù)的范圍都在0 和100 之間。 輸出要求 輸出最大的和。,問題描述,輸入樣例 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6

2、5 輸出樣例 30,2、解題思路,這道題目可以用遞歸的方法解決?；舅悸肥牵?以D( r, j)表示第r 行第 j 個數(shù)字(r，j 都從1 開始算)，以MaxSum(r, j) 代表從第 r 行的第 j 個數(shù)字到底邊的最佳路徑的數(shù)字之和，則本題是要求 MaxSum(1, 1) 。 從某個D(r, j)出發(fā)，顯然下一步只能走D(r+1, j)或者D(r+1, j+1)。如果走D(r+1, j)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j) + D(r, j)；如果走D(r+1, j+1)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j+1) + D(r,

3、j)。所以，選擇往哪里走，就看MaxSum(r+1, j)和MaxSum(r+1, j+1)哪個更大了。,3、參考程序 I,#include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int MaxSum( int r, int j) if( r = N ) return Drj; int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 nSum2 ) return nSum1+Drj; return nSum2+Drj; ,3、參考程序 I

4、,int main(void) int m; scanf(%d, ,程序I分析,上面的程序，效率非常低，在N 值并不大，比如N=100 的時候，就慢得幾乎永遠算不出結(jié)果了。 為什么？是因為過多的重復(fù)計算。 我們不妨將對MaxSum 函數(shù)的一次調(diào)用稱為一次計算。那么，每次計算MaxSum(r, j)的時候，都要計算一次MaxSum(r+1, j+1)，而每次計算MaxSum(r, j+1)的時候，也要計算一次MaxSum(r+1, j+1)。重復(fù)計算因此產(chǎn)生。 在題目中給出的例子里，如果我們將MaxSum(r, j)被計算的次數(shù)都寫在位置（r, j），那么就能得到右面的三角形：,1 1 1 1

5、2 1 1 3 3 1 1 4 6 4 1,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,程序分析,從上圖可以看出，最后一行的計算次數(shù)總和是16，倒數(shù)第二行的計算次數(shù)總和是8。不難總結(jié)出規(guī)律，對于N 行的三角形，總的計算次數(shù)是20 +21+22+2(N-1)=2N-1。當N= 100 時，總的計算次數(shù)是一個讓人無法接受的大數(shù)字。 既然問題出在重復(fù)計算，那么解決的辦法，當然就是，一個值一旦算出來，就要記住，以后不必重新計算。即第一次算出MaxSum(r, j)的值時，就將該值存放起來，下次再需要計算MaxSum(r, j)時，直接取用存好的值即可，不必再次調(diào)用MaxSum 進行函數(shù)

6、遞歸計算了。這樣，每個MaxSum(r, j)都只需要計算1 次即可，那么總的計算次數(shù)（即調(diào)用MaxSum 函數(shù)的次數(shù)）就是三角形中的數(shù)字總數(shù)，即1+2+3+N = N(N+1)/2。 如何存放計算出來的MaxSum（r, j）值呢？顯然，用一個二維數(shù)組aMaxSumNN就能解決。aMaxSumrj就存放MaxSum(r, j)的計算結(jié)果。下次再需要MaxSum(r, j)的值時，不必再調(diào)用MaxSum 函數(shù)，只需直接取aMaxSumrj的值即可。,4、參考程序 II,#include #include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM

7、+ 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int MaxSum( int r, int j) if( r = N ) return Drj; if( aMaxSumr+1j = -1 ) /如果MaxSum(r+1, j)沒有計算過 aMaxSumr+1j = MaxSum(r+1, j); if( aMaxSumr+1j+1 = -1) aMaxSumr+1j+1 = MaxSum(r+1, j+1); if( aMaxSumr+1j aMaxSumr+1j+1 ) return aMaxSumr+1j +Drj; return aM

8、axSumr+1j+1 + Drj; ,4、參考程序 II,int main(void) int m; scanf(%d, ,程序II分析,這種將一個問題分解為子問題遞歸求解，并且將中間結(jié)果保存以避免重復(fù)計算的辦法，就叫做“動態(tài)規(guī)劃”。動態(tài)規(guī)劃通常用來求最優(yōu)解，能用動態(tài)規(guī)劃解決的求最優(yōu)解問題，必須滿足，最優(yōu)解的每個局部解也都是最優(yōu)的。以上題為例，最佳路徑上面的每個數(shù)字到底部的那一段路徑，都是從該數(shù)字出發(fā)到達到底部的最佳路徑。 實際上，遞歸的思想在編程時未必要實現(xiàn)為遞歸函數(shù)。在上面的例子里，有遞推公式：,因此，不需要寫遞歸函數(shù)，從aMaxSumN-1這一行元素開始向上逐行遞推，就能求得aMaxS

9、um11的值了。,5、參考程序 III,int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int main(void) int i, j; scanf(%d, ,思考題：上面的幾個程序只算出了最佳路徑的數(shù)字之和。如果要求輸出最佳路徑上的每個數(shù)字，該怎么辦？,動態(tài)規(guī)劃解題的一般思路,許多求最優(yōu)解的問題可以用動態(tài)規(guī)劃來解決。 首先要把原問題分解為若干個子問題。注意單純的遞歸往往會導(dǎo)致子問題被重復(fù)計算，用動態(tài)規(guī)劃的方法，子問題的解一旦求出就要被保存，所以每個子問題只需求解一次。 子問題經(jīng)常和原問題形式

10、相似，有時甚至完全一樣，只不過規(guī)模從原來的n 變成了n-1，或從原來的nm 變成了n(m-1) 等等。 找到子問題，就意味著找到了將整個問題逐漸分解的辦法。 分解下去，直到最底層規(guī)模最小的的子問題可以一目了然地看出解。 每一層子問題的解決，會導(dǎo)致上一層子問題的解決，逐層向上，就會導(dǎo)致最終整個問題的解決。 如果從最底層的子問題開始，自底向上地推導(dǎo)出一個個子問題的解，那么編程的時候就不需要寫遞歸函數(shù)。,動態(tài)規(guī)劃解題的一般思路,用動態(tài)規(guī)劃解題時，將和子問題相關(guān)的各個變量的一組取值，稱之為一個“狀態(tài)”。一個“狀態(tài)”對應(yīng)于一個或多個子問題，所謂某個“狀態(tài)”下的“值”，就是這個“狀態(tài)”所對應(yīng)的子問題的解。

11、 比如數(shù)字三角形，子問題就是“從位于(r，j)數(shù)字開始，到底邊路徑的最大和”。這個子問題和兩個變量r 和j 相關(guān)，那么一個“狀態(tài)”，就是r, j 的一組取值，即每個數(shù)字的位置就是一個“狀態(tài)”。該“狀態(tài)”所對應(yīng)的“值”，就是從該位置的數(shù)字開始，到底邊的最佳路徑上的數(shù)字之和。 定義出什么是“狀態(tài)”，以及在該 “狀態(tài)”下的“值”后，就要找出不同的狀態(tài)之間如何遷移即如何從一個或多個“值”已知的 “狀態(tài)”，求出另一個“狀態(tài)”的“值”。狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)轉(zhuǎn)移方程”。,動態(tài)規(guī)劃解題的一般思路,用動態(tài)規(guī)劃解題，如何尋找“子問題”，定義“狀態(tài)”，“狀態(tài)轉(zhuǎn)移方程”是什么樣的，

12、并沒有一定之規(guī)，需要具體問題具體分析，題目做多了就會有感覺。 甚至，對于同一個問題，分解成子問題的辦法可能不止一種，因而“狀態(tài)”也可以有不同的定義方法。不同的“狀態(tài)”定義方法可能會導(dǎo)致時間、空間效率上的區(qū)別。,最長上升子序列,1、問題描述,一個數(shù)的序列bi，當b1 b2 . bS 的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2, ., aN)，我們可以得到一些上升的子序列(ai1, ai2, ., aiK)，這里1 = i1 i2 . iK = N。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子

13、序列中最長的長度是4，比如子序列(1, 3, 5, 8). 你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度。,問題描述,輸入數(shù)據(jù) 輸入的第一行是序列的長度N (1 = N = 1000)。第二行給出序列中的N 個整數(shù)，這些整數(shù)的取值范圍都在0 到10000。 輸出要求 最長上升子序列的長度。 輸入樣例 7 1 7 3 5 9 4 8 輸出樣例 4,2、解題思路,如何把這個問題分解成子問題呢？經(jīng)過分析，發(fā)現(xiàn) “求以ak（k=1, 2, 3N）為終點的最長上升子序列的長度”是個好的子問題這里把一個上升子序列中最右邊的那個數(shù)，稱為該子序列的“終點”。雖然這個子問題和原問題形式上并不完全一樣，

14、但是只要這N 個子問題都解決了，那么這N 個子問題的解中，最大的那個就是整個問題的解。 由上所述的子問題只和一個變量相關(guān)，就是數(shù)字的位置。因此序列中數(shù)的位置k 就是“狀態(tài)”，而狀態(tài) k 對應(yīng)的“值”，就是以ak 做為“終點”的最長上升子序列的長度。這個問題的狀態(tài)一共有N 個。狀態(tài)定義出來后，轉(zhuǎn)移方程就不難想了。,2、解題思路,假定MaxLen (k)表示以ak 做為“終點”的最長上升子序列的長度，那么： MaxLen (1) = 1 MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak 且 k1 + 1 這個狀態(tài)轉(zhuǎn)移方程的意思就是，MaxLen(k)的值，就是在ak

15、 左邊，“終點”數(shù)值小于ak，且長度最大的那個上升子序列的長度再加1。因為ak 左邊任何“終點”小于ak 的子序列，加上ak 后就能形成一個更長的上升子序列。 實際實現(xiàn)的時候，可以不必編寫遞歸函數(shù)，因為從 MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3),3、參考程序,int bMAX_N + 10; int aMaxLenMAX_N + 10; int main(void) int i, j, N; scanf(%d, ,3、參考程序,for( i = 2; i bj ) if( nTmp aMaxLenj ) nTmp

16、= aMaxLenj; aMaxLeni = nTmp + 1; int nMax = -1; for( i = 1;i = N;i + ) if( nMax aMaxLeni) nMax = aMaxLeni; printf(%dn, nMax); return 0; ,思考題：改進此程序，使之能夠輸出最長上升子序列,最長公共子序列,1、問題描述,我們稱序列Z = 是序列X = 的子序列當且僅當存在嚴格上升的序列，使得對j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。 現(xiàn)在給出兩個序列X 和Y，你的任務(wù)是找到X 和Y 的最大公共子序列，也就是說要找到一個最

17、長的序列Z，使得Z 既是X 的子序列也是Y 的子序列。 輸入數(shù)據(jù) 輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個長度不超過200 的字符串，表示兩個序列。兩個字符串之間由若干個空格隔開。,問題描述,輸出要求 對每組輸入數(shù)據(jù)，輸出一行，給出兩個序列的最大公共子序列的長度。 輸入樣例 abcfbc abfcab programming contest abcd mnp 輸出樣例 4 2 0,2、解題思路,用字符數(shù)組s1、s2存放兩個字符串，用s1i表示s1中的第i 個字符，s2j表示s2中的第j個字符（字符編號從1 開始），用s1i表示s1的前i個字符所構(gòu)成的子串，s2j表示s2的前j個字符構(gòu)成

18、的子串，MaxLen(i,j)表示s1i 和s2j 的最長公共子序列的長度，那么遞推關(guān)系如下： if( i =0 | j = 0 ) MaxLen(i, j) = 0 /兩個空串的最長公共子序列長度是0 else if( s1i = s2j ) MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1; else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);,2、解題思路,顯然本題目的“狀態(tài)”就是s1 中的位置i 和s2 中的位置j。 “值”就是MaxLen(i, j)。 狀態(tài)的數(shù)目是s1 長度和s2 長度的乘積?？梢杂靡粋€

19、二維數(shù)組來存儲各個狀態(tài)下的“值”。 本問題的兩個子問題，和原問題形式完全一致的，只不過規(guī)模小了一點。,3、參考程序,#include #include #define MAX_LEN 1000 char sz1MAX_LEN; char sz2MAX_LEN; int aMaxLenMAX_LENMAX_LEN; int main(void) while( scanf(%s%s, sz1+1 ,sz2+1 ) 0 ) int nLength1 = strlen( sz1+1); int nLength2 = strlen( sz2+1); int i, j; for( i = 0;i = nLength1; i + )