程序設(shè)計(jì)實(shí)習(xí)講義8

1、程序設(shè)計(jì)實(shí)習(xí)第八講動(dòng)態(tài)規(guī)劃1樹(shù)形遞歸存在冗余計(jì)算例1：POJ 2753 Fibonacci數(shù)列求 Fibonacci數(shù)列的第n項(xiàng)int f(int n) if(n=0 | n=1) return n; return f(n-1)+f(n-2);2f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余計(jì)算計(jì)算過(guò)程中存在冗余計(jì)算，為了除去冗余計(jì)算可以從已知條件開(kāi)始計(jì)算，并記錄計(jì)算過(guò)程中的中間結(jié)果。樹(shù)形遞歸存在冗余計(jì)算3去除冗余：int fn+1;f1=f2=1;int I;for(i=3;i=n;i+) fi =

2、 fi-1+fi-2;cout fn 動(dòng)態(tài)規(guī)劃4例2POJ1163 數(shù)字三角形在上面的數(shù)字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經(jīng)過(guò)的數(shù)字之和最大。路徑上的每一步都只能往左下或右下走。只需要求出這個(gè)最大和即可，不必給出具體路徑。三角形的行數(shù)大于1小于等于100，數(shù)字為 0 - 99 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 5輸入格式：/三角形行數(shù)。下面是三角形73 88 1 02 7 4 4 4 5 2 6 5 要求輸出最大和6解題思路： 以D( r, j)表示第r行第 j 個(gè)數(shù)字，以MaxSum(r, j) 代表從第 r 行的第 j 個(gè)數(shù)字到底邊的各條路徑中，數(shù)

3、字之和最大的那條路徑的數(shù)字之和，則本題是要求 MaxSum(0,0) 。（假設(shè)行編號(hào)和一行內(nèi)數(shù)字編號(hào)都從0開(kāi)始)。 典型的動(dòng)態(tài)規(guī)劃問(wèn)題。從某個(gè)D(r, j)出發(fā)，顯然下一步只能走D(r+1,j)或者D(r+1, j+1)，所以，對(duì)于N行的三角形：if ( r = N-1 ) MaxSum(r,j) = D(N-1,j)else MaxSum( r, j) = Max(MaxSum(r1,j), MaxSum(r+1,j+1) ) + D(r,j),7#include #define MAX 101 int triangleMAXMAX; int n; int longestPath(int i

4、, int j); void main() int i,j; cin n; for(i=0;in;i+) for(j=0;j triangleij; cout longestPath(0,0) endl; 數(shù)字三角形的遞歸程序：8數(shù)字三角形的遞歸程序：int longestPath(int i, int j) if(i=n) return 0; int x = longestPath(i+1,j); int y = longestPath(i+1,j+1); if(xy) x=y; return x+triangleij; 超時(shí)！9為什么超時(shí)？回答：重復(fù)計(jì)算 7 3 8 8 1 0 2 7 4

5、 4 4 5 2 6 5 如果采用遞規(guī)的方法，深度遍歷每條路徑，存在大量重復(fù)計(jì)算。則時(shí)間復(fù)雜度為 2n,對(duì)于 n = 100，肯定超時(shí)。10改進(jìn)思想：從下往上計(jì)算，對(duì)于每一點(diǎn)，只需要保留從下面來(lái)的路徑中和最大的路徑的和即可。因?yàn)樵谒厦娴狞c(diǎn)只關(guān)心到達(dá)它的最大路徑和，不關(guān)心它從那條路經(jīng)上來(lái)的。11解法1：如果每算出一個(gè)MaxSum( r,j)就保存起來(lái)，則可以用o(n2)時(shí)間完成計(jì)算。因?yàn)槿切蔚臄?shù)字總數(shù)是 n(n+1)/2此時(shí)需要的存儲(chǔ)空間是：int D100100; /用于存儲(chǔ)三角形中的數(shù)字 int aMaxSum 100100; /用于存儲(chǔ)每個(gè)MaxSum(r,j)12#define MA

6、X_NUM 100int DMAX_NUM + 10MAX_NUM + 10; int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;main() int i, j; scanf(%d, & N); for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) scanf(%d, &Dij);for( j = 1; j 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; else aMaxSumi-1j = aMaxSumij+1 + D

7、i-1j;printf(%d, aMaxSum11);13解法2:沒(méi)必要用二維Sum數(shù)組存儲(chǔ)每一個(gè)MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組Sum100即可,即只要存儲(chǔ)一行的MaxSum值就可以。比解法一改進(jìn)之處在于節(jié)省空間，時(shí)間復(fù)雜度不變14#define MAX_NUM 100int DMAX_NUM + 10MAX_NUM + 10; int N;int aMaxSumMAX_NUM + 10;main() int i, j; scanf(%d, & N); for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) sca

8、nf(%d, &Dij);for( j = 1; j 1 ; i - ) for( j = 1; j aMaxSumj+1 ) aMaxSumj = aMaxSumj + Di-1j; else aMaxSumj = aMaxSumj+1 + Di-1j;printf(%d, aMaxSum1);15遞歸到動(dòng)規(guī)的一般轉(zhuǎn)化方法原來(lái)遞歸函數(shù)有幾個(gè)參數(shù)，就定義一個(gè)幾維的數(shù)組，數(shù)組的下標(biāo)是遞歸函數(shù)參數(shù)的取值范圍，數(shù)組元素的值是遞歸函數(shù)的返回值，這樣就可以從邊界開(kāi)始，逐步填充數(shù)組，相當(dāng)于計(jì)算遞歸函數(shù)值的逆過(guò)程。16例題：最長(zhǎng)上升子序列問(wèn)題描述一個(gè)數(shù)的序列bi，當(dāng)b1 b2 . bS的時(shí)候，我們稱(chēng)這個(gè)序列

9、是上升的。對(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)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4，比如子序列(1, 3, 5, 8). 你的任務(wù)，就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。17輸入數(shù)據(jù)輸入的第一行是序列的長(zhǎng)度N (1 = N = 1000)。第二行給出序列中的N個(gè)整數(shù)，這些整數(shù)的取值范圍都在0到10000。輸出要求最長(zhǎng)上升子序列的長(zhǎng)度。輸入樣例71 7 3

10、5 9 4 8輸出樣例418解題思路找子問(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ù)，稱(chēng)為該子序列的“終點(diǎn)”。雖然這個(gè)子問(wèn)題和原問(wèn)題形式上并不完全一樣，但是只要這N個(gè)子問(wèn)題都解決了，那么這N個(gè)子問(wèn)題的解中，最大的那個(gè)就是整個(gè)問(wèn)題的解。192. 確定狀態(tài)：上所述的子問(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è)。203. 找出狀態(tài)轉(zhuǎn)移方程：狀態(tài)定義出來(lái)后，轉(zhuǎn)移方程就不難想了。假定Max

11、Len (k)表示以ak做為“終點(diǎn)”的最長(zhǎng)上升子序列的長(zhǎng)度，那么：MaxLen (1) = 1MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak且 k1 + 1這個(gè)狀態(tài)轉(zhuǎn)移方程的意思就是，MaxLen(k)的值，就是在ak左邊，“終點(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)21#include #incl

12、ude #define MAX_N 1000int bMAX_N + 10;int aMaxLenMAX_N + 10;main()int N;scanf(%d, & N);for( int i = 1;i = N;i + )scanf(%d, & bi);aMaxLen1 = 1;for( i = 2; i = N; i + ) /每次求以第i個(gè)數(shù)為終點(diǎn)的最長(zhǎng)上升子序列的長(zhǎng)度int nTmp = 0; /記錄滿足條件的，第i個(gè)數(shù)左邊的上升子序列的最大長(zhǎng)度22for( int j = 1; j bj ) if( nTmp aMaxLenj )nTmp = aMaxLenj;aMaxLeni =

13、 nTmp + 1;int nMax = -1;for( i = 1;i = N;i + )if( nMax aMaxLeni)nMax = aMaxLeni;printf(%dn, nMax);23例題： Poj 1458 最長(zhǎng)公共子序列 給出兩個(gè)字符串，求出這樣的一個(gè)最長(zhǎng)的公共子序列的長(zhǎng)度：子序列中的每個(gè)字符都能在兩個(gè)原串中找到，而且每個(gè)字符的先后順序和原串中的先后順序一致。24最長(zhǎng)公共子序列Sample Inputabcfbc abfcab programming contestabcd mnp Sample Output420 25輸入兩個(gè)子串s1,s2,設(shè)MaxLen(i,j)表示:

14、 s1的左邊i個(gè)字符形成的子串，與s2左邊的j個(gè)字符形成的子串的最長(zhǎng)公共子序列的長(zhǎng)度MaxLen(i,j) 就是本題的“狀態(tài)”假定 len1 = strlen(s1),len2 = strlen(s2）那么題目就是要求MaxLen(len1,len2)最長(zhǎng)公共子序列26顯然：MaxLen(n,0) = 0 ( n= 0len1） MaxLen(0,n) = 0 ( n=0len2）遞推公式：if ( s1i-1 = s2j-1 )MaxLen(i,j) = MaxLen(i-1,j-1) + 1;elseMaxLen(i,j) = Max(MaxLen(i,j-1), MaxLen(i-1,j

15、) ); 最長(zhǎng)公共子序列27S1s1i-1S2s2j-1S1i-1S2j-1S1長(zhǎng)度為 iS2長(zhǎng)度為 jMaxLen(S1,S2)不會(huì)比MaxLen(S1,S2j-1) 和MaxLen(S1i-1,S2)都大，也不會(huì)比兩者中任何一個(gè)小28#include #include char sz11000;char sz21000;int anMaxLen10001000;main()while( cin sz1 sz2 ) int nLength1 = strlen( sz1);int nLength2 = strlen( sz2);int nTmp;int i,j;for( i = 0;i = n

16、Length1; i + )anMaxLeni0 = 0;for( j = 0;j = nLength2; j + )anMaxLen0j = 0;29for( i = 1;i = nLength1;i + ) for( j = 1; j nLen2 )anMaxLenij = nLen1;elseanMaxLenij = nLen2;cout anMaxLennLength1nLength2 endl;30活學(xué)活用掌握遞歸和動(dòng)態(tài)規(guī)劃的思想，解決問(wèn)題時(shí)靈活應(yīng)用31例題： POJ 1661 Help JimmyHelp Jimmy 是在下圖所示的場(chǎng)景上完成的游戲：32場(chǎng)景中包括多個(gè)長(zhǎng)度和高度各不

17、相同的平臺(tái)。地面是最低的平臺(tái)，高度為零，長(zhǎng)度無(wú)限。 Jimmy老鼠在時(shí)刻0從高于所有平臺(tái)的某處開(kāi)始下落，它的下落速度始終為1米/秒。當(dāng)Jimmy落到某個(gè)平臺(tái)上時(shí)，游戲者選擇讓它向左還是向右跑，它跑動(dòng)的速度也是1米/秒。當(dāng)Jimmy跑到平臺(tái)的邊緣時(shí)，開(kāi)始繼續(xù)下落。Jimmy每次下落的高度不能超過(guò)MAX米，不然就會(huì)摔死，游戲也會(huì)結(jié)束。 設(shè)計(jì)一個(gè)程序，計(jì)算Jimmy到地面時(shí)可能的最早時(shí)間。 33輸入數(shù)據(jù)第一行是測(cè)試數(shù)據(jù)的組數(shù)t（0 = t = 20）。每組測(cè)試數(shù)據(jù)的第一行是四個(gè)整數(shù)N，X，Y，MAX，用空格分隔。N是平臺(tái)的數(shù)目（不包括地面），X和Y是Jimmy開(kāi)始下落的位置的橫豎坐標(biāo)，MAX是一次下

18、落的最大高度。接下來(lái)的N行每行描述一個(gè)平臺(tái)，包括三個(gè)整數(shù)，X1i，X2i和Hi。Hi表示平臺(tái)的高度，X1i和X2i表示平臺(tái)左右端點(diǎn)的橫坐標(biāo)。1 = N = 1000，-20000 = X, X1i, X2i = 20000，0 Hi Y = 20000（i = 1.N）。所有坐標(biāo)的單位都是米。 Jimmy的大小和平臺(tái)的厚度均忽略不計(jì)。如果Jimmy恰好落在某個(gè)平臺(tái)的邊緣，被視為落在平臺(tái)上。所有的平臺(tái)均不重疊或相連。測(cè)試數(shù)據(jù)保Jimmy一定能安全到達(dá)地面。34輸出要求對(duì)輸入的每組測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)，Jimmy到地面時(shí)可能的最早時(shí)間。輸入樣例13 8 17 200 10 80 10 134 1

19、4 3輸出樣例2335Jimmy跳到一塊板上后，可以有兩種選擇，向左走，或向右走。走到左端和走到右端所需的時(shí)間，是很容易算的。如果我們能知道，以左端為起點(diǎn)到達(dá)地面的最短時(shí)間，和以右端為起點(diǎn)到達(dá)地面的最短時(shí)間，那么向左走還是向右走，就很容選擇了。因此，整個(gè)問(wèn)題就被分解成兩個(gè)子問(wèn)題，即Jimmy所在位置下方第一塊板左端為起點(diǎn)到地面的最短時(shí)間，和右端為起點(diǎn)到地面的最短時(shí)間。這兩個(gè)子問(wèn)題在形式上和原問(wèn)題是完全一致的。將板子從上到下從1開(kāi)始進(jìn)行無(wú)重復(fù)的編號(hào)(越高的板子編號(hào)越小，高度相同的幾塊板子，哪塊編號(hào)在前無(wú)所謂)，那么，和上面兩個(gè)子問(wèn)題相關(guān)的變量就只有板子的編號(hào)。解題思路：36不妨認(rèn)為Jimmy開(kāi)始的位置是一個(gè)編號(hào)為0，長(zhǎng)度為0的板子，假設(shè)LeftMinTime(k)表示從k號(hào)板子左端到地面的最短時(shí)間，RightMinTime(k)表示從k號(hào)板子右端到地面的最短時(shí)間，那么，求板子k左端點(diǎn)到地面的最短時(shí)間的方法如下： 37if ( 板子k左端正下方?jīng)]有別的板子) if( 板子k的高度 h(k) 大于Max)LeftMinTime(k) = ;elseLeftMinTime(k) = h(k);else if( 板子k左端正下方的板子編號(hào)是m ) LeftMinTime(k) = h(k)-h(m) + Min( LeftMinTime(m) + Lx(k)-Lx(