计算机算法基础 第2版 习题及答案 第6章

PAGE44第6章 动态规划假设矩阵A、B、C、D、E的维数序列如下，找出其最佳连乘顺序。(a)5,10,3,12,5,50解：最佳顺序为(((AB)(CD))E)。

8,10,6,11,3,35解：最佳顺序为((A(B(CD)))E)。

找出下面二序列的最长公共子序列：<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1,0>iiyj010110110j01234567890000000000001111111101122222220112223333012233344401233344450123444555012344555601234556660xi112030410xi1120304150617081它们的LCS是<1,0,0,1,1,0>，其长度为6。下面表中列出了搜索7个关键字A[1..7]的各种情况的概率。请为他们找出一个最佳二元搜索树并求出其平均复杂度。i01234567pi0.040.060.080.020.100.120.14qi0.060.060.060.060.050.050.050.05解：表W(i,j),ji\0123456710.060.160.280.420.490.640.811.0020.060.180.320.390.540.710.9030.060.200.270.420.590.7840.060.130.280.450.6450.050.200.370.5660.050.220.4170.050.2480.05

表E(i,j),ji\0123456710.060.280.621.021.341.832.443.1220.060.300.680.931.411.962.6130.060.320.571.041.482.1340.060.240.571.011.5550.050.300.721.2060.050.320.7870.050.3480.05表root(i,j),ji\012345671-12223352-2333553-334554-45565-5666-677-7这个最佳二元搜索树如下。它的平均复杂度是3.12次比较。AA[5]A[2]A[1]A[3]A[6]A[7]d0d1d2d3d4A[4]d6d5d7给出一个在序列A[1..n]中找最长递增子序列的O(nlgn)算法的伪码。解： Improved-LCS(A[1..n],L,B,length)L¬L[1]¬1 //当前只有一个长度l=1的初始解[1]¬nil //父亲未知S[0]¬A[0]- //因二元搜索的需要，加的一个左边点T[0]¬0 //S[0]在序列A中的序号S[1]¬A[1] //长度为1的子序列的结尾元素开始只有A[1]T[1]¬1 //S[1]在序列A中的序号S[L+1]¬ //因二元搜索的需要，加的一个右边点fori=2ton Binary-search(S,0,L+1,A[i],k) //调用二元搜索子程序，其伪码在后面。 //找出k使得S[k]A[i]<S[k+1]，见下面伪码。 L[i]¬k+1 //L[i]长度必为k+1 [i]¬T[k] //A[i]接在A[j]后面，这里[i]=j=T[k] S[k+1]¬A[i] //因为A[i]<S[k+1],更新S[k+1] T[k+1]¬i //同时更新对应的序号 ifL[i]>L then L¬L+1 S[L+1]¬ //多了一个长度 endifendfor //下面找出最大的L[i]值index¬1fori=2ton ifL[index]<L[i] thenindex¬iendforlength¬L[index] //下面把找到的LIS输出到B[1..length]forj=lengthdownto1 B[j]¬A[index] index¬[index]endforreturnB[1..length]End BinarySearch(S,p,r,x,k) //输入时有S[p]x<S[r]，输出k使得S[k]x<S[k+1]ifp=r then kp exitendifmidpoint¬ë(p+r)/2ûifS[midpoint]>x thenBinarySearch(S,p,midpoint,x,k) elseBinarySearch(S,midpoint,r,x,k)endifEnd假设我们要将一根大型长钢管锯成若干段。我们在要锯的地方打上标记，一共是n个标记。这些标记距离钢管左端的距离，从左到右，分别是a1，a2，…，an厘米。这个钢管的总长是l厘米，l>an(参见下图)。当我们将钢管锯为两截时，需要的代价与当时被锯钢管的长度成正比，比例是每一厘米p元。请用动态规划设计一个算法，找出最优的顺序来完成这n处的切割并使总的代价最小。分析你的算法的复杂度。(提示：用a0=0和an+1=l表示钢管左端和右端位置。用[ai,aj]表示从标记ai到标记aj这段钢管。用C(i,j)表示完成对[ai,aj]这段钢管的切割任务所需的最小代价，也就是完成所有ak(i<k<j)处的切割所需代价。找出C(i,j)的归纳公式。)以下面数据为例，用你在(a)中的算法找出最优的切割顺序和总代价。请显示你的计算过程。a1=2，a2=5，a3=9，a4=14，l=15，p=1。解：(a) 定义C(i,j)=切割钢管[ai,aj]（子问题）所需最小代价。我们有以下归纳公式：C(i,j)=mini+1≤k≤j-1{C(i,k)+C(i,j)=0 (初始解) 如果j=i+1在下面的伪码中，我们用表S[i,j]记录切割钢管[ai,aj]的位置。Optimal-Cutting(A,n,p)fori¬0ton C[i,i+1]¬0 //初始解endforforl¬2ton+1 //l=j–i是子问题的规模 fori¬0to(n+1)–l j¬i+l C[i,j]¬¥ fork¬i+1toj-1 q¬C[i,k]+C[k,j]+p(aj–ai) ifq<C[i,j] then C[i,j]¬q S[i,j]¬k endif endfor endforendforreturnCandSEnd上面算法的复杂度显然是O(n3)。(b) a1=2,a2=5,a3=9,a4=14,l=15,p=1。表C、表S和表示顺序的二叉树构造如下，总的代价是35元。a1a1a2a3a4a3a2a4a1如下图所示，顺序放好的n根钢管的重量顺序为W[i](1£i£n)。我们需要把他们依照顺序焊成一根钢管，但每次焊接可任意选两根相邻的钢管来焊接。每次焊接的代价与被焊两段钢管的总重量成正比。为简单起见，把代价定为被焊两段钢管的总重量。例如，W[1]=5,W[2]=1,W[3]=2，如果先把W[1]和W[2]焊好，代价为5+1=6。焊好的这块有重量6，再把W[3]焊上，又要代价6+2=8，总代价是14。但如果先焊W[2]和W[3]，再焊W[1]，则总代价为11。用动态规划设计一个算法，计算出最优的焊接顺序使总代价最小。应用你上面的算法求出以下5根钢管的最优焊接顺序和总代价：W[1]=8,W[2]=1,W[3]=7,W[4]=2,W[5]=9。解：(a) 我们用[ai,aj]表示把从ai到aj这一段的钢管焊好后的钢管。找[ai,aj]的最优焊接顺序定义为子问题。我们定义C(i,j)=将钢管[ai,aj]焊好的最小代价(子问题的解，1ijn)。我们有以下归纳公式：C(i,j)=mini≤k≤j-1{Ci,k+CkC(i,i)=0 (初始解，i=1，2，…，n)如果定义W(i,j)=t=ijW[t]C(i,j)=mini≤k≤j-1{Ci,kC(i,i)=0 在下面的伪码中，我们用表S[i,j]记录将钢管[ai,aj]分为两段的地方，也就是最后一次应焊的位置。表W(i,j)(1£i£j£n)可以先计算好。Welding(W,n)fori¬1ton C[i,i]¬0endfor //初始解forl¬1ton-1 fori¬1ton–l j¬i+l C[i,j]¬¥ fork¬itoj-1 q¬C[i,k]+C[k+1,j]+W(i,j) //W(i,j)已算好，伪码在后面 ifq<C[i,j] then C[i,j]¬q S[i,j]¬k endif endfor endforendforreturnCandSEndWeight(W,n)fori¬1ton W[i,i]¬W[i]endforfori¬1ton-1 forj¬i+1ton W[i,j]¬W[i,j-1]+W[j] endforendforreturnWEnd(b)W[1]=8,W[2]=1,W[3]=7,W[4]=2,W[5]=9。解:表W(i,j),j表C(i,j),j1234512345189161827109243662218101920818373791830927421140115950表S(i,j),j1234511113223433444最优焊接顺序由下面二叉树表示。总代价为62(=8+16+11+27)。如下图所示，顺序放好的n根钢管的重量顺序为W[i](1£i£n)。我们需要把他们依照顺序焊成一根钢管，但每次焊接可任意选两根相邻的钢管来焊接。每次焊接的代价与被焊两段钢管中的较重的一根的重量成正比。为简单起见，就把代价定为被焊两段钢管中的较重的一根的重量。例如，W[1]=5,W[2]=1,W[3]=2，如果先把W[1]和W[2]焊好，代价为5，再把W[3]焊上，又要代价6，总代价是11。但如果先焊W[2]和W[3]，再焊W[1]，则总代价为2+5=7。用动态规划设计一个算法，计算出最优的焊接顺序使总代价最小。应用你上面的算法求出以下5根钢管的最优焊接顺序和总代价：W[1]=6,W[2]=2,W[3]=7,W[4]=5,W[5]=8。解：(a) 我们用[ai,aj]表示把从ai到aj这一段的钢管焊好后的钢管。找[ai,aj]的最优焊接顺序定义为子问题。定义C(i,j)=将钢管[ai,aj]焊好的最小代价(子问题的解，1ijn)。我们有以下归纳公式：C(i,j)=mini≤k≤j-1{Ci,k+Ck+1,j+maxt=ikWt,t=k+1jWt} 如果j>i，C如果定义W(i,j)=t=ijWC(i,j)=mini≤k≤j-1{Ci,k+CkC(i,i)=0。 在下面的伪码中，我们用表S[i,j]记录将钢管[ai,aj]分为两段的地方，也就是最后一次应焊的位置。表W(i,j)(1£i£j£n)可以先计算好。Welding(W,n)fori¬1ton C[i,i]¬0 //初始解endforforl¬1ton-1 fori¬1ton–l j¬i+l C[i,j]¬¥ fork¬itoj-1 q¬C[i,k]+C[k+1,j]+max{W(i,k),W(k+1,j)} ifq<C[i,j] then C[i,j]q S[i,j]¬k endif endfor endforendforreturnCandSEndWeight(W,n)fori¬1ton W[i,i]¬W[i]endforfori¬1ton-1 forj¬i+1ton W[i,j]¬W[i,j-1]+W[j] endforendforreturnWEnd(b)W[1]=6,W[2]=2,W[3]=7,W[4]=5,W[5]=8。解：表W(i,j),j表C(i,j),j1234512345168152028106142537229142220716283712203071945134085850表S(i,j),j1234511223223333444

最优焊接顺序由下面二叉树表示。总代价为37(=6+8+8+15)。假设一通讯公司要设计一个n路的复用器。它把n条平行的输入线路并入到一条输出线路。这个复用的过程是逐步实现的。它每次把相邻的两条线路并为一条输出线路。如果这两条线路的带宽分别是a和b的话，那么合并后的输出线路有带宽a+b。经过一系列两两合并后，我们得到一条输出线路，它的带宽是所有输入带宽之和。下面的图给出n=5的一个例子。我们假定在合并两条带宽分别是a和b的线路时的硬件代价为a+b。下图例子中的设计需要的硬件总代价是25+27+37+64=153。MUXMUXMUXMUXMUXW1=10W2=15W3=12W4=18W5=9W=25W=37W=27W=64n-wayMUX假设这n条输入线路的带宽依次为W1，W2，…，Wn，用动态规划设计一个算法来确定最优的合并顺序以使硬件总代价最小。应用你的算法为下列带宽序列确定合并的最佳顺序并给出硬件总代价：W[1]=13,W[2]=21,W[3]=17,W[4]=12,W[5]=25。解：(a)这道题和第6题做法一样。定义C(i,j)=将Wi到Wj之间所有线路合并的最小代价(子问题的解，1ijn)。我们有以下归纳公式：C(i,j)=mini≤k≤j-1{Ci,k+CkC(i,i)=0 如果定义W(i,j)=t=ijW[t]C(i,j)=mini≤k≤j-1{Ci,kC(i,i)=0 在下面的伪码中，我们用表S[i,j]记录求C(i,j)时得的k值。表W(i,j)(1£i£j£n)可以用下面子程序Bandwidth(W,n)先计算好。MUX(W,n)fori¬1ton C[i,i]¬0endforforl¬1ton-1 fori¬1ton–l j¬i+l C[i,j]¬¥ fork¬itoj-1 q¬C[i,k]+C[k+1,j]+W(i,j) ifq<C[i,j] then C[i,j]q S[i,j]¬k endif endfor endforendforreturnCandSEndBandwidth(W,n)fori¬1ton W[i,i]¬W[i]endforfori¬1ton-1 forj¬i+1ton W[i,j]¬W[i,j-1]+W[j] endforendforreturnWEnd(b)W[1]=13,W[2]=21,W[3]=17,W[4]=12,W[5]=25。表C(i,j),j表W(i,j),j123451234510348512620511334516388203879150221385075302983317295440374123750525表S(i,j),j12345112222223334445合并的顺序如下。总代价为34+29+54+88=205。MUXMUXMUXMUXMUXW1=13W2=21W3=17W4=12W5=25W=34W=54W=29W=88假设我们有三个字母或数字的序列，X[1..m]=x1x2...xm，Y[1..n]=y1y2...yn，和Z[1..m+n]=z1z2...zm+n。如果序列Z是由X和Y中的元素按顺序交汇而成，那么Z被称为X和Y的一个洗牌。例如，下面图中的序列Z=cchocohilaptes是X=chocolate和Y=chips的一个洗牌。 YY=chipsX=chocolateZ=cchocohilaptes用动态规划设计一个算法来确定序列Z是否是X和Y的一个洗牌。(提示：用M[i,j]=1表示Z[1..i+j]是X[1..i]和Y[1..j]的一个洗牌。然后找出归纳公式。)用你的算法确定以下三序列中，Z是否是X和Y的一个洗牌。X=FEAST, Y=LOVE, Z=FLOEVASET解一：有个简单的方法是先求X和Z的最长公共子序列W。如果WX，则Z不可能是X和Y的一个洗牌。如果W=X，检查把X从Z中删去后的序列是否等于Y。如果是，则Z是解二：(a) 我们建一个表M，其中M[i,j]=1(1im,1jn)表示Z[1..i+j]是X[1..i]和Y[1..j]的一个洗牌。我们有以下归纳公式。M[0,0]=1 (初始解，i=j=0)如果(j>0,M[i,j-1]=1和Z[i+j]=Y[j])或者(i>0,M[i-1,j]=1和Z[i+j]=X[i])，那么M[i,j]=1否则M[i,j]=0。如果M[m,n]=1，那么Z是X和Y的一个洗牌。伪码如下。Shuffle(X[1..m],Y[1..n],Z[1..m+n]，M，D) //D[i,j]是指向子问题的指针M[0,0]1fori¬0tom forj¬0ton if(j>0andM[i,j-1]=1andZ[i+j]=Y[j]) then M[i,j]1 D[i,j]¬“” else if(i>0andM[i-1,j]=1andZ[i+j]=X[i]) then M[i,j]1 D[i,j]¬“” else M[i,j]0 D[i,j]¬nil endif endif endforendforifM[m,n]=1 thenreturnyesandD elsereturnnoendifEnd算法显然有复杂度O(mn)。算法中表D可省略，但如果要知道Z是如何洗牌得到的，那么可从D得到。(b)X=FEAST, Y=LOVE, Z=FLOEVASET。表MY[j]LOVEX[i]01234010000F111100E200110A300010S400011T500001由上表知Z是X和Y的一个洗牌。一块长方形电路板的上下两边各有n个端口并用数字顺序标为1，2，3，…，n。根据电路设计的要求，我们需要把上边的n个端口和下边的n个端口一一配对后用导线连接。假设与上边第i个端口号连接的下边的端口号是π(i)，那么要连接的n个对子为(i,π(i))(1≤i≤n)。下面的图给出了一个n=8的例子。在这个例子中，我们有π(1)=3，π(2)=1，π(3)=6，π(4)=8，π(5)=2，π(6)=5，π(7)=4，π(8)=7。现在需要把这些对子分组使得在一组里的导线不相交从而可以分布在同一个绝缘层上。比如，在下图中，连接对子(1,3),(3,6),(4,8)的导线是不相交的。如何用最少的组数把它们分开是个有趣的问题但不在此讨论。现在的问题是，我们只找一组导线不相交的对子集合，使得它含有的对子最多。比如在下图中，{(2,1),(5,2),(6,5),(8,7)}就是最大的一组导线不相交的对子集合，它含有4个导线不相交的对子。请用最长递增子序列算法里的方法设计一个O(n2)算法来找出一组最大的导线不相交的对子集合。解：我们注意到，如果有一组导线不相交的对子，(i1,π(i1)),(i2,π(i2)),…,(ik,π(ik))，其中i1<i2<…<ik，因为他们的导线都不相交，那么我们必须有π(i1)<π(i2)<…<π(ik)。也就是说，这些电路板下方的端口号是一个递增序列。反过来，如果在序列,π(1),π(2),…,π(n)中有一个递增子序列，π(i1)<π(i2)<…<π(ik)，那么{(i1,π(i1)),(i2,π(i2)),…,(ik,π(ik))}就一定是一组导线不相交的对子。所以上述问题等价於在序列π(1),π(2),…,π(n)中找一个最长递增子序列的问题。用书中6.6节的算法即可。假定A[1..n]是一个含n个英文字母的序列。我们希望找一个最长的子序列使得它的字母是按字母顺序递增或不降。比如，A=pacubbkdffa，它的子序列abbdff就是一个按字母顺序不降的子序列。并且，它的长度是6，是一个最长的不降子序列。为方便起见，我们假定所有字母都是小写字母。请设计一个O(n)算法找出A[1..n]中一个最长不降子序列。以A=pacubbkdffa为例，用你上述算法计算其最长不降子序列。解：(a)因为英文只有26个字母，所以任何一个不降序列必以其中一字母结尾。所以我们在扫描序列A[1..n]时，建立26个变量，S[a],S[b],…,S[z]，分别用以记录到当前为止，我们所看到的以对应字母a，b，…，z结尾的最长不降序列的长度。并且，用I(a),I(b),…,I(z)分别记录这些当前最长不降序列在序列A[1..n]中终止的位置。开始时S[a]=S[b]=…=S[z]=0 //边界条件I[a]=I[b]=…=I[z]=0。 此外，我们还定义L[i]为A[1..n]中以A[i]为终止点的最长的不降序列的长度，[i]是指向子问题的指针。归纳公式如下：L[i]=1+max{S[k]|k£A[i]} //在小于等于A[i]的字母中找一个当前最长序列Longest-Alphabet-Increasing-Subsequence(A[1..n],L,B) //B[1..L]是结果fori¬atoz S[i]¬I[i]¬0endforfori=1ton s¬0 //初始化长度 forj¬atoA[i] //找max{S[k]|k£A[i]} ifS[j]>s then s¬S[j] [i]¬I[j] endif endfor L[i]¬1+s I[A[i]]¬i //以字母A[i]结尾的最长序列一定结尾于A[i]。 S[A[i]]¬L[i] //以字母A[i]结尾的不降序列的长更新endforFindksuchthatS(k)=max{S[k]|kÎ{a..z}} //这一步找最大S(k)L¬S(k)index¬I(k)forj¬Ldownto1 B[j]¬A[index] index¬[index]endforreturnB[1..L]End 因为每次计算L[i]时最多只需检查26个S[j]的值，所以算法复杂度为O(n)。(b)以A=pacubbkdffa为例，计算其最长不降子序列。我们得到下面表格。因为L[10]=6最大，所以L=6。由[10]=9开始往回找到这个字序列，abbdff。index1234567891011pacubbkdffaL[i]11232344562[i]00232566892S[a]12S[b]23S[c]2S[d]4S[f]56S[k]4S[p]1S[u]3B[i]abbdff(最长公共子串问题)一个字符串中的连续的一段字符序列称为该子符串的一个字串。例如school中cho就是一个子串。子串和子序列的区别是，子序列中字符在原序列中的位置不一定连续，而子串必须连续。两个字符串都含有的子串称为他们的公共子串。例如，university和anniversary就含有许多公共子串，例如ni，niv，y，ers等，但最长的一个是nivers。假设有字符串X=x1x2…xn和Y=y1y2…ym，请设计一个基于动态规划的O(mn)算法来找出X和Y的最长公共子串。解：定义l(i,j)为以X[i]和Y[j]结尾的X和Y的最长公共子串的长度。归纳公式为：l(i,j)=li-1,j-1+1如果xi=yj0否则 (1l(i,0)=0，l(0,j)=0 //初始解(1in,1jm)Longest-Common-String(X[1..n],Y[1..m],L)L¬0 //初始化最长公共子串的长度fori¬0ton l(i,0)¬0endfor //初始解forj¬0tom l(0,j)¬0endfor //初始解fori¬1ton forj¬1tom ifX[i]=Y[j] then l(i,j)¬l(i-1,j-1)+1 ifl(i,j)>L then L¬l(i,j) u¬i v¬j endif else l(i,j)¬0 endif endforendforreturnL,u,vEnd最长公共子串是以X[u]终止的X中的L个字符，即X[u-L+1]到X[u]这一段字符。算法复杂度显然是O(nm)。如下图(a)的例子所示，有n个多米诺骨牌，s1,s2,…,sn，按顺序竖放排成一排。994911161017182117s2s1s3s4s594911101618172117s2s1s3

s4

s5

(a)(b)让我们用U[k]和L[k]分别表示骨牌sk(1kn)竖放后上半部分数字和下半部分数字。例如，在上图(a)的例子中，U[3]=16，L[3]=10。我们假定，在开始给定的序列里，U[k]=ak，L[k]=bk。这样，n个上半部的数字形成一个序列，a1,a2,…,an，而n个下半部的数字也形成一个序列，b1,b2,…,bn。这两个给定的序列不一定是排好序的。我们希望翻转一些骨牌后使得这两个序列都是递增序列。我们假定min{ak,bk}min{ak+1,bk+1}，和max{ak,bk}max{ak+1,bk+1}(1kn-1)，使得这种排序是可能的。例如，上图(b)显示，把图(a)中s3和s4翻转后可使得上下两个序列都是递增序列。为简单起见，设akbk。请用多级图的方法设计一个O(n)的算法以确定最少需要翻转几个骨牌和哪些骨牌使得：U[1]U[2]…U[n]和L[1]L[2]…L[n]。只要求解释图的构造，不要求伪码。解：我们按如下步骤构造一个多级图：为骨牌sk(1kn)构造第k级顶点集合Vk。Vk含两个顶点，一个代表翻转前的状态，另一个代表翻转后的状态，分别记为v(k,1)和v(k,2)。我们用U(k,1)和L(k,1)表示v(k,1)的上、下两个数，用U(k,2)和L(k,2)表示v(k,2)的上、下两个数。显然有U(k,1)=ak，L(k,1)=bk，U(k,2)=bk，L(k,2)=ak。从Vk的顶点到Vk+1的顶点，1kn-1，的边定义如下：如果U(k，1)U(k+1，1)和L(k，1)L(k+1，1)，则有边(v(k，1),v(k+1，1)，权值为0。如果U(k，1)U(k+1，2)和L(k，1)L(k+1，2)，则有边(v(k，1),v(k+1，2)，权值为1。如果U(k，2)U(k+1，1)和L(k，2)L(k+1，1)，则有边(v(k，2),v(k+1，1)，权值为0。如果U(k，2)U(k+1，2)和L(k，2)L(k+1，2)，则有边(v(k，2),v(k+1，2)，权值为1。否则没有边。总的原则是，相邻两点如果满足排序要求，则有边。所有指向v(k,2)的边有权值1，因为经过v(k,2)的路径要求sk翻转。其它边有权值0。图中加上一个源点s和它到V1的两条边：(s，v(1，1))权值为0，和(s，v(1，2))权值为1。图中加上一个汇点t和Vn到t的两条边：(v(n，1)，t)权值为0，和(v(n，2)，t)权值为0。下图是以题目中的骨牌序列为例构造的多级图。显然，任何一条从s到t的路径给出一个满足排序要求的骨牌序列。如果路径经过非初始状态的骨牌（即下面一排的点）则表示这个骨牌要翻转，所以路径的总权值就等于要翻转的骨牌的个数。因此，一条最短路径对应一个最优解。下图中的最短路径用粗线条标出。可见，翻转s3和s4是一个最优解。显然，这是一个O(n)的算法。 9911v(2,1)94v(1,1)1610v(3,1)1718v(4,1)2117v(5,1)119v(2,2)

49v(1,2)1016v(3,2)

1817v(4,2)

1721v(5,2)

st0000000011111110汽车的装配需要顺序完成n步工作。假设工厂里有二条汽车装配线，A线和B线，分别都有n个车间顺序完成这n步工作。但是，A线和B线的第i个车间需要的装配时间不同，分别为A[i]和B[i](1in)。为方便起见，A[i]和B[i]也用来作为各车间的名字。虽然我们可以选择A[i]或B[i]来完成第i步装配工作，但是切换到另一条线需要运输时间，而在同一条线上则不需要运输时间。假设从车间A[i]转到车间B[i+1]的时间是TA[i]，而从车间B[i]转到车间A[i+1]的时间是TB[i]。另外，从入口到A[1]车间需要时间A[0]，从入口到B[1]车间需要时间B[0]，从车间A[n]到出口需要时间A[n+1]，从车间B[n]到出口需要时间B[n+1]。现在我们希望找到一条最优的装配流程使一部汽车从入口开始到出口为止的时间最短。这里，装配流程是指完成这n步装配工作的车间序列。请用动态规划设计一个O(n)算法来找到这个最优流程。解：这个问题可以用一个多级图来描述。图中起点S代表入口，终点T代表出口。两点之间有n级顶点集合，V1，V2，…，Vn，其中Vi(1in)含两顶点，分别代表A[i]和B[i]。从S到A[1]的边有权A[0]，从S到B[1]的边有权B[0]，从A[n]到T的边有权A[n+1]，从B[n]到T的边有权B[n+1]。另外，从Vi(1in-1)的顶点到Vi+1的顶点有4条边。它们是，边(A[i],A[i+1])有权值0，边(B[i],B[i+1])有权值0，边(A[i],B[i+1])有权值TA[i]，边(B[i],A[i+1])有权值TB[i]。另外代表A[i]的顶点有权值A[i]，代表B[i]的顶点有权值B[i](1in)。S和T权值为0。下面的图给出了一个n=6的例子。显然，最优流程对应着一条从S到T的最短路径。与书中6.5节中多级图不同的是，这里的路径长度包括顶点的权值。图中粗线标出该例子的解。另外，我们定义从入口到每个车间完成的最佳流程为一个子问题。图中每个子问题的解标在顶点边上。我们定义子问题的解如下：DA[i]=从S到完成A[i]的最短时间，DB[i]=从S到完成B[i]的最短时间，(1in)。那么我们有以下归纳公式：DA[1]=A[0]+A[1]， //初始解DB[1]=B[0]+B[1] //初始解DA[i]=min{DA[i-1]+A[i]，DB[i-1]+TB[i-1]+A[i]} (2in)DB[i]=min{DB[i-1]+B[i]，DA[i-1]+TA[i-1]+B[i]} (2in)。当算出DA[n]和DB[n]后，最佳解的值为D=min{DA[n]+A[n+1]，DB[n]+B[n+1]}。下面是伪码。Shortest-Schedule(A[0..n+1,B[0..n+1],TA[1..n-1],TB[1..n-1])DA[1]A[0]+A[1]DB[1]B[0]+B[1]fori¬2ton ifDA[i-1]+A[i]DB[i-1]+TB[i-1]+A[i] then DA[i]DA[i-1]+A[i] PA[i]A[i-1] //父亲指针 else DA[i]DB[i-1]+TB[i-1]+A[i] PA[i]B[i-1] endif ifDB[i-1]+B[i]DA[i-1]+TA[i-1]+B[i] then DB[i]DB[i-1]+B[i] PB[i]B[i-1] else DB[i]DA[i-1]+TA[i-1]+B[i] PB[i]A[i-1] endifendforifDA[n]+A[n+1]DB[n]+B[n+1] then D¬DA[n]+A[n+1] P¬A[n] else D¬DB[n]+B[n+1] P¬B[n]endifS //准备输出路径，堆栈S清空Push(S,P) fork¬ndownto2 ifP=A[k] thenP¬PA[k] elseP¬PB[k] endif Push(S,P)endforfork¬1ton Pop(S) //按顺序输出经过的车间endforEnd因为算法中每一个循环中的每一步只需要O(1)时间，而每一个循环变量最多有n个不同值，所以算法有O(n)的复杂度。假设我们有一个n个数的序列，A[1],A[2],…,A[n]，通过n-1次对两个相邻的数做减法后，序列变成一个数。例如，序列4,5,3,9中有4个数字。如果我们在5和3之间做减法，因为5-3=2，序列变为4,2,9。如果再取4和2做减法，得到序列2,9。最后，在2和9之间做减法，得到一个数-7。和矩阵连乘问题类似，这个过程可以用一个二叉树表示，树中每个内结点代表一个减法操作。例如，上面的例子可以用下面图(a)中的二叉树表示。让我们把这样一棵树称为减法归约树，而每一次减法操作称为一次减法归约。显然，我们可以有许多减法归约树，但我们希望找到一棵最佳减法归约树使最后的数字最大。不难看出下面图(b)中的二叉树就是上面例子的最佳减法归约树，它产生的最后数字是11，是最大可能的结果。5(5(a)序列4,5,3,9的一棵减法归约树(b)序列4,5,3,9的一棵最佳减法归约树94322-79453211-7请设计一个动态规划的算法为序列A[1..n]找出一棵最佳减法归约树，并分析你的算法的复杂度。应用你的算法算出序列5,-3,7,2,-1的一棵最佳减法归约树。你需要显示每一步的细节。解：(a) 我们把计算子序列A[i],A[i+1],…,A[j](1ijn)的最佳减法归约树定义为一个子问题。我们定义L(i,j)为子序列A[i],A[i+1],…,A[j]的最佳减法归约树能产生的最大值。当i=j时，L(i,i)=A[i]。为了得到最佳减法归约树，我们需要考虑一个对称的问题，即找到一个减法归约树使得最后的数值最小。让我们称题中的最佳减法归约树为最大归约树，而对称问题中的最佳减法归约树为最小归约树。让我们定义S(i,j)是子序列A[i],A[i+1],…,A[j](1ijn)的最小归约树能产生的最小值。当i=j时，S(i,i)=A[i]。我们得到下面的归纳公式：L(i,j)=maxi≤k≤j-1{Li,k-S(k+1,j)}S(i,j)=mini≤h≤j-1{S(i,h)-L(h+1,j)L(i,i)=S(i,i)=A[i]。另外，我们用K(i,j)和H(i,j)分别记彔L(i,j)和S(i,j)中的k值和h值。下面是伪码。Max-Min-trees(A[1..n])fori=1ton L(i,i)S(i,i)A[i] //初始化endforforl1ton-1 //子问题的规模，l=j–i。 fori1to(n–l) j(i+l) L(i,j)- S(i,j)+ forkitoj-1 ifL(i,k)-S(k+1,j)>L(i,j) then L(i,j)L(i,k)-S(k+1,j) K(i,j)k endif endfor forhitoj-1 ifS(i,h)-L(h+1,j)<S(i,j) then S(i,j)S(i,h)-L(h+1,j) H(i,j)h endif endfor endforendforreturnL,S,K,Hend这个算法的复杂度显然是O(n3)。下面是由表K和H构造最大和最小归约树的递归算法。Max-Redude-Tree(L,S,K,H,i,j)ifi=j thenconstructasinglenodepwithvalueA[i] else constructrootnodepwithvalueofL[i,j] //根结点 kK[i,j] left(p)Max-Redude-Tree(L,S,K,H,i,k) //左子树 right(p)Min-Redude-Tree(L,S,K,H,k+1,j) //右子树endifreturnpEndMin-Redude-Tree(L,S,K,H,i,j)ifi=j thenconstructasinglenodepwithvalueA[i] else constructrootnodepwithvalueofS[i,j] //根结点 hS[i,j] left(p)Min-Redude-Tree(L,S,K,H,i,h) //左子树 right(p)Max-Redude-Tree(L,S,K,H,h+1,j) //右子树endifreturnpEnd(b)序列5,-3,7,2,-1的最大归约树的运算L(i,j)12345S(i,j)123451581517181581-1-22-3-10-8-72-3-10-12-13375637544234235-15-1K(i,j)12345H(i,j)12345111111123322222233334333444455最大归约树如下：335-37-1018-132-1*假设我们有n个活动要申请使用大礼堂:S={a1,a2,…,an}。礼堂从时间t=0起可以安排。活动ai(1i£n)需要连续使用的时间是ti并且在时刻di前结束，这里有0<ti£di<¥。也就是说它必须被安排在时刻di-ti前开始，否则不可能按时完成。因为在任何时刻，两个活动不能同时使用礼堂，所以我们只能满足一部分活动，但我们希望能满足尽量多的活动。请用动态规划设计一个O(n2)算法选出集合S中最大的一个活动子集并做出它们可以不冲突地使用大礼堂的调度，也就是给出每一个被选中活动开始的时刻。(提示：先把集合S中活动按他们的结束时间di(1i£n)排序。可假定d1£d2£…£dn。然后，定义子集Si={a1,a2,…,ai}(1£i£n)。按照动态规划的原理，先考虑S1，再考虑S2，…，最后考虑Sn。为子集Si定义以下子问题：能否找出j个不冲突的活动？如果能，最早什么时刻可完成？我们定义M(i,j)为安排集合Si中j(1£j£n)个不冲突活动所需的最短时间。如果集合Si中不可能找出这j个活动，则置M(i,j)=¥。假设我们已算出M(i,j)(1£i£k-1,1£j£n)，我们该怎样算M(k,j)(1£j£n)?)请用上面的算法找出下面7个话动的最优解。A[i]1234567T[i]442.54.5635D[i]587.511.5141215

解：不妨假定d1£d2£…£dn。我们称之为时限序列。如下图所示，在一个不冲突的活动调度中，如果aj安排在ai紧后面但是有di>dj，那么把它们交换一下后的调度仍正确。由此可假设，一组不冲突的活动可以从t=0开始，按照时限序列顺序安排，并且，相邻两个活动之间没有时间的间隔。让我们定义子集Si={a1,a2,…,ai}(1£i£n)。再定义它的子问题：能否找出j(1£j£n)个不冲突的活动？如果能，最早什么时刻可完成？我们定义以下二维函数：M(i,j)=不冲突地安排集合Si中j个活动所须的最短时间(1£j£n)。如果不可能，例如，j>i，则置M(i,j)=¥。初始解为M(i,0)=0(1£i£n)，M(0,j)=¥(1£j£n)。 假设我们已算好M(i,j)(0£i£k-1,1£j£n)，下面要算M(k,j)(1£j£n)。我们需要找到递归公式，分析如下。 因为Sk=Sk-1{ak}，而M(k,j)是安排Sk中j个活动所需时间，那么我们有两种方法安排这j个活动：把ak选上。那么，必须从Sk-1中选出j-1个活动并满足条件M(k-1,j-1)+tk£dk。不选ak。那么，必须从Sk-1中选出j个活动。如果是第一种情况，M(k,j)=M(k-1,j-1)+tk。如果是第二种情况，M(k,j)=M(k-1,j)。M(k,j)应该是两种情况中小的那个。所以，我们有以下归纳公式：M(k,j)=min{M(k-1,j),M(k-1,j-1)+tk} 如果M(k-1,j-1)+tk£dk，否则M(k,j)=M(k-1,j)。算完M表之后，找出最大的j使M(n,j)¹¥。那么，我们最多可以安排j个活动。下面是伪码，其中变量U[k,j]=1用来表示是第一种情况(即ak在计算M(k,j)时被选中)，U[k,j]=0是第二种情况。Schedule-Activities(A[1..n],T[1..n],D[1..n],M,U)fori¬0ton M(i,0)¬0 //初始解一部分endforforj¬1ton M(0,j)¬¥ //初始解另一部分endforfork¬1ton forj¬1ton ifM(k-1,j-1)+T[k]£D[k] thent¬M(k-1,j-1)+T[k] elset¬¥ endif ift<M(k-1,j) then M(k,j)¬t U(k,j)¬1 //第1种情况，A[k]被选入M(k,j) else M(k,j)¬M(k-1,j) U(k,j)¬0 endif endforendforj¬1 //找最大的j使M[n,j]非无穷大whileM(n,j)¹¥andj£n //一旦M(n,j)=¥，那么M(n,j+1)更是¥ j¬j+1endwhilej¬j–1 //最优解有j个活动t¬M(n,j) k¬n //从A[n]开始，输出这j个活动whilej>0 ifU(k,j)=1 then scheduleA[k]from(t–T[k])tot //安排A[k]在最后面，到t为止 t¬(t–T[k]) j¬j–1 //还有j-1个活动需安排 endif k¬k–1 //下面考虑Sk-1和M(k-1,j)，如果U(k,j)=1，则j已更新为j-1endwhileEnd算法的复杂度显然是O(n2)。用上面的算法找出下面7个话动的最优解。A[i]1234567T[i]442.54.5635D[i]587.511.5141215按结束时间排序后得到：A[i]1234567T[i]42.544.5365D[i]57.5811.5121415表M和表U计算如下(两表合一)M(i,j)/U(i,j)01234567原序号00¥¥¥¥¥¥¥104/1¥¥¥¥¥¥302.5/16.5/1¥¥¥¥¥202.5/06.5/0¥¥¥¥¥402.5/06.5/011/1¥¥¥¥602.5/05.5/19.5/1¥¥¥¥502.5/05.5/09.5/0¥¥¥¥702.5/05.5/09.5/014.5/1¥¥¥被调度的活动是A[1]，A[3]，A[6]，A[7](原序号)。表中阴影部分显示的是从最右边非无穷大M(n,j)开始往回找出j个活动的路线。实际调度如下图。假设你有n尺的一卷布要卖。你可以整卷卖，也可以裁为几段卖，但每段必须是整数尺。假定从1尺长到n尺长的各种长度的价格都已定好为P[i](1£i£n)。现在希望找到一个裁剪方案使总的卖价最大。例如，下面表格显示从1尺到6尺的价格(n=6)，那么，如果把这6尺布裁为2尺和4尺两段，则可卖出4+7=11元。如果裁为3段，每段2尺，则可卖出34=12元，而不裁整卖却只值9元。长i(尺)123456价格pi(元)144789请用动态规划设计一算法来计算如何裁开(或不裁开)这n尺布使得总的卖价最大。请给出伪碼和它的复杂度。解: 设一段有i尺长的布裁开或不裁开所能得到的最大卖价为R[i]。当i=n时，R[n]即是答案。我们用动态规划方法求R[i]。以下是归纳公式：R[1]=P[1] (初始解，i=1)。R[i]=max{max1≤k≤i-1Rk+Ri-k,P 因为裁为两段长为a和b也就是b和a，所以归纳公式可改进为：R[1]=P[1] (初始解，i=1)。R[i]=max{max1≤k≤i/2Rk+Ri-k我们用C[i]表示第一刀应从那里剪开。根据这个公式，题目中例子的解如下，其中nil表示不裁开卖为最佳：i123456R[i](元)1458912C[i](尺)nilnil1212伪码如下。Cloth-Cutting(P,n)R[1]¬P[1]fori¬2ton q¬P[i] //整卖i尺布的价钱 C[i]¬nil fork¬1toëi/2û ifq<R[k]+R[i-k] then q¬R[k]+R[i-k] C[i]¬k endif endforendforreturnR,CEnd 该算法复杂度显然是O(n2)。假设有n个硬币排成一个序列V[1..n]，其币值依次为V[1]，V[2]，…，V[n]。两个玩游戏的人轮流从序列中取走一个硬币，但每次只能取序列头尾两端的硬币之一，而不能从序列中间取。假设你和对手玩这个游戏，而且你走第一步。用动态规划设计一个O(n2)算法使你在最坏情况下能取走硬币的总币值最大。这里，最坏情况是指对手和你一样聪明。请给出归纳公式和初始解，不要求伪码。用你上面(a)部分算法对序列V[1..5]=<5,2,8,3,6>进行运算，显示每步结果。解：(a)定义M(i,j)=走第一步的人在最坏情况下能从子序列V[i..j]中取走硬币的最大总币值。定义W(i,j)=k=ijV[k]，即子序列V[i..jM(i,i)=V[i]， (初始解，i=1,2,…,n)M(i,j)=W(i,j)–min{W(i+1,j),W(i,j-1)} 如果i<j。这是因为，你只有两种选择，取子序列中第一个硬币或最后一个。如果你取走第一个硬币，对手面临子序列V[i+1..j]，否则对手面临子序列V[i..j-1]。因为最坏情况下，对手会分别取走总币值W(i+1,j)或W(i,j-1)，因此，让对手取走其中小者是最好的结果。所以，在最坏情况下，走第一步的人最多可得M(i,j)=W(i,j)–min{W(i+1,j),W(i,j-1)}。我们用K(i,j)记录第一步的人取的是头还是尾，所以有：如果W(i+1,j)≤W(i,j-1),那么K(i,j)=i，否则K(i,j)=j。算法显然有O(n2)复杂度。(b)用上面(a)部分算法对序列V[1..5]=<5,2,8,3,6>进行运算。W(i,j)12345M(i,j)1234515715182415510131122101319228514381117388114394365656K(i,j)12345113152345333455下面的二叉树描述了这个解中二人取硬币的过程。从这个例子中可见，先走第一步的人不一定比后走的拿到更大总币值。242418261351038第3步取走V[4]=3第5步取走V[2]=2第2步取走V[1]=5第1步取走V[5]=6开始总价值=W(1,5)W(2,4)W(1,4)W(2,3)第4步取走V[3]=8重新做18题，但不同的是，这次我们考虑最好情况，即假设对手很苯，每次都走错，而且你仍然走第一步。解：(a)定义M(i,j)=走第一步的人在最好情况下能从子序列V[i..j]中取走硬币的最大总币值。归纳公式为：M(i,i)=V[i]， (初始解一部分，j=i=1,2,…,n)M(i,i+1)=max{V[i]，V[i+1]} (初始解另一部分，j=i+1，i=1,2,…,n-1)M(i,j)=max{M(i+2,j)+V[i],M(i+1,j-1)+V[i],M(i+1,j-1)+V[j],M(i,j-2)+V[j]} 如果j>i+1。这是因为，你能得到最好的结果的前提是，对手在下一步得到最差的结果。所以，算法在每一步确定两个硬币，一个是你拿的，另一个是给对手拿的。我们用K(i,j)记录第1步你取的是头还是尾，而用U(i,j)记录对手在第2步应该取的硬币。具体操作如下：如果M(i,j)=M(i+2,j)+V[i]，则K(i,j)=i，U(i,j)=i+1;如果M(i,j)=M(i+1,j-1)+V[i]，则K(i,j)=i，U(i,j)=j;如果M(i,j)=M(i+1,j-1)+V[j]，则K(i,j)=j，U(i,j)=i;如果M(i,j)=M(i,j-2)+V[j]，则K(i,j)=j，U(i,j)=j-1。算法显然有O(n2)复杂度。(b)用上面(a)部分算法对序列5,2,8,3,6进行运算。M(i,j)1234515513131922811143881443656K(i,j)12345U(i,j)12345113151222423452222333344454455下面的二叉树描述了这个解中二人取硬币的过程。151550第3步你取走V[1]=5，对手无硬币可取。第1步你取走V[5]=6，对手取V[4]=3开始时总价值W(1,5)W(1,3)246+38+25W(1,1)第2步你取走V[3]=8，对手取V[2]=3有n个硬币排成一列，分别有币值c1,c2,...,cn。这些币值也许有相同的，但都是正数。设计一个O(n)的算法选取出一组不相邻的硬币使得总币值最大。不相邻的意思是，选出的硬币在原序列中不相邻。你只需定义子问题的集合和设计归纳公式。不要求伪码。用上面(a)部分的算法为下面的币值序列选取一组不相邻的硬币使得总币值最大。要求显示每一步的结果。<c1,c2,c3,c4,c5,c6,c7,c8>=<4,14,7,3,13,5,9,7>。解： (a) 我们定义子集Ci={c1,c2,...,ci}(1in)。对应于Ci的子问题是，从Ci中选取出一组不相邻的硬币使得总币值最大。我们定义：F(i)=Ci中一组不相邻的硬币可能有的最大总币值。我们有如下归纳公式：F(0)=0,F(1)=c1 (初始解) F(i)=max{ci+F(k-2),F(k-1)} 如果i≥2。 用上面(a)部分的算法于下面的币值序列。<c1,c2,c3,c4,c5,c6,c7,c8>=<4,14,7,3,13,5,9,7>每步的结果显示于下面的表中。序号i012345678C(i)4147313597F(i)0414141727273636选择+F(0)+F(0)F(2)+F(2)+F(3)F(5)+F(5)F(7)表中，如果第i列的选择是+F(k)，则表示F(i)选中硬币C(i)，再加上F(k)。如果第i列的选择是F(k)，则表示解F(i)不选硬币C(i)，F(i)=F(k)。上面例子的解是：C(7),C(5),C(2)，总价值是36。两个人的游戏中有两摞硬币。其中一摞有n个，从下向上分别有币值A[1],A[2],…,A[n]，存于数组A[1..n]。另一摞有m个，从下向上分别有币值B[1],B[2],…,B[m]，存于数组B[1..m]。假设币值都是正数。两个游戏者轮流从这两摞硬币中每次取走一枚硬币直到取完。规定每次只能取两摞中其中一摞的最上面的一枚硬币，不允许不取或从中间取。游戏前，所有币值都已知。用动态规划设计一个O(mn)算法以求出第一个取硬币的人在最坏情况时能得到的最大总币值。最坏情况是指对方和你一样聪明，每次都能正确地取走硬币使他的总币值最大化。你需要给出归纳公式和初始条件。伪码可略去。用(a)中的算法对以下两个币值序列求出第一个玩游戏的人在最坏情况时能得到的最大总币值。A[1..6]=<4,12,6,10,3,8>,B[1..5]=<13,9,1,5,7>。解：(a)定义子序列A[1..i]和B[1..j](1in,1jm)。那么对应的子问题是，给定两摞硬币，A[1..i]和B[1..j]，求出第一个取硬币的人在最坏情况时能得到的最大总币值。我们定义M(i,j)为这个最大总币值。再定义：W(0,j)=k=1jB[k]，W(i,0)=k=1iAk，W(i,j)=W(0,j)+我们有以下初始解：M(0,0)=0 (初始解，i=0和j=0)。归纳公式如下，我们用K(i,j)来记录应当取走的硬币：M(0,j)=W(0,j)–M(0,j-1)，K(i,j)=B[j] (i=0和j>0)，M(i,0)=W(i,0)–M(i-1,0)，K(i,j)=A[i] (i>0和j=0)，M(i,j)=W(i,j)–min{M(i-1,j),M(i,j-1)} 如果i>0和j>0。如果M(i-1,j)≤M(i,j-1)，则有K(i,j)=A[i]，否则K(i,j)=B[j]。用(a)中的算法求解以下两序列：A[1..6]=<4,12,6,10,3,8>,B[1..5]=<13,9,1,5,7>。W(i,j)01234500132223283514172627323921629383944513223544455057432455455606753548575863706435665667178fM(i,j)012345K012345001391414210-BBBBB1413171319201ABAABB21217212625312ABAAAA31025232228293ABABBB42223313332384ABAAAA51335263231395ABABAB63026393440396ABAAAA 取币序号 1234567891011总值游戏者1A[6]8A[5]3B[4]5A[3]6A[1]4B[1]1339游戏者2B[5]7A[4]10B[3]1A[2]12B[2]939一块宽为L的长方形电路板的上边有m个端口，它们与电路板左端的距离分别为U[1],U[2],…,U[m]。电路板的下边有n个端口，它们与电路板左端的距离分别为L[1],L[2],…,L[n],n<m。现在需要在上面的m个端口中选出n个端口，分别与下边的n个端口用导线连接，并要求这n条导线的总长最小。下图给出了一个m=8，n=4的示意图。证明在一个最佳解中，任意两个连线不会相交。为上述问题设计一个O(mn)的动态规划的算法。解:我们用反证法证明。我们用(i,j)和d(i,j)分别表示点U[i]和L[j]之间的线段及其距离。假设在一个最佳解中，有两个线段，(i,j)和(u,v)相交。那么，如下图(b)所示，U[i]、U[u]、L[j]、L[v]四点形成一个四边形。其两对角线长度之和大于其对边长之和，故有d(i,j)+d(u,v)>d(i,v)+d(u,j)。这就是说，把这两线段换为(i,v)和(u,j)后，可得到一个更好的解，与最佳解矛盾。我们考虑如下子问题：假设上边的可用端口为U[1],U[2],…,U[i](im)。而下边需要连接的端口是L[1],L[2],…,L[j](jn,ji)。现在需要在上面的i个端口中选出j个端口，分别与下边的j个端口用导线连接，并要求这j条导线的总长最小。显然，当i=m，j=n时，该子问题就是原问题。我们定义d(i,j)=Ui-L[j]2+L2为点U[i]和L[j]之间的距离，定义这个子问题的最佳解的j条导线的总长是MMM(i,0)=0 (初始解，i=0,1,…,m)。如果M(i,j)=M(i-1,j)，记K(i,j)=F，否则，记K(i,j)=T。伪码如下：Segment-Selection(U[1..m],L[1..n],M,K)fori0tom M(i,0)0endif //初始解forj1ton fori1toj-1 M(i,j) endfor forijtom ifM(i-1,j)d(i,j)+M(i-1,j-1), then M(i,j)M(i-1,j) K(i,j)=F else M(i,j)M(i-1,j-1)+d(i,j) K(i,j)=T endif endforendforimforjndownto1 //输出结果 whileK(i,j)=F ii-1 endwhile outputpair(i,j) //连結U[i]和L[j] ii–1endforEnd //M(m,n)是总长显然这是一个O(mn)算法。假设在一个n