动规基础多阶段决策过程是指这样一类特殊的活动可以按时间

初识动态规划算（mulispcisonrocss）是指（nmicrorming）并答案保起来让后再次到时直答案必重新解动规划算将问题的决策；而动态规划法中，还要每个最优决序列中是包含一个优决策子序1、最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。2、子问题性质。子问题性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问12341～3步是动态规划算法解决问题的基本步骤，在只需要计算最优值的问题中，完成这三个基本步骤就可以了。如果问题需要构造最优解，还要执行第4步；此时，在第3步通常需要记录的信息，以便在步骤4中，有足够的信息快速地构造出最优解。例：（问题来源：1999年青少年信息学（计算机）分区联赛高中组复赛试题的第一发弹能够到达任意的高度，但是以后每一发弹都不能高于前一发的高度。某天，捕捉到敌国的来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能所有的。输入依次飞来的高度（给出的高度数据是不大于30000的正整数），计算这套系统最多能拦3892071553002991701586（最多能的数389300299170158分析：因为只有一套 系统，并且这套系统除了第一发弹能到达任意高度外，以后的每一发弹都不能高于前一发弹的高度；所以，被的应该按飞来的高度组成一个非递增序列。题目要求我们计算这套系统最多能的数，并依次输出被的高度，实际上就是要求我们在设X={x1,x2,…,xn}为依次飞来的序列，Y={y1,y2,…,yk}为问题的最优解（即X为s=∞——第一发弹能够到达任意的高度）。如果y1=x1，即飞来的第一枚被成功。那么，根据题意“每一发弹都不能高于前一发的高度”，问题的状态将由s=∞变成s≤x1（x1为第一枚的高度）；在当前状态下，序列Y1={y2,…,yk}也应该是序列X1={x2,…,xn的最长非递增子序列（大家用反证法很容易证明）s≤x1下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的。这就是问题的最优子设D(i)为第i枚被之后，这套系统最多还能的数（包含被的第i枚）。我们可以设想，当系统了第k枚xk，而xk又是序列X={x1,x2,…,xn}中的最小值，即第k枚为所有飞来的中高度最低的，则有D(k)=1；当系统了最后一枚xn，那么，系统最多也只能这一枚了，即D(n)=1；其它情况下，也应该有D(i)≥1。根据以上分假设系统最多能的数为dmax（即问题的最优值）， （i为被系统的第一枚的顺序号mxD(1)、D(2)(n)D(i)i从1到nD(1)D(2)Dn)(1)D5)D2)、D(3)、D(4)D(5)D()D(n)=1。如果将n作为阶段对问题进行划分，根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出D(n-1)、D(n-2)、……D(1)的值。这样，每个D(i)的值只计算一次，并在计算的同时把计算结果保存下来，从而避免了有些子问题被重fori=1tonnextfori=n-1to1step-1forj=i+1tonifx(j)<=x(i)andD(i)<D(j)+1thennextjnextremdmax用来保存问题的最优值（系统最多能的数）；xh用来保存第一枚被的fori=1toifD(i)>dmaxthennextprintfori=xh+1toifx(i)<=x(i-1)thenprintx(i)next从实践中动态规划算法的精髓，不断提高自己的应用能力。第3章动态规划例3-1[最短路经]图12-2中的有向图。假设要寻找一条从源节点s=1到目的节点d=5的()()1，3，4，59)vv是怎样确定的，此后vd的路径时，都必须采用最优策略。例3-2[0/1背包问题]13.4节的0/1背包问题。如前所述，在该问题中需要决定x1..xni=1，2，.，nxix1=0，则问题转变为相对于其余物品（2，3，.，n）cx1=1，问题就变为关于最大背包容c-w1rÎ{c，c-w1}为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为rx101，[x2，.，xn必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn，因而[x1，y2，.，yn]是一个更好的方案。n=3,w=[100,14,10],p=[20,18,15],c116x11，则在本次决策之后，可用的背包容量为r=116-100=16。[x2，x3]=[0,1]15，但因为[x2，x31，0]18，因此[x2，x30，1]并非最优策略。x=1，0，1]可改进为x=1，1，0x10，则对于剩下的两种物品而言，容量限制116。总之，如果子问题的结果[x2，x3]不是剩余情况下的一个最优解，则[x1，x2，x3]3-3航费]某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$10；从芝加哥到纽约票价$20；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$20。特兰大直飞纽约，票价$100。而使用直飞方式时，从洛杉矶到纽约的花费为$200。不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$140（在处理局部最优路径如果用三维数组（tag，起点，终点）tag0表示转飞，tag1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（0，亚特兰大，纽约），它对应的最优路当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（dynamicprogrammingrecurrenceequation），它可以帮助我们高效地解决问题。3-4[0/1背包]3-20/1背包问题中，最优决策序列由最优决策子序列组成。假设f(i,y)152yi，i1，.，n时的最优解的值，即：和利用最优序列由最优子序列构成的结论，可得到f的递归式。f(1,c)是初始时背包问题的最优解。可使用（152）式通过递归或迭代来求解f1,c)。从f(n,*)fn,*由（151）式得出，然后由（15-2）f(i,*)(i=n-1，n-2，.，2)，最后由（15-2）式得出f(1,c)。1520≤y＜10，则f3,y)0y≥10，f3,y)15。利用递归式（152），可得f(2,y)=0(0≤y＜10)；f（2，y）=15（10≤y＜14）；f（2，y）=18（14≤y＜24）和f（2，y）33（y≥24）f1116maxf（2，11（2，116-w1）+p1}=max{f（2，116），f（2，16）+20}=max{33，38=38xi值，步骤如下：若f1c)=f2,c)x10x11。接下来需从剩余容量c-w1中寻求最优解，用f(2,c-w1)xi(i=1.n)值。在该例中，可得出f211633≠f1116)x1138p1=18x2x3r116w116f21618，得f31614≠f216)x21r=16w22f(3,2)=0，即得x30动态规划方法采用最优原则（principleofoptimality）来建立用于计算最优解的递归式。所谓最优不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯（traceback）以构造最优解。34中已建立了背包问题的动态规划递归方程，求解递归式（152）的一个很自然的方法便15-1p、wnp为整型，F(1,c)f(1,c)15-1intF(inti,int{//返回f(iyif(i==n)return(y<w[n])?0:if(y<w[i])returnreturnmax(F(i+1,y),F(i+1,y-w[i])+}151tn)满足：t1a；t（n）≤2t（n1）+b（n＞1），a、b为t(n)=O(2n)。3-5设n5，p63546，w=[2,2,6,5,4]c=10,f110f110)F110151yji=jF110，而它有左孩子和右孩子，分别对F(2,10)F2,8)28次递归调用。但我们注意到，其中可能含有重复前面f38)f48、f46、f42、f58、f56、f53、f(5,2)和f511935151做了一些不必要的工作。为了避免f(i,y)的重复计算，必须f(i,y)值的表格L，该表格的元素是三元组(i,y,f(i,y))。在计算每一f(i,y)之前，应检查表L中是否已包含一个三元组(i,y,*)，其中*表示任意值。如果已包含，则从该表中取出f(i,y)的值，否则，对f(i,y)进行计算并将计算所得的三元组(i,y,f(i,y))加入表L。L既可以用散列（见7.4节）的形式，也可用二叉搜索树(见11章)的形式。当权为整数时，可设计一个相当简单的算法（152）f1,c)34所给出的策略，因此每个f(i,y)15-2用二维数组f[][]来保存各f的值。而Traceback152xi值。函数Knapsack的复杂性为(nc）Traceback的复杂性为(n)。15-2fxtemvoidKnapsack(Tp[],intw[],intc,intn,T**{//iyfiy//初始化fnfor(inty=0;y<=yMax;y++)f[n][y]=0;for(inty=w[n];y<=c;y++)f[n][y]=p[n];//for(inti=n-1;i>1;i--){for(inty=0;y<=yMax;y++)f[i][y]=f[i+1][y];for(inty=w[i];y<=c;f[i][y]=max(f[i+1][y],f[i+1][y-w[i]]+}f[1][c]=if(c>=f[1][c]=max(f[1][c],f[2][c-w[1]]+}temvoidTraceback(T**f,intw[],intc,intn,int{//for(inti=1;i<n;if(f[i][c]==f[i+1][c])x[i]=0;else{x[i]=1;c-=x[n]=(f[n][c])?1:}元组方法（152有两个缺点：1)要求权为整数；2)c15215-1c＞2n15-2的复杂性为W(n2n)。可利用元组的方法来克服i，f(i,y)都以数对(y,f(i,y))y的递增次序存P(i)f(i,y)y的非递减函数，因此P(i)中各数对(y,f(i,y))f(i,y)的递增次序排列的。3-635。对f152i=5时，fP50046)]表示。而P4、P3)P2分别为0046910)]0,04,69101011)]和0,02,34669901011f(1,10)，利用式（15-2）得f(1,10)=max｛f(2,10)，f(2,8)+p1｝。由P2)f21011、f(2,8)=9f289来自数对6，9，因此f1,10max｛1115｝15xi的值，因为f(110f(26p1x11f26=f36w2p2f34p2x21；由f34f(4,4)=f(5,4)x3=x4=0f(5,4)≠0x5=1。检查每个P(i)中的数对，可以发现每对(y,f(i,y))xi,.,xn0/1赋值的不同组合。设（a,b）和（c,d）xixn01a≥cb＜d，则(a,b)受(b,c)支配。被支配者不必加入P(i)中。若在相同的数对中有两个或的赋值，则只有一个放入P(i)。假wn≤C，P(n)=[(0,0),(wnpn，P（n）xn01。对于每个i，P(i)P(i+1)Qwi≤s≤c且(s-wi,t-pi)P(i+1)中的一个数对时，（s,t）Q中的一个数对。现在Qxi=1时的数对集，而P(i+1)xi=0的数对集。接下来，合并Q和P(i+1)P(i)。3-7156。P(5)=[(0,0),(4,6)],Q54910P5)Q合并得到P4。因54)受46支配，可删除(54(4,6),(9,10)]P3，首先由P4得Q=[(6,5),10,11P(3)=[(0,0),(4,6),(9,10),(10,11P2：由P3Q23，(69，P3Q合并得P(2)=[(0,0),(2,3),(4,6),(6,9),(9,1010,11。因为每个xi,.,xn0/1赋值，因此P(i)2n-i+1个。计算P(i)时，计算Q需消耗(|P(i+1)|）P(i+1)和Q同样需要(|P(i+1)|)的时间。计算P(i)(nåi=2|P(i1)|=O2n。当权为整数时，|P(i|≤c+1,此时复杂性为O(min{nc,2n})。6.4.3m×m0~255的灰度值。因此一个像素至多需8位。若每个像素都用最大位8位，则总的空间为8m2位。为了减少空间，采用变长模式（variablebitscheme），即不同像素用不同位数来存储。像素值为0和1时只需1位空间；值2、3各需2位；值4，5，6和7各需3位；以此类15-3a中的折线将m×m1×m2256256创建文件创建三个文件：SegmentLength,BitsPerPixel和Pixels。第一个文件包2中所建的段的长度(18BitsPerPixel给出了各段中每个像素的位数（减1），文件中各项均为3位。文件Pixels则是以变长格式的像素的二进制串。3)例3-8图15-3b的4×4图像。按照蛇形的行主次序，灰度值依次为10，9，12，40，50，35，15，12，8，10，9，15，11，130，1602404，10，9，12、[40，50，35、[15,12,8,10,9,15,11]和［130,160,240］SegmentLength2，2，6，2；文件BitsPerSegment3，5，3，7Pixels包含了按蛇形行主次序排列的16个灰度值，其中头三个各用4位，接下来三个各用6位，再接下来的七个各用4位，最后三个各用8位。因此单元中前30位了前六个像101010011100111000110010这三个文件需要的空间分别为：文件SegmentLength需32位；BitsPerSegment需1位；Pixels需82位，共需126位。而如果每个像素都用8位，则空间需8×16=1假设在2)之后，产生了n个段。段标题（segmentheader）用于段的长度以及该段中每个像11li和bii段的段长和该段每个像素的长度，则第i段像素所需要的空间为li*bi。在2)中所得的三个文件的总空间为11n+nåi=1libiii+1被合并时，合并后的段长应为li+li+1。此时每个像素的位数为max{bi，bi+1}位。尽管这种技术增加了文件Pixels的空间消耗，但同时也减少了一个段标题的空间。3-915812SegmentLength变为5，6，2，BitsPerSegment变为5，3，7。而文件Pixels的前36位的是合并后的第一段：001010001001001100111000110010100011其余的像素（1583段）1个段标题，文件SegmentLengthBitsPerPixel位，而文件Pixels65121我们希望能设计一种算法，使得在产生n个段之后，能对相邻段进行合并，以便产生一个具有最小空间需求的新的段集合。在合并相邻段之后，可利用诸如LZW法（见7.5节）和编码（见9.5.3节）等其他技术来进一步压缩这三个文件。sqqs00i段(i＞0Cii-1，i-2，.，i-r+1i-rC所需要的空间消耗等1i-r段所需空间+lsum(i-r+1,i)*bmax(i-r+1,i)+11lsum(ab)=båjlj，bmax(a,b)=max{ba,...,bb}。假如在C1i-r段的合并不是最优合并，那1i-r进行最优合并，也即保证最优原则得以维持。故C的空间消耗为：si=si-r+lsum（i-r+1,i）*bmax（i-r+1,i）+r1ilsum256256之内)。尽管我们不r，但我们知道，由于Cr必须产生最小的kayik的值，snnkay3-102)中得到五个段，它们的长度为6，3，10，2，3]，像素位数为1，2，3，2，1]，要用（15-3）计算sn，必须先求出sn-1，.，s0的值。s0为0，现计算=s0+l1*b11117kay11s2s2=min{s1+l2b2,s0+(l1+l2)*max{b1,b2}}+11=min{17+6,0+9*2}+11=29kay2=s1.s517，29，67，73，82]，kay1.kay51，2，2，3，4。因s5=8282kay5导出本合并的方式，过程如下：因为kay5=4，所以s5是由（15-3）在k=4时取得的，因而最优合并包括：段1到段(5-412，3，45125的合并用递归式（15-3）sikayi15-3为递归式的计算代码。l，bkay是一维的全局整型数组，L是段长限制（256），header为段标题所需的空间11。调用S(n)返回snkayTraceback(kay,n)可得到最优合并。153的复杂性。t0c（c为一个常数）：（n＞0）(nO2n。Traceback的复杂性为(n)。15-3s,kay及最优合并intS(intSi并计算kayiif(i==0)return0;//k=1时,根据（15-3）计算最小值intlsum=l[i],bmax=b[i];ints=S(i-1)+lsum*bmax;kay[i]=1;kfor(intk=2;k<=i&&lsum+l[i-k+1]<=L;k++){lsum+=l[i-k+1];if(bmax<b[i-k+1])bmax=b[i-k+1];intt=S(i-k);if(s>t+lsum*bmax){s=t+lsum*bmax;kay[i]=k;}}returns+}voidTraceback(intkay[],int{//if(n==0)Traceback(kay,n-cout<<"Newsegmentbeginsat"<<(n-kay[n]+1)<<}siS的复杂性减少到(n)n个不同的si例3-11再例15-10中五个段的例子。当计算s5时，先通过递归调用来计算s4，.，s0。s4s3，.，s0s4s3计算了两次，每一次计算s3s2s2s116s来保存先前si15-4，其中s0的全局整型数组。15-4intS(intSikayiif(i==0)returnif(s[i0returns[i//计算s[i//首先根据（15-3）计算k=1时最小intlsum=l[i],bmax=b[i];s[i]=S(i-1)+lsum*bmax;kay[i]=1;kfor(intk=2;k<=i&&lsum+l[i-k+1]<=L;k++){lsum+=l[i-k+1];if(bmax<b[i-k+1])bmax=b[i-k+1];intt=S(i-k);if(s[i]>t+lsum*bmax){s[i]=t+lsum*bmax;kay[i]=k;}}s[i]+=header;returns[i];}为了确定程序15-4的时间复杂性，使用分期计算模式（amortizationscheme）。在该模式中，总时间被分解为若干个不同项，通过计算各项的时间然后求和来获得总时间。当计算si时，若sjS(j)的消耗计入sj；若sjS(j)的消耗计入si(sj依次sq的消耗转移至每个sq)15-4的其他消耗也被计入si。因为L256之内的li1154的其他消耗为(1sisin，因而总工作量为(n)。倘若用式（153）s1sn，便可得到一个复杂性为(n)si计算之前，sj15-5Traceback（见15-3）来获得最优合并。15-5skavoidVbits(intl[],intb[],intn,ints[],int计算sikayi]intL256,header11s[0]=0;根据式（153）计算sifor(inti1;ini+k1时,计算最小值intlsum=l{i},bmax=b[i];s[i]=s[i-1]+lsum*bmax;kay[i]=1;kfor(intk=2;k<=i&&lsum+l[i-k+1]<=L;k++){lsum+=l[i-k+1];if(bmax<b[i-k+1])bmax=b[i-k+1];if(s[i]>s[i-k]+lsum*bmax){s[i]=s[i-k]+lsum*bmax;kay[i]=k;}}s[i]+=}}m×nAn×pB相乘需耗费(mnp)的时间（216）mnp作为两A、B和C的乘积，有两种方式计算此乘积。在第式中，先用A乘以B得到矩阵D，然后D乘以C得到最终结果，这种乘法的顺序可写为(A*B)*CA*(B*C),道理同上。尽管这两种不同的计算顺序所得的结果相同，但3-12A100×1矩阵，B1×100矩阵，C100×1A*B10000，得到的结果D100×100C1000000算(A*B*C1010000。B*C100001×1A100A*（B*C）10100（A*B）*C时，还需10000个单元来A*B，而A*（B*C）计算过程中，只需用1个单元B*C。要求是，确定一个图像需旋转、平移和缩放多少次才能近另一个图像。实现匹配的方法之一便是执行10012×1T：T=åA(x,y,z)*B(x,y,z)*C(x,y,zA，B和C12×3，3×33×1矩阵。(xy,z)tA(xy,z)*B(xy,z)*C(xy,z)256×256×256100100*2563*t≈17*109tt12*3*312*3*1=144；但如果从右向左相乘，t3*3*112*3*14524*101175*1010140125A*C（序所需要操作数并选择作数比少的那乘顺序。但于阵相乘说，情要复杂得多。如计算矩阵乘积M1M2Mq，其中Miriri+1()=4的***D（）计算：A*((B*C)*D)A*(B*(C*D))(A*B)*(C*D)(A*(B*C))qq来说，考虑每一种计算顺序并选择(q3。用MijMi×.×Mj（i≤j）c(i,j)Mij的消耗，kay(i,j)MijMik×Mk+1,jMij的最优算法包括如何用最优算法MikMkjMik×Mkj。根据最优原理，可得到如下的动态规划递归式：kay(i,i+s)=k.以上求c的递归式可用递归或迭代的方法来求解。c(1，q)为用最优法计算矩阵链的消耗，kay(1,q)kay值来确定。01c(i,j)kay(i,j)，否则算3-13q5r（105,110210），c中有四个cs=01此用动态规划方法可立即求得它们的值：c(11=c(550;c(1,2)=50;c(45200。现计算C(2，5：c(25min{c22c(3,5)+50,c(23c(24c(55100}（155）其中c(22c(550；c(230；c(4,5)=200。再用递归式计算c(35c24c(35min{c33+c(4,5)+100,c(3,4)+c(5,5)+20}=min{0+200+100,20+0+20=40c(2,4)=min{c(2,2)+c(3,4)+10,c(2,3)+c(4,4)+100}=mn0201050102030kay(354，kay(2,4)=2。现在,c(2,5)所需的所有中间值都已求得，将它们代入式（15-5）得：c(2,5)=min{0+40+50,50+200+500,30+0+100}=90kay(2,5)=2再用式（154）计算c(15c(35、c(1,3)和c(14。同上述过40、15090kay4、22。代入式（15-4）得：c(1,5)=min{0+90+500,50+40+100, 90+0+200}=190kay(15=190kay(1,5)kay(1,5)2，M12×M35M12M35kay(1,2)=1知M12M11×M22kay(3,5)=4M35M34×M55算出。依此类推，M34M33×M44得出。因而此最优乘法算法的步骤为：M11×M22=M1M33×M44=M3M34×M55=M3M12×M35=M1c(ij)kay(i,j)156。在函数C中，rkay是全局二维数组变量，函数C返回c(ij)kay[a][b]=kay(a,b)(a,b)c(ab)c(i,j)Traceback利用函数Ckay值来推t(q)Cq=j-i+1（Mijq个矩阵运算的结果）q12时，t(qddq2时，tq)=2q-1åk1t(k+eqe是一个常量。因q＞2时，t(q)＞2t(q-1)+et(q)=W(2q)Traceback的复杂性为(q)。15-6c(i,j)kay(i,j)intC(inti,int返回c(i,j)k(i,jkay[i][j]if(i==j)return0;//一个矩阵的情形if(ij-1)两个矩阵的情形kay[i][i+1]=i;return设ukiintu=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];kay[i][j]=i;for(intk=i+1;k<j;k++)inttC(i,k)C(k+1,jr[i]*r[k+1]*r[j+1];if(r<u){//小于最小值的情形u=t;kay[i][j]=k;}return}voidTraceback(inti,intj,int{//Mij的最优方法if(i==j)return;Traceback(i,kay[i][j],kay);Traceback(kay[i][j]+1,j,cout<<"MultiplyM"<<i<<","<<cout<<"andM"<<(kay[i][j]+1)<<","<<j<<}c（及相应的kay），可将复杂性降低到（q3）。而为了避免重复计算，需用一个全局数组c[][]c(i,j)值，该数组初始值为0。函数C的新代码见程序15-15-7c(i,j)intC(inti,int返回c(i,j)kayijkayIjif（c[i][j]>）return若未计算,if(i==j)return0;//一个矩阵的情形ifij1两个矩阵的情形c[i][j]=r[i]*r[i+1]*r[i+2];returnc[i][j];}设ukiintu=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];kay[i][j]=i;for(intk==i+1;k<J;K++){<intt=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];if(t<{>u=tkay[i][j]=k;}c[i][j]=u;returnu;}为分析改进后函数C的复杂性，再次使用分期计算方法。注意到调用C(1,q)时每个ci（1≤i≤j≤q）c(a,b)s=j-i＞1s计入第c(a,b)c(a,b)sc(a,b)的第一次cc(i,i)ssq-s1c(ij)需要计算，因此总的q-1ås=1(qs+1)=(q3)。cs2，3，.，q-1c(i,i+s)kay例3-14例3-13中五个矩阵的情况。先初始化c(i,i)(0≤i≤5)为0，然后对于i=1,.,4分c(i,i+1)。c(1,2)=r1r2r350，c(2,3)=50，c(3,4)=20c(4,5)=200kay1，2，34。s=2时，可得：c(1,3)=min{c(1,1)+c(2,3)+r1r2r4,c(1,2+c(3,3)+r1r3r4kay(132c(24c(353040kay值23。s=3c(1,4)和c(25c(2,5)所需要的所有中间值均已知(见155式)，代入计算后可得c(2,5)=90，kay(2,5)=2。c(1,4)可用同样的计算s=4时，可直接用（15-4）c(1,5)，因为该式右边所有项都已知。ckay的迭代程序见函数MatrixChain（158），该函数的复杂性为(q3kay156Traceback函数推算出相应的最优乘法计算过程。15-8ckay的迭代计算voidMatrixChain(intr[],intq,int**c,int{//Mijka//c[i][ic[i][i+1]kayii1for(inti=1;i<q;i++){c[i][i]=c[i][i+1]=r[i]*r[i+1]*r[i+2];kay[i][i+1]=i;}c[q][q]=计算余下的ckafor(ints=2;s<q;for(inti=1;i<=q-s;i++)//kic[i][i+s]=c[i][i]+c[i+1][i+s]+r[i]*r[i+1]*r[i+s+1];kay[i][i+s]=i;//for(intk=i+1;k<i+s;k++)inttc[i][k]c[k+1][i+s]r[i]*r[k+1]*r[i+s+1];if(t<c[i][i+s]){//更小的最小项c[i][i+s]=kay[i][i+s]=}}}的长度之和。对于每对顶点(i,j)ij之间可能有多条路径，各路径的长度可能各不相同。ijij的最短路径。3-15154131)2)3)4)由该图可知,10、28、9、273)13的最短在所有点对最短路径问题（allpairsshorest-pathsproblem）G中每对顶点之间的最短路径。也就是说，对于每对顶点(i,j)ijji的最短路径。因此对于一个np=n(n-1)G中不含有长度为G中每对顶点(i,j)之间总有一条不含环路的最短路径。当有0的环路时，可能得到长度为－∞的更短路径，因为包含该环路的最短路径往往Gn1nc(i,j,k)ijk表示该路径中的最大顶点。因此，如果Gc(i,j,0)=i=jc(i,j,0)=0；如G中不包含边，则c(i,j,0)=+∞。c(i,j,n)ij的最短路径的长度。例3-16图15-4。若k=0,1,2,3，则c(1,3,k)=∞；c(1,3,4)=28；若k=5,7c(1,3,k)10k=8,9,10c13,k)9139。对k＞0c(i,j,k)kij的最短路径有两种可能：该路径kc(i,j,k-1)c(i,k,k-1)+c(k,j,k-1)。c(i,j,k)可取两者中的最小值。因此可得到如下递归式：c(i,j,k)=min{c(i,j,k-1),c(i,k,k-1)+c(k,j,k-1)以上的递归将一个k级运算转化为多个k-1级运算，而多个k-1级运算应比一个k级运算简t(k)c(i,jk)t(k2t(k1ct(n2n。因此得到所c(i,j,n)的时间为(n22n)。c(i,j,k-1)c(i,j,n)。利用避免重复计算c(ijk)c值的时间减少到(n3。这可通过递归方式（157矩阵链问题）15-5所示。for（inti=1；i<=n;i++）for(intj=1;j<=n;j++)ci,j0aija//计算cijk0knfor(intk=1;k<=n;k++)for(intfor(intj=1;j<=n;j++if(c(i,k,k-1)+c(k,j,k-1)<c(i,j,k-1)c(i,j,k)=c(i,k,k-1)+c(k,j,k-1);elsec(i,j,k)=c(i,j,k-1);15-5i，c(i,k,k)=c(i,k,k1c(k,i,k=c(k,i,k1c(i,j)155c(i,j,k)c(i,j)c(i,j,n1AdjacencyWDigraphAllPairscijc[i][j]NoEdgeAllPairs同kayijkay[i][j]ijk值。在后面将看到如kay值来推断出从一个顶点到另一顶点的最短路径（1510中的函数OutputPath）。159的时间复杂性为(n3O(n)。15-9ckay的计算temvoidAdjacencyWDigraph::Allpairs(T**c,intijcijkayijcijc（i，j，0）for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){c[i][j]=a[i][j];kay[i][j]=}for(i=1;i<=n;i++)c[i][i]=0;//c[i][j]for(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){Tt1=c[i][k];Tt2=Tt3=if(t1!=NoEdge&&t2!=NoEdge&&(t3==NoEdge||t1+t2<t3)){c[i][j]=t1+t2;kay[i][j]=}}15-10voidoutputPath(int**kay,inti,int{//ijif(i==j)if(kay[i][j]==0)cout<<j<<'else{outputPath(kay,i,outputPath(kay,kay[i][j],}temvoidOutputPath(T**c,int**kay,TNoEdge,inti,int{//ijif(c[i][j]==NoEdge)cout<<"Thereisnopathfrom"<<i<<"to"<<j<<endl;return;}cout<<"Thepathis"<<endl;cout<<i<<'';outputPath(kay,i,j);cout<<endl;}3-1715-6aa，15-6b15-9所计算出的c矩阵，15-6ckay15-6ckay151kay15445的最短路径，因为kay45045的最短路径14kay14315的最在11.5.3节的交叉分布问题中，给定一个每边带n个针脚的布线通道和一个排列C。顶部的针脚i与底部的针脚Ci相连，其中1≤i≤n，数对(i,Ci)称为网组。总共有n个网组需连接或连通。假设有两个或的布线层，其中有一个为优先层，在优先层中可以使用更细的连线，其电阻也可能比其他层要小得多。布线时应尽可能在优先层中布设的网组。而剩下的其他网组将布设在其他层。当且仅 NoncrossingSubset，MNS)。在该集中，任意两个网组都不交叉。因(i,Ci)完全由i决定，因此可用i来指定(i,Ci)。例3-18图15-7（对应于图10-17）。(1,8)和(2,7)（也即1号网组和2号网组）交叉，因而不能布设在同一层中。而18，(7,9)和(9,10)未交叉，因此可布设在同一层。但这3MNS10-17中给出的例子中，集合｛(425579910)｝4MNSMNS(i,j)MNS，其中所有的(u,Cu)满足u≤i，Cu≤jsize(i,j)MNS(i,j)的大小(即网组的数目)MNS(n,n)MNSsize(n,n)是它的3-191017中的例子，MNS(1010)318的，size10104，因为18，(27，(79，83，(910)10676MNS(76)。因此只需剩下的4个网组是否属于MNS(7,6)，如图15-8所示。子集｛(3,4)55｝23的无交叉子集，因此size(76)2i=1时，1C1)MNS(1,j)j≥C1MNS(1的一个成员i＞1j＜Ci，则(i,Ci)MNS(i,j)MNS(i,j)的(u,Cu)u＜iCu＜j，因此：size(i,j)=size(i-1,j),j<-5（1>j≥Ci，则(i,Ci)MNS(i,j)内。若(i,Ci)在MNS(i,j)MNS(i,j)中不会有这样的(u,Cu：u＜i且Cu＞Ci，因为这个网组必与(i,Ci)MNS(i,j)中的其u＜i且Cu＜CiMNS(i,j)Mi-1,Ci-1个。若(i,Ci)MNS(i,j)MNS(i,j)中的所有(u,Cu)u＜i；因此size(i,j)=size(i-1j)。虽然不能确定(i,Ci是否在MNS(i,j)中，但我们可以根据获取更大MNS的原则来作出选择。因此：size(i,j)=max{size(i-1,j),size(i-1,Ci-1)+1},j≥Ci（15-8）虽然从（15-6）式到（15-8）式可用递归法求解，但从前面的例子可以看出，即使避免了重复计算，动态规划递归算法的效率也不够高，因此只考虑迭代方法。在迭代过程中先用式（15-6）计size1,j)，然后再用式（15-7）和（15-8）i=2,3,.,nsize(i,j)，TracebackMNS(n,n)中的所有网组。3-20159157size(i,j)size10104MS44size1010)入手。可用（158）式算出sie1010。根据式（158）size1010)=size910MNS910MNS1010)≠size810MNS(9,10)中必9号网组。MNS(9,10)MNS(8,C9-1)=MNS(8,9)MNS(89=MNS(7,9)知，8MNS(79，因为size(79size69)MNS7号网组。MNS(7,9)MNS6C71=MNS(68size68size58)65号网组，3MNS4号网组等其他网组被排除。因此回溯过程所得到的大小4MNS为{3,5,7,9}。size10jj≠101511sizei,j)MNSMNS用来计算size(i,j)的值，计算结果用一个二维数组MN来。size[i][j]表示size(i,j)，其中i=j=n或1≤i＜n，0≤j≤n，计算过程的时间复杂性为(n2TracebackNet［0m1］中输出所MNS，其时间复杂性为(n)MMS问题的动态规划算法的总的时间复杂性为(n21511voidMNS(intC[],intn,intij，计算sizeij//size1*for(intj=0;j<C[1];j++)size[1][j]=0;for(j=C[1];j<=n;j++)size[1][j]=1;//size[i][*],1<i<nfor(inti=2;i<n;i++){for(intj0jC[i];j++)size[i][j]=size[i-1][j];for(j=C[i];j<=n;size[i][j]=max(size[i-1][j],size[i-1][C[i]-}size[n][n]=max(size[n-1][n],size[n-1][C[n]-}voidTraceback(intC[],int**size,intn,intNet[],int&Net0m1MMSintj=n;//所允许的底部最大针脚编号m=0;//网组的游标for(inti=n;i>1;i--//i号netMNS中ifsize[i][j]size[i-1][j]){//MNSNet[m++]=i;j=C[i]-1;}1MNS中?if(j>=C[1])Net[m1;//MNS}前文主要介绍了动态规划的一些理论依据，前文所说的具有明显的阶段划分和状态转移方程的动题，并子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。子问题是独立的(即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地：11.对fn+1(xn+1)初始化2.fork:=ndownto1for每一个xk∈Xkfor每一个uk∈Uk(xkfk(xk):=一个极值ift比fk(xk)thenfk(xk):=t计算fk(xk)的最优值9.t:=一个极值10for每一个x1∈X1iff1(x1)比tthen下面通过实例来分析动态规划的设计步骤和具体应用。例1已经文介绍过了。例1和例23456是没有明显阶段划分的动4567是比较特殊的动态8是两重动态规划（即为了解决问题要进行两次动态规划）的例子。123Bitonic45678[9]我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入从左下角右上角两条路，两条径中任何一条边都不能，并要求两路径的长度最xk=(ak,bk)k时所处的位置，相应的，决策变量也增加一维，用[10LITTLESHOPOFFLOWERSYouwanttoarrangethewindowofyourflowershopinamostpleasantway.YouhaveFbunchesofflowers,eachbeingofadifferentkind,andatleastasmanyvasesorderedinarow.Thevasesaregluedontotheshelfandarenumberedconsecutively1throughV,whereVisthenumberofvases,fromlefttorightsothatthevase1istheleftmost,andthevaseVistherightmostvase.Thebunchesaremoveableandareuniquelyidentifiedbyintegersbetween1andF.Theseid-numbershaveasignificance:Theydeterminetherequiredorderofappearanceoftheflowerbunchesintherowofvasessothatthebunchimustbeinavasetotheleftofthevasecontainingbunchjwheneveri<j.Suppose,forexample,youhaveabunchofazaleas(id-number=1),abunchofbegonias(id-number=2)andabunchofcarnations(id-number=3).Now,allthebunchesmustbeputintothevaseskeetheirid-numbersinorder.Thebunchofazaleasmustbeinavasetotheleftofbegonias,andthebunchofbegoniasmustbeinavasetotheleftofcarnations.Iftherearemorevasesthanbunchesofflowersthentheexcesswillbeleftempty.Avasecanholdonlyonebunchofflowers.Eachvasehasadistinctcharacteristic(justlikeflowersdo).Hence,puttingabunchofflowersinavaseresultsinacertainaestheticvalue,expressedbyaninteger.Theaestheticvaluesarepresentedinatableasshownbelow.Leavingavaseemptyhasanaestheticvalueof0.VASE1234517--25-3-5--Accordingtothetable,azaleas,forexample,wouldlookgreatinvase2,buttheywouldlookawfulinvase4.Toachievethemostpleasanteffectyouhavetoizethesumofaestheticvaluesforthearrangementwhilekeetherequiredorderingoftheflowers.Ifmorethanonearrangementhasthealsumvalue,anyoneofthemwillbeacceptable.Youhavetoproduceexactlyonearrangement.1<=F<=100whereFisthenumberofthebunchesofflowers.Thebunchesarenumbered1throughF<=V<=100whereVisthenumberof-50<=Aij<=50whereAijistheaestheticvalueobtainedbyputtingtheflowerbunchiintothevaseTheinputisatextfilenamedThefirstlinecontainstwonumbers:F,ThefollowingFlines:EachoftheselinescontainsVintegers,sothatAijisgivenasthejthnumberonthe(i+1)stlineoftheinputfile.Theoutputmustbeatextfilenamedflower.outconsistingoftwoThefirstlinewillcontainthesumofaestheticvaluesforyourThesecondlinemustpresentthearrangementasalistofFnumbers,sothatthek’thnumberonthislineidentifiesthevaseinwhichthebunchkisput.35723-5-24521-410-215-4-2024Yourprogramwillbeallowedtorun2Nopartialcreditcanbeobtainedforatest本题虽然是IOI’99中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们以花束的编号来划分阶段。在这里，第k阶段布置第kFF+1个阶段，增加第F+1xkkxkukk+1束花放置的花瓶号；最优指标函数fk(xk)k束花到第n束花所得到的最大美学值；A(i,j)ij中的美学值,V是花瓶总数,F是花的总数。,1的规划方程中的允许决策空间：xk+1≤uk≤V-(F-k)+1比较麻烦，因此有待改进。还是以花束kkxkk束花所在的花瓶；注意，这里我们F1束花。于是状态变量ukk-1束花所在的花fk(xk)表示从第一束花到第k束花所获得的美学价值；A(i,j)ij中的美学值,V是花瓶总数,F是花的总数。则状态转移方程为：以花瓶的数目来划分阶段，第k个阶段决定花瓶kxkk个花瓶中放了多xkxk束花是否放在第kuk=10来表示。最优指标函数fk(xk)表示前kxk束花，所能取得的最大美学值。注意，这里仍然是不止一种的规划方法。有时各种方法所产生的效果是差不多的，但的时候，就像我们的例子一样，中，我们可以更深刻地动态规划的构思技巧。地已有结果，数据也不易压缩，因而空间是比较突出的。另一方面，动态规划的高时效性一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅必不可少的内容，以及数据划时，一个我们经常采用的方法是用一个与结点数一样多的数组来每一步的决策，这对于倒推求得们就应该抓住问题的主要。省去这个决策的数组，而改成在从最优解逐级倒推时，再计算一用，如果能有效地使用这一，对于相当大规模的问题，空间也不至于溢出（为了求出最优方案，保Data1和Data2这样两个数组，每次将Data1作为上一阶段，推得Data2数组，然后，将Data2通过覆盖到Data1之上，大。另外一种实现方法是，对于一个可能与前NData[0..N]，其中各项为最近N各阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的只要对应成对数组Data中下标为kmod(N+1)的单元的就可以了。这种处理方法对于程序修改的代码很少，速度动态规划与静态规划的关u1,u2,...,un，使指标函数V1n(xl,u1,u2,...,un)达到最优(最大或最小)的极值[11]用动态规划解下列非线性规划其中gk(uk)为任意的已知函数解：按变量ukknx1,x2,..xn取gk(uk)为阶段指标，最优值函数的基本方程为(注意到[12Themorepointsstudentsscoreinourcontests,thehappierwehereattheUSACOare.Wetrytodesignourcontestssothatpeoplecanscoreasmanypointsaspossible,andwouldlikeyourassistance.Wehaveseveralcategoriesfromwhichproblemscanbechosen,wherea"category"isanunlimitedsetofcontestproblemswhichallrequirethesameamountoftimetosolveanddeservethesamenumberofpointsforacorrectsolution.YourtaskiswriteaprogramwhichlstheUSACOstaffhowmanyproblemsfromeachcategorytoincludeinacontestsoasto izethetotalnumberofpointsinthechosenproblemswhilekeethetotalsolutiontimewithinthelengthofthecontest.Theinputincludesthelengthofthecontest,M(1<=M<=10,000)(don'tworry,youwon'thavetocompeteinthelongercontestsuntiltrainingcamp)andN,thenumberofproblemcategories,where1<=N<=10,000.EachofthesubsequentNlinescontainstwointegersdescribingacategory:thefirstintegerlsthenumberofpointsaproblemfromthatcategoryisworth(1<=points<=10000);thesecondlsthenumberofminutesaproblemfromthatcategorytakestosolve(1<=minutes<=10000).Yourprogramshoulddeterminethenumberofproblemsweshouldtakefromeachcategorytomakethehighest-scoringcontestsolvablewithinthelengthofthecontest.Remember,thenumberfromanycategorycanbeanynonnegativeinteger(0,one,ormany).Calculatethe umnumberofpossiblepoints.PROGRAMNAME:INPUTLine1:M,N--contestminutesandnumberofproblemclassesLines2-N+1:Twointegers:thepointsandminutesforeachclassSAMPLEINPUT(fileinflate.in)300410025012035OUTPUTAsinglelinewith umnumberofpointspossiblegiventheSAMPLEOUTPUT(fileinflate.out)用数值方法求解时存在维数灾(curseofdimensionality)m个取值，那么对于n维问题，状态xk就有mn个值，对于每个状态值都要计算、函数fk(xk)，对于n稍大(即使动态规划与递推——动态规划是最优化[13]142点、第3点时，路径长度mod4的余数不一定是最小，也就是说最优策略的子策略不一定最优——这个问题的路径是否存在，用fk(sk)来表示，则递推如下：lenk,ik-1ki条边的长度，方括号表示“或(or)”运算。最后的结果就是可以使f4(s4)s4值。这个递推法的递推和动态规划的规划方程非常相似，我们在这里借用了动态规划的符号也就是为了[14]有一个三角形木板,n(n+1)/2颗钉子，还有(n+1)个格子（n=5时如下图a）dd，且除了最左端和最右端的我们知道小球落在第i个格子中的概率现在的问题是计算拔掉某些钉子后，小球落在编号为mpm。假定最下面一排钉子不会3是某些钉子被拔掉后小球一条可能的路径。图 图 图输入1行为整数n（2<=n<=50）和m（0<=m<=n）n行依次为木板上从上至下n*.’表示钉子被拔n行中空格符可能出现在任何位置。仅一行，是一个既约分数(00/1)m的格子中的概率pm5*.**.*****既约分数的定义：A/BA、B为正整数且5*.**.***** [15]数字三角形7 下走（0表示）或向右下走（1表示）。每一点的路径总数。把这个总数用fk(xk)表示，那么递推就是：在这里，虽然求和只有两项，但我们仍然用∑的形式表示，就是为了突出这个递推和上面的规划方程