1、程序設計實習,第八講 動態(tài)規(guī)劃,樹形遞歸存在冗余計算,例1：POJ 2753 Fibonacci數(shù)列 求 Fibonacci數(shù)列的第n項 int f(int n) if(n=0 | n=1) return n; return f(n-1)+f(n-2); ,f(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),1,1,0,0,1,0,1,0,冗余計算,計算過程中存在冗余計算，為了除去冗余計算 可以從已知條件開始計算，并記錄計算過程中 的中間結果。,樹形遞歸存在冗余計算,去除冗余： int fn+1;

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

3、個數(shù)字到底邊的各條路徑中，數(shù)字之和最大的那條路徑的數(shù)字之和，則本題是要求 MaxSum(0,0) 。（假設行編號和一行內數(shù)字編號都從0開始)。 典型的動態(tài)規(guī)劃問題。從某個D(r, j)出發(fā)，顯然下一步只能走D(r+1,j)或者D(r+1, j+1)，所以，對于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),#include #define MAX 101 int triangleMAXMAX; int n; int lo

4、ngestPath(int i, int j); void main() int i,j; cin n; for(i=0;i triangleij; cout longestPath(0,0) endl; ,數(shù)字三角形的遞歸程序：,數(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; 超時！,為什么超時？,回答：重復計算,7 3 8 8 1 0 2

5、7 4 4 4 5 2 6 5,如果采用遞規(guī)的方法，深度遍歷每條路徑，存在大量重復計算。則時間復雜度為 2n,對于 n = 100，肯定超時。,改進思想：從下往上計算，對于每一點，只需要保留從下面來的路徑中和最大的路徑的和即可。因為在它上面的點只關心到達它的最大路徑和，不關心它從那條路經(jīng)上來的。,解法1： 如果每算出一個MaxSum( r,j)就保存起來，則可以用o(n2)時間完成計算。因為三角形的數(shù)字總數(shù)是 n(n+1)/2 此時需要的存儲空間是： int D100100; /用于存儲三角形中的數(shù)字 int aMaxSum 100100; /用于存儲每個MaxSum(r,j),#define

6、 MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; main() int i, j; scanf(%d, ,解法2: 沒必要用二維Sum數(shù)組存儲每一個MaxSum(r,j),只要從底層一行行向上遞推，那么只要一維數(shù)組Sum100即可,即只要存儲一行的MaxSum值就可以。 比解法一改進之處在于節(jié)省空間，時間復雜度不變,#define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM +

7、 10; main() int i, j; scanf(%d, ,遞歸到動規(guī)的一般轉化方法,原來遞歸函數(shù)有幾個參數(shù)，就定義一個幾維的數(shù)組，數(shù)組的下標是遞歸函數(shù)參數(shù)的取值范圍，數(shù)組元素的值是遞歸函數(shù)的返回值，這樣就可以從邊界開始，逐步填充數(shù)組，相當于計算遞歸函數(shù)值的逆過程。,例題：最長上升子序列 問題描述 一個數(shù)的序列bi，當b1 b2 . bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2, ., aN)，我們可以得到一些上升的子序列(ai1, ai2, ., aiK)，這里1 = i1 i2 . iK = N。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的

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

9、原問題形式上并不完全一樣，但是只要這N個子問題都解決了，那么這N個子問題的解中，最大的那個就是整個問題的解。,2. 確定狀態(tài)： 上所述的子問題只和一個變量相關，就是數(shù)字的位置。因此序列中數(shù)的位置k 就是“狀態(tài)”，而狀態(tài) k 對應的“值”，就是以ak做為“終點”的最長上升子序列的長度。這個問題的狀態(tài)一共有N個。,3. 找出狀態(tài)轉移方程： 狀態(tài)定義出來后，轉移方程就不難想了。假定MaxLen (k)表示以ak做為“終點”的最長上升子序列的長度，那么： MaxLen (1) = 1 MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak且 k1 + 1 這個狀態(tài)轉移方程的意

10、思就是，MaxLen(k)的值，就是在ak左邊，“終點”數(shù)值小于ak ，且長度最大的那個上升子序列的長度再加1。因為ak左邊任何“終點”小于ak的子序列，加上ak后就能形成一個更長的上升子序列。 實際實現(xiàn)的時候，可以不必編寫遞歸函數(shù)，因為從 MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3),#include #include #define MAX_N 1000 int bMAX_N + 10; int aMaxLenMAX_N + 10; main() int N; scanf(%d, /記錄滿足條件的，第i個數(shù)左邊的上升

11、子序列的最大長度,for( int j = 1; j bj ) if( nTmp aMaxLenj ) nTmp = aMaxLenj; aMaxLeni = nTmp + 1; int nMax = -1; for( i = 1;i = N;i + ) if( nMax aMaxLeni) nMax = aMaxLeni; printf(%dn, nMax); ,例題： Poj 1458 最長公共子序列,給出兩個字符串，求出這樣的一個最長的公共子序列的長度：子序列中的每個字符都能在兩個原串中找到，而且每個字符的先后順序和原串中的先后順序一致。,最長公共子序列,Sample Input abc

12、fbc abfcab programming contest abcd mnp Sample Output 4 2 0,輸入兩個子串s1,s2, 設MaxLen(i,j)表示: s1的左邊i個字符形成的子串，與s2左邊的j個字符形成的子串的最長公共子序列的長度 MaxLen(i,j) 就是本題的“狀態(tài)” 假定 len1 = strlen(s1),len2 = strlen(s2） 那么題目就是要求 MaxLen(len1,len2),最長公共子序列,顯然：MaxLen(n,0) = 0 ( n= 0len1） MaxLen(0,n) = 0 ( n=0len2） 遞推公式： if ( s1i-

13、1 = s2j-1 ) MaxLen(i,j) = MaxLen(i-1,j-1) + 1; else MaxLen(i,j) = Max(MaxLen(i,j-1), MaxLen(i-1,j) );,最長公共子序列,S1,s1i-1,S2,s2j-1,S1i-1,S2j-1,S1長度為 i,S2長度為 j,MaxLen(S1,S2)不會比MaxLen(S1,S2j-1) 和 MaxLen(S1i-1,S2)都大，也不會比兩者中任何一個小,#include #include char sz11000; char sz21000; int anMaxLen10001000; main() wh

14、ile( cin sz1 sz2 ) int nLength1 = strlen( sz1); int nLength2 = strlen( sz2); int nTmp; int i,j; for( i = 0;i = nLength1; i + ) anMaxLeni0 = 0; for( j = 0;j = nLength2; j + ) anMaxLen0j = 0;,for( i = 1;i nLen2 ) anMaxLenij = nLen1; else anMaxLenij = nLen2; cout anMaxLennLength1nLength2 endl; ,活學活用,掌握

15、遞歸和動態(tài)規(guī)劃的思想，解決問題時靈活應用,例題： POJ 1661 Help Jimmy,Help Jimmy 是在下圖所示的場景上完成的游戲：,場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。 Jimmy老鼠在時刻0從高于所有平臺的某處開始下落，它的下落速度始終為1米/秒。當Jimmy落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是1米/秒。當Jimmy跑到平臺的邊緣時，開始繼續(xù)下落。Jimmy每次下落的高度不能超過MAX米，不然就會摔死，游戲也會結束。 設計一個程序，計算Jimmy到地面時可能的最早時間。,輸入數(shù)據(jù) 第一行是測試數(shù)據(jù)的組數(shù)t（0

16、 = t = 20）。每組測試數(shù)據(jù)的第一行是四個整數(shù)N，X，Y，MAX，用空格分隔。N是平臺的數(shù)目（不包括地面），X和Y是Jimmy開始下落的位置的橫豎坐標，MAX是一次下落的最大高度。接下來的N行每行描述一個平臺，包括三個整數(shù)，X1i，X2i和Hi。Hi表示平臺的高度，X1i和X2i表示平臺左右端點的橫坐標。1 = N = 1000，-20000 = X, X1i, X2i = 20000，0 Hi Y = 20000（i = 1.N）。所有坐標的單位都是米。 Jimmy的大小和平臺的厚度均忽略不計。如果Jimmy恰好落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重疊或相連。測試數(shù)據(jù)保

17、Jimmy一定能安全到達地面。,輸出要求 對輸入的每組測試數(shù)據(jù)，輸出一個整數(shù)，Jimmy到地面時可能的最早時間。 輸入樣例 1 3 8 17 20 0 10 8 0 10 13 4 14 3 輸出樣例 23,Jimmy跳到一塊板上后，可以有兩種選擇，向左走，或向右走。走到左端和走到右端所需的時間，是很容易算的。如果我們能知道，以左端為起點到達地面的最短時間，和以右端為起點到達地面的最短時間，那么向左走還是向右走，就很容選擇了。因此，整個問題就被分解成兩個子問題，即Jimmy所在位置下方第一塊板左端為起點到地面的最短時間，和右端為起點到地面的最短時間。這兩個子問題在形式上和原問題是完全一致的。將

18、板子從上到下從1開始進行無重復的編號(越高的板子編號越小，高度相同的幾塊板子，哪塊編號在前無所謂)，那么，和上面兩個子問題相關的變量就只有板子的編號。,解題思路：,不妨認為Jimmy開始的位置是一個編號為0，長度為0的板子，假設LeftMinTime(k)表示從k號板子左端到地面的最短時間，RightMinTime(k)表示從k號板子右端到地面的最短時間，那么，求板子k左端點到地面的最短時間的方法如下：,if ( 板子k左端正下方?jīng)]有別的板子) if( 板子k的高度 h(k) 大于Max) LeftMinTime(k) = ; else LeftMinTime(k) = h(k); else if( 板子k左端正下方的板子編號是m ) LeftMinTime(k) = h(k)-h(m) + Min( LeftMinTime(m) + Lx(k)-Lx(m), RightMinTime(m) + Rx(m)-Lx(k); ,上面，h(i)就代表i號板子的高度