第3章動態規劃(2)1最長公共子序列最大子段和內容矩陣連乘問題；最長公共子序列；凸多邊形最優三角剖分；流水作業調度；背包問題；23.3最長公共子序列子序列：若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}是X的子序列，這是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例：序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相應的遞增下標序列為{2,3,5,7}。3最長公共子序列給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例：若X={A,B,C,B,D,A,B}Y={B,D,C,A,B,A}則序列{B,C,A}是X和Y的一個公共子序列，但序列{B,C,B,A}是X和Y的最長公共子序列。4最長公共子序列問題給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。求解方法：窮舉法

動態規劃法51.窮舉法對X={x1,x2,…,xm}的所有子序列，檢查它是否也是Y={y1,y2,…,yn}的子序列，從而確定它是否為X和Y的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列。6窮舉法─時間復雜度分析X={x1,x2,…,xm}的所有子序列個數：

2m對X的每個子序列檢查它是否也是Y的子序列：

O(n)最壞情況下時間復雜度：

O(n2m)─指數時間72.動態規劃法最長公共子序列的結構子問題的遞歸結構計算最優值構造最長公共子序列算法的改進8(1)最長公共子序列的結構設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列。若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列。若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。9最優子結構性質2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。最長公共子序列問題具有最優子結構性質。10(2)子問題的遞歸結構由最長公共子序列問題的最優子結構性質可知，要找出X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm（或yn）；當xm≠yn時，必須解兩個子問題：找出Xm-1和Y的最長公共子序列及X和Yn-1的最長公共子序列這兩個公共子序列中較長者即為X和Y的最長公共子序列。11子問題的遞歸結構建立子問題最優值的遞歸關系：用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi={x1,x2,…,xi}，Yj={y1,y2,…,yj}當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時c[i,j]=0。12遞歸法算法描述13RECURSIVE-LCS-LENGTH(X,Y,i,j) ifi==0orj==0 return0 ifX[i]==Y[j] c[i,j]=RECURSIVE-LCS-LENGTH(X,Y,i-1,j-1)+1 else c[i,j]=max{RECURSIVE-LCS-LENGTH(X,Y,i-1,j),

RECURSIVE-LCS-LENGTH(X,Y,i,j-1)} returnc[i,j]時間復雜度分析最壞情況下，每次遞歸需求解兩個子問題。14遞歸樹15(3)計算最優值由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。16動態規劃法算法描述LCS-LENGTH(X,Y,m,n) letb[1..m,1..n]andc[0..m,0..n]benewtables fori=1tom c[i,0]=0 forj=0ton c[0,j]=0 …17LCS-LENGTH(X,Y,m,n) … fori=1tom forj=1ton ifX[i]==Y[j] c[i,j]=c[i-1,j-1]+1 b[i,j]=“↖” elseifc[i-1,j]≥c[i,j-1] c[i,j]=c[i-1,j] b[i,j]=“↑” else c[i,j]=c[i-1,j] b[i,j]=“←” returncandb18例題19X={A,B,C,B,D,A,B}Y={B,D,C,A,B,A}(4)構造最長公共子序列

PRINT-LCS(b,X,i,j) ifi==0orj==0 return ifb[i,j]==“↖”

PRINT-LCS(b,X,i-1,j-1) printX[i] elseifb[i,j]==“↑”

PRINT-LCS(b,X,i-1,j) else

PRINT-LCS(b,X,i,j-1)20例題21內容矩陣連乘問題；最長公共子序列；最大子段和；凸多邊形最優三角剖分；流水作業調度；背包問題；22實例233.4最大子段和給定由n個整數（可能為負整數）組成的序列，求該序列形如的子段和的最大值。當所有整數均為負整數時，定義其最大子段和為0。依上述定義，所求的最優值為243.4最大子段和例如：當時，最大子段和為251、簡單算法窮舉法：求取所有可能的有序對(i,j)情況下的子段和26intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(intk=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}27計算時間O(n3)28intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){

intthissum=0; for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}考慮：計算時間O(n2)2、分治算法如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種情形：與a[1:n/2]的最大子段和相同；與a[n/2+1:n]的最大子段和相同為，且，292、分治算法情形(1)和(2)可遞歸求得情形(3)，a[n/2]和a[n/2+1]在最優子序列中。在a[1:n/2]中計算出在a[n/2+1:n]中計算出則s1+s2即為出現情形(3)時的最優值30T(n)=O(nlogn)intMaxSubSum(int*a,intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);……}31調用MaxSubSum(a,1,n)else{……ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}……}32else{……ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=min(sum,leftsum,rightsum);returnsum;}333、動態規劃算法若記，則所求的最大子段和為而對于當時，否則，動態規劃遞歸式：343、動態規劃算法intMaxSum(intn,int*a){ intsum=0,b=0; for(inti=1;i<=n;i++){ if(b>0)b+=a[i]; elseb=a[i]; if(b>sum)sum=b; } returnsum;}35T(n)=O(n)4、最大子矩陣和問題是最大子段和問題向二維的推廣最大子矩陣和問題：給定一個m行n列的整數矩陣A，求矩陣A的一個子矩陣，使其各元素之和最大。用二維數組a[1:m][1:n]表示給定的m行n列的整數矩陣。4、最大子矩陣和問題子數組a[i1:i2][j1:j2]表示左上角和右下角行列坐標分別為(i1,j1)和(i2,j2)的子矩陣，其各元素之和記為最大子矩陣和問題的最優值為374、最大子矩陣和問題設，則384、最大子矩陣和問題intMaxSum2