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

2、5 輸出樣例 30,2、解題思路,這道題目可以用遞歸的方法解決。基本思路是： 以D( r, j)表示第r 行第 j 個(gè)數(shù)字(r，j 都從1 開(kāi)始算)，以MaxSum(r, j) 代表從第 r 行的第 j 個(gè)數(shù)字到底邊的最佳路徑的數(shù)字之和，則本題是要求 MaxSum(1, 1) 。 從某個(gè)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)哪個(gè)更大了。,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 的時(shí)候，就慢得幾乎永遠(yuǎn)算不出結(jié)果了。 為什么？是因?yàn)檫^(guò)多的重復(fù)計(jì)算。 我們不妨將對(duì)MaxSum 函數(shù)的一次調(diào)用稱為一次計(jì)算。那么，每次計(jì)算MaxSum(r, j)的時(shí)候，都要計(jì)算一次MaxSum(r+1, j+1)，而每次計(jì)算MaxSum(r, j+1)的時(shí)候，也要計(jì)算一次MaxSum(r+1, j+1)。重復(fù)計(jì)算因此產(chǎn)生。 在題目中給出的例子里，如果我們將MaxSum(r, j)被計(jì)算的次數(shù)都寫(xiě)在位置（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,程序分析,從上圖可以看出，最后一行的計(jì)算次數(shù)總和是16，倒數(shù)第二行的計(jì)算次數(shù)總和是8。不難總結(jié)出規(guī)律，對(duì)于N 行的三角形，總的計(jì)算次數(shù)是20 +21+22+2(N-1)=2N-1。當(dāng)N= 100 時(shí)，總的計(jì)算次數(shù)是一個(gè)讓人無(wú)法接受的大數(shù)字。 既然問(wèn)題出在重復(fù)計(jì)算，那么解決的辦法，當(dāng)然就是，一個(gè)值一旦算出來(lái)，就要記住，以后不必重新計(jì)算。即第一次算出MaxSum(r, j)的值時(shí)，就將該值存放起來(lái)，下次再需要計(jì)算MaxSum(r, j)時(shí)，直接取用存好的值即可，不必再次調(diào)用MaxSum 進(jìn)行函數(shù)

6、遞歸計(jì)算了。這樣，每個(gè)MaxSum(r, j)都只需要計(jì)算1 次即可，那么總的計(jì)算次數(shù)（即調(diào)用MaxSum 函數(shù)的次數(shù)）就是三角形中的數(shù)字總數(shù)，即1+2+3+N = N(N+1)/2。 如何存放計(jì)算出來(lái)的MaxSum（r, j）值呢？顯然，用一個(gè)二維數(shù)組aMaxSumNN就能解決。aMaxSumrj就存放MaxSum(r, j)的計(jì)算結(jié)果。下次再需要MaxSum(r, j)的值時(shí)，不必再調(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)沒(méi)有計(jì)算過(guò) 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分析,這種將一個(gè)問(wèn)題分解為子問(wèn)題遞歸求解，并且將中間結(jié)果保存以避免重復(fù)計(jì)算的辦法，就叫做“動(dòng)態(tài)規(guī)劃”。動(dòng)態(tài)規(guī)劃通常用來(lái)求最優(yōu)解，能用動(dòng)態(tài)規(guī)劃解決的求最優(yōu)解問(wèn)題，必須滿足，最優(yōu)解的每個(gè)局部解也都是最優(yōu)的。以上題為例，最佳路徑上面的每個(gè)數(shù)字到底部的那一段路徑，都是從該數(shù)字出發(fā)到達(dá)到底部的最佳路徑。 實(shí)際上，遞歸的思想在編程時(shí)未必要實(shí)現(xiàn)為遞歸函數(shù)。在上面的例子里，有遞推公式：,因此，不需要寫(xiě)遞歸函數(shù)，從aMaxSumN-1這一行元素開(kāi)始向上逐行遞推，就能求得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, ,思考題：上面的幾個(gè)程序只算出了最佳路徑的數(shù)字之和。如果要求輸出最佳路徑上的每個(gè)數(shù)字，該怎么辦？,動(dòng)態(tài)規(guī)劃解題的一般思路,許多求最優(yōu)解的問(wèn)題可以用動(dòng)態(tài)規(guī)劃來(lái)解決。 首先要把原問(wèn)題分解為若干個(gè)子問(wèn)題。注意單純的遞歸往往會(huì)導(dǎo)致子問(wèn)題被重復(fù)計(jì)算，用動(dòng)態(tài)規(guī)劃的方法，子問(wèn)題的解一旦求出就要被保存，所以每個(gè)子問(wèn)題只需求解一次。 子問(wèn)題經(jīng)常和原問(wèn)題形式

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

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

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

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

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

15、 左邊，“終點(diǎn)”數(shù)值小于ak，且長(zhǎng)度最大的那個(gè)上升子序列的長(zhǎng)度再加1。因?yàn)閍k 左邊任何“終點(diǎn)”小于ak 的子序列，加上ak 后就能形成一個(gè)更長(zhǎng)的上升子序列。 實(shí)際實(shí)現(xiàn)的時(shí)候，可以不必編寫(xiě)遞歸函數(shù)，因?yàn)閺?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; ,思考題：改進(jìn)此程序，使之能夠輸出最長(zhǎng)上升子序列,最長(zhǎng)公共子序列,1、問(wèn)題描述,我們稱序列Z = 是序列X = 的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列，使得對(duì)j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。 現(xiàn)在給出兩個(gè)序列X 和Y，你的任務(wù)是找到X 和Y 的最大公共子序列，也就是說(shuō)要找到一個(gè)最

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

18、的子串，MaxLen(i,j)表示s1i 和s2j 的最長(zhǎng)公共子序列的長(zhǎng)度，那么遞推關(guān)系如下： if( i =0 | j = 0 ) MaxLen(i, j) = 0 /兩個(gè)空串的最長(zhǎng)公共子序列長(zhǎng)度是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 長(zhǎng)度和s2 長(zhǎng)度的乘積?？梢杂靡粋€(gè)

19、二維數(shù)組來(lái)存儲(chǔ)各個(gè)狀態(tài)下的“值”。 本問(wèn)題的兩個(gè)子問(wèn)題，和原問(wèn)題形式完全一致的，只不過(guò)規(guī)模小了一點(diǎn)。,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 + )