动态规划经典问题

1、动态规划经典问题刘汝佳目录一、最长公共子序列O(mn)二、最优排序二叉树0(卡)三、最长上升子序列O(nlogn)四、最优三角剖分O(rP)五、最大m子段和O(mn)六、0/背包问题O(minnc, 2n, n1.44n)七、最优排序二叉树0(卡)八、最优合并问题O(nlogn)、最长公共子序列 Longest Common Subsequence(LCS) Given two sequences xl . . m andf l . . n. finda longest subsequence common to them both.x: ABCBDCBCBA =LCS (兀 y)functi

2、onal notation,but not a function分析考虑前缀X仁i和y仁j,定义ci5j = |LCS(x1J5y1.j)|则cm,n = |LCS(x, y)|.递推公式为ifxi=yJl otherwise.很直观考虑xi=yO的情形:x:1 2关键点一:最优子结构为了使用动态规划，问题需具备最优子结构(Optimal Substructure) B9Optimal substructureAn optimal solution to a problem (instance) contains optimal solutions to subproblems.丿Ifz =

3、LCS(x, y). then any prefix of z is an LCS of a prefix of x and a prefix of y.直接书写的程序LCS(x, y. z；y)ifx|7 =yjthen cij j LCS(兀 y, z-lj-1) + 1 else ci. j <- max LCS(x? y.LCS(X y.递归树分析m+nHeight = m m work potentially exponential, but werre solving subproblems already solved!关键点二：重叠子问题为了让动态规划确实发挥功效，问题应

4、该包含尽. ° Overlapping subproblemsA recursive solution contains asmallff number of distinctsubproblems repeated many times.The number of distinct LCS subproblems fortwo strings of lengths m解决方法:记忆化 注意 memoizatiori 不是 memorizationMemoization: After computing a solution to a subproblem, store it in

5、a table. Subsequent calls check the table to avoid redoing work.LCS(x5 y. z5 ；)same> asbeforeifc/；j=NILthen if xz =yjthen cij LCSg” z-l?j-l) + 1 else cij J maxLCS(x?y,LCS(圣”Time = constant work per table entry.Space = &(mn).自底向上递推Idea:A B C B D A变形.回文词空间优化如果只需要最优值,可以用滚动数组实现按照i递增的顺序计算,di,j只和d/

6、和变形.回文词以及关系，因此只需要保留相邻两行,空间复杂度为O(minm,n)更进一步的，可以只保留一行，每次用单独 的变量x保留di-1,j,则递推方程为lf(i=j) dj=x;else x = dj; dj=maxdj-15 dj;给一个字符串a,保持原字符的顺序不变,至 少要加几个字符才能变成回文词？彳列：abfcbfa 9 afbcfcbfa红、绿色表示原字符，白色为新增字符显然，S和s'在任何一个位置不可能都是白色（不 需要加那个字符!）应该让红色字符尽量多！相当于求s和逆序串s' 的LCS,让LCS中的对应字符（红色）对齐 中间的 每个绿色字符都增加一个字符和它相

7、等1234554321、最优排序二叉树给n个关键码和它们的频率，构造让期望比 较次数最小的排序二叉树分析定理：最优排序二叉树的子树也是最优排 序二叉树给出关键码频率对照表（升序排列）问题：把哪个关键码做为根？则左右子树 可以递归往下做用递归来思考，但用递推来做先考虑两个结点的情形CostD：xl + 12x2 = 32x2 + 12x1MincD|eFGHIJKLMN0P 812bo514182024117222210 A1123可以用矩阵来保存结果 Cj,k表示从j到k的关键码组成的最优排序二叉树Rootj,k记录这棵排序二叉树的根分析分析BC234310268281254304052414

8、46185620242A B C D E F G H II J KDFH00112334445667788Q9ABCDEFGHIJKABDGHEF分析考虑三个结点的情形最优值放在CB,D中，根放在rootB,D中分析分析BCDJEFGHIJKLMN0P 2t1081230514182024117222210 * Root = DDBestB,c分析类似地,更新所有Cj-2,j和rootg-2,j分析分析Roots分析四个结点的情形（如AD） Choose A as rootUse 0 for left Best B-D is known Choose B as rootA-A is in C0

9、90Best C-D is known Choose C as rootA-B isinC091D is in C3?3 Choose D as rootis in C0,2Use 0 in C4,3 for right分析分析最终计算结果为» Finalcost2310H81D428121BQ78543019S12288644D230121977324zbJ科151125604618Fr212180W186562022D186W79260242AC D E F G H I J:分析可以利用root矩阵递归地构造出最优树ABCDEFGH IJF 2 4 4 4 4 5时间复杂度:计算

10、每个Cij和rooti,j需要 枚举根结点，故为O(rP)空间复杂度：需要两个nF矩阵，OS。三、最长上升子序列最长上升子序列问题(LIS)给一个序列， 求它的一个递增子序列，使它的元素个数 尽量多。例如序列1,6,2,5,47的最长上升子 序列是1,2,5,7 (还有其他的，这里略去)分析定义di是从第1个元素到第i个元素为止的最长子 序列长度，则状态转移方程为di = min dk + 1更 <1 且 ak<ai直接使用这个方程得到的是0(孕)算法下面把它优化到O (nlogn)状态的组织 d佰相同的a值只需要保留最小的,因此用数 组gi表示d值为啲数的a最小值，显然gi<

11、;=g2<=-<=gk计算di:需要在g中找到大于等于ai的第 一个数j,则di=j更新g：由于gj>ai,需要更新gj=ai代码使用STL的lower_bound可以直接求出比ai 大的第一个数，用二分查找实现，每次转移 时间O(logn),总时间0(nlogn)fill(g, g + n, infinity);for(int i = 0; i < n; i+ +)int j = lower_bound(g, g + n, ai) - g; di = j + 1；gj = ai；变形1:航线问题有两行点，每行n个第一行点和第二行点是一一 对应的，有线连接，如下图所示选

12、择尽量多的线，两两不交叉分析设与第1行第i个点对应的是第2行第fi个点 假设ivj,两条线(i, fi)和(j, fj)的充要条件是 fivfj,因此问题变成了求f的最长上升子序列时间复杂度为O (nlogn)变形2:两排列的LCS给1ri的两个排列p1? p2求6和P2的最长公共子序列例：1 5 3 2 4 O 5 3 4 2 1分析算法一：直接套用LCS算法，时间0(卡)算法二:注鳶到把两个排列做相同的置换,LCS不变，可以先把6排列为1,2,3.,n15324 O 12345即映射5T2, 2T4, 4->5,卩2作同样置换 53421 023541与1,2,3.n的LCS显然是最

13、长上升子序列，时 间降为0 (nlogn)推广：DAG上的最短路 “上升”依赖于序关系V二,它具有一般性 DAG(有向无环图)的最长路径问题:把有向 边看成偏序关系，则本题的算法一仍然适用, 时间复杂度为0(n2)如果图的边数m比较， 可进一步优化到0(m),因为每条边恰好考虑 一次(用邻接表或前向星，而不是邻接矩阵)算法二不再适用！因为d值相同的a不一定可 以两两相互比较,不一定存在最小值.四、最优三角剖分冷一fn个顶点的凸多边形,有很多方法对它进行 三角咅U分（polygon triangulation）每个三角形有一个权计算公式（如周长,顶点权和）, 求总权最小（大）的三角剖分方案分析用

14、di,j表示由顶点i,i+1, .,j组成的多边形(注意i可以大于j)的最小代价-方案一：枚举三个顶点，组成一个三角形，决策 是0(2)的-方案二：边(i,j) 一定属于一个唯一的三角形，设第 三个顶点为k,则决策仅为0(n)采用方案二状态0(卡),决策0(n),总O(rP)分析确定k后，最优方案应该是di,k+dk,j+w(i,k,j)因此转移方程 di,j=maxdi,k+dk,j+w(i,k,j)变形1:最优矩阵乘法链需要计算n个矩阵的乘积"A?A"由于矩阵乘法满足结合律，可以有多种计算 方法例如宀是10*100, A?是100*5, A3是 5*50,则-顺序1:

15、（A1A2）A3,代价为10*100*5+10*5*50=7500-顺序2：人（人2人3）,代价为100*5*10+10*100*50=75000求代价最小的方案（加括号方法）共同的结构用二叉树(binary tree)可以表示两个问题相同的 结构，每个结点表示一个区间(结点区间/矩阵区 间)，左子树和右子树表示分成的两个序列如果在原问题中让di,j表示/j的最优值，则在 方程形式上也完全等价(AA2A3)(A4(A5A6)4变形2.决斗编号为门的门个人按逆时针方向排成一 圈，他们要决斗门-1场。每场比赛在某相邻 两人间进行，败者退出圈子，紧靠败者右 边的人成为与胜者直接相邻的人。任意两人之间

16、决斗的胜负都将在一矩阵中 给出（如果A/,/=1则/与/决斗/总是風，如果 A/,y=O则/与j决斗时/'总是输），求出所有可能赢得整场决斗的人的序号首先把圈想象成一条链12341设di,j表示i是否能和j相遇，则相遇的充要条件是 存在k, i和k, k和j都能相遇,且國能打败ki >k < i同样是0(乍)个状态，决策0(n),总0(2)五、最大m子段和给一个序列a1)a2).,an求m个丕相交(可以相接)的连续序列，总和 尽量大例如m=2, 1 2 3 4 5-67分析设di,j为以j项结尾的i段和的最大值，则需要 枚举此段开头y和上一段结尾x,即di,j=maxdi-

17、1,x + ay.j每次需要枚举x<y<=j,决策量为0(2),状态 为O(nm),共0(伽)注意到如果也是本段的，答案变成为 di,j-1+aj,因此方程优化为di,j=maxdi,j-1+aO, di-1,x+aj, x<j优化后状态仍然是二维的，但决策减少为0(n),总O(n2m)可以继续优化注意到时间主要耗费在对x的妆举匕计Mmaxdi-1,x.这个值我们把d的第一维称为”阶段”,则本题是典型 的多阶段决策问题-计算一个阶段时,顺便记录本阶段最大值-只保留相邻两个阶段(滚动数组)则时间降为O(nm),空间降为0(n)六、CM背包问题给定n种物品和一个背包，物品i的重量

18、是Wj, 价值是Vj,背包容量为c对于每个物品，要么装背包，要么不装选择装背包的物品集合，使得物品总重量 不超过背包容量C,且价值和尺量大分析设di,j为背包容量为j时，只考虑前i个物品时 的最夭价值和-如果装第i个物品，背包容量只剩卜Wj-如果不装,背包容量不变因此di,j=maxdi,j-wi+vi, di-1,j状态有nc个，每个状态决策只有两个，因此 总时间复杂度为O(nc).用滚动数组后，空间 复杂度只有0(c)当C大时，算法效率非常低事实上，由于C 是数值范围参数,一般不把它看作输入规模. 这样的O(nc)只是一个伪多项式算法事实上，如果物品重量和背包容量都是实数 时,算法将失败，

19、因为看起来物品的重量和 可以是”任何实数”.但事实是:物品重量和只有刀种可能的取值, 并不是无限多种算法一：枚举创个子集合，再计算，枚举2Y 计算n,共吃门算法二：采用递归枚举，共创算法三：先考虑一半元素，保存个和再 考虑后一半元素，每计算出一个和w,查找重 量=c-w的元素中价值的最大值.下面考虑实现细节算法三前一半元素的2"2个和按重量从小到大排序后放在 表a里对于任何两个和i, j,如果Wj<Wj且vpvj,贝ijj 是不需要保存的，因此按重量排序好以后也是按价 值排序的考虑后一半元素时，每得到一个重量w,用二分查 找得到重量不超过cw的最大元素，则它的价值也 最大.预处

20、理时间复杂度2n/2log2n/2,每个重量W二分查找 时间为Iog2n/2,因此总2n/2log2n/2=O(n1.44n)七、再谈最优排序二叉树给n个关键码和它们的频率，构造让期望比 较次数最小的排序二叉树基本分析设结点i.j的最优代价为di,j,则刀人 7 = linndi, 1 + dk + 1,7 + iffz, j述 kW j其中wi,j=fj+fj+i+fj,（如果认为根结点的代价为0, 则wi,j要减去fQ直接计算是0（2）的设di,j的最优决策为Ki,j,下面证明Ki,j-1<=Ki,j<=Ki+1,j从而把时间复杂度降到0（卡）四边形不等式街）(门) 凸性(Mo

21、nge condition/quadrangle inequality) wij+wiT<=wij+wi5j55 i<=i5<j<=j5单调性(区间包含格上)w(i,5j)<=w(i3j,)5 i<=i5<j<=j,列j列亍(if)(i'j *)验证四边形不等式只需验证wi5j+wi+15j+1 <=wi+15j+wi3j+1移项得wi+1 ,j+1-wi+1 ,j<=wi,j+1-wi,j当j固定时记函数f(x) = wx,j+1-wx,j,则上 式变为：f(i+1)<=f(i),因此f(i)是减函数,w为凸；f(i)

22、是增函数，w为凹固定i有同样的结论(减函数时为凸)本题中的w本题中，w的凸性更好证明：wi5j+wi+1j+1 =wij+(wij+fj+1-fi) =wi+1j+wij+1两边是完全相等的或者计算f(x)=wx,j+1-wx,j=fi+1=常数常数既是增函数也是减函数，因此 本题中，W既为凸也为凹定理考虑递归式 di,j=mindi,k-1+dk,j+wi,j定理（F.Yao）:若w满足四边形不等式，贝Ud也 满足四边形不等式，即di,j+di,j,<=di,j+di,j,i<=i5<=j<=j,证明：对长度）二闩归纳，显然iv=1时正确ih 或j=j'时（同

23、一行或同一列），等式显然成立 -情形1: i'二j,退化为反三角不等式-情形2:Xj情形反三角不等式 i'=i时,di,j+dijv二di；j+dij退化为dij+djJ5<=diJl设k为让dij取最小值的决策（有多个时取最 大药一个k,后向）.若kv=j,则k是计算dRil考虑过的合法决策dij<=wij+di5k-1+dkj两边加上dj,j',得dij+djj5<=wij+diA-1+dkj+djj5情形反三角形不等式设k为让dij取最小值的决策kv=j时有dij+djJl<=wiJ+diJk-1+dkJ+djJ5用单调性和反三角形不等式（

24、归纳假设），有diJ+djJ5<=wij5+di5k-1+dkJ5由于k是最佳决策，右边恰好是dij,这就证 明了情形1中kv=j的情形,k>j时类以情形2 非退化的情形 i'vj时,右边保留两项di；j和di,j设二者取 最小值时的决策分别另y和乙仍需分ZV二y和 z>y两种情况（对称）.下窗只考虑zv二y时 y和z是合法决策，因此yv二j, z>i,且dij<=wij+di,z-1 +dzJ dij5<=wij5+diy-1+dyj5 两式相加并整理，对应项写在一起，得情形2 非退化的情形两式相加并整理，对应项写在一起，右边V二 wi+wHdi，

25、z1+dy1+dz，jHdyj 因ZV二y,红蓝色分别用四边形不等式，右边v二wijHwjHdi，z1Hdy1+dzj+dy，j 按红蓝色分别组合，得dij+di5j5<=dij5+di5j zv二y时命题得证.z>y时类似决策单调性进一步地,d的凸性可以推出决策的单调性设kij为让di,j取最小值的决策，下面证明kiJ<=kij+1<=ki+1J+15 i<=j即：k在同行同列上都是递增的证明：i=j时显然成立.由对称性，只需证明 ki,j<=ki,j+1.记dki,j=di,k-1+dk,j+wi,j, 贝|J只需要证明对于所有的ivkv二k'v

26、二j,有dkIiJ<=dJiJdk，ij+1<=dkij+1决策单调性事实上，我们可以证明一个更强的式子dki,j-dki,j<=dki>j+1-dki,j+1（i<k<=k5<=j） k在口更优（左>=0）9k在上也更优（右>=0）设K是i,j的最优值，则对于它左边的任意k, K在 i,j更优可推出k，在i,j+1上也更优，因此在区间 l,j+1±, k，左边的值都比它尢 如下图kk1决策单调性欲证dki,j-dji,j<=dki,j+1-dki,j+1,移项得 dki,j+dki,j+1<=dki,j+1+dji,

27、j按定义展开，两边消去wi,j+wi,j+1,得 di,k-1+dk,j+di,k,-1+dk,j+1<= di,k/+dk,j+1+di,k"+dK,j同时消去红色部分，得dkj+dk5j+1<=dkj+1+dk5j这就是k<=k5<=j<j+1时d的凸性算法优化由于k是单调，计算di,j时决策只需从ki,j1枚举至(J ki+1,j即可当1=(4固定时，一 d1,L+1的决策是k口丄倒k2,L+1一 d2,L+2的决策是k2,L+1SiJk3,L+2一 d3,L+3的决策是k3丄+2到k4丄+3 -总决策是从k1,L到kn-L+1,n,共0(n)对于0(n)个L,共0(n勺个决策.本题方程略有不同M旦也可用类似方法证明八、最优合并问题有n个正整数,每次可以合并两个相邻的数 （相加），代价为相加后的新数.按如何的顺序把所有的数合并成一个，使得 代价总