《动态规划经典问题》由会员分享，可在线阅读，更多相关《动态规划经典问题（70页珍藏版）》请在金锄头文库上搜索。
1、动态规划经典问题刘汝佳目录一、最长公共子序列O(、最优排序二叉树O(、最长上升子序列O(、最优三角剖分O(、最大、02n, 七、最优排序二叉树O(、最优合并问题O(、最长公共子序列 析考虑前缀x1.y1. 定义ci,j = |x1. y1.|则cm,n = |x, y)|. 递推公式为很直观. 考虑xi=yj的情形:关键点一: 最优子结构为了使用动态规划, 问题需具备最优子结构(接书写的程序递归树分析关键点二: 重叠子问题为了让动态规划确实发挥功效, 问题应该包含尽量多的重叠子问题(决方法: 记忆化注意果只需要最优值, 可以用滚动数组实现按照di,j只和dj和di,及d关系，因此只需要保留相邻
2、两行, 空间复杂度为O(m,n)更进一步的, 可以只保留一行, 每次用单独的变量j, 则递推方程为If(i=j) dj=x; x = dj; dj=d dj ;变形. 回文词给一个字符串a, 保持原字符的顺序不变, 至少要加几个字符才能变成回文词?例: 、绿色表示原字符, 白色为新增字符显然, 任何一个位置不可能都是白色(不需要加那个字符!)应该让红色字符尽量多! 相当于求让色)对齐, 中间的每个绿色字符都增加一个字符和它相等二、最优排序二叉树给造让期望比较次数最小的排序二叉树分析定理：最优排序二叉树的子树也是最优排序二叉树给出关键码序排列）问题：把哪个关键码做为根？则左右子树可以递归往下做0
3、 8 12 305 14 18 20 2 4 11 7 22 22 10 .递归来思考，但用递推来做先考虑两个结点的情形分析可以用矩阵来保存结果 Cj,k表示从j,k记录这棵排序二叉树的根分析考虑三个结点的情形最优值放在CB,D中，根放在,D中分析类似地，更新所有Cj和j分析四个结点的情形（如析最终计算结果为分析可以利用间复杂度：计算每个Ci,j和i,j需要枚举根结点，故为O(空间复杂度：需要两个n*(、最长上升子序列最长上升子序列问题（一个序列，求它的一个递增子序列，使它的元素个数尽量多。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7（还有其他的，这里略去）分析定义di是从第
4、1个元素到第则状态转移方程为直接使用这个方程得到的是O(法下面把它优化到O(态的组织因此用数组gi表示显然g1ai, 需要更新gj=ai代码使用i大的第一个数, 用二分查找实现, 每次转移时间O( 总时间O(g, g + n, ;则因此按重量排序好以后也是按价值排序的考虑后一半元素时, 每得到一个重量w, 用二分查找得到重量不超过则它的价值也最大. 预处理时间复杂度2n/2, 每个重量, 因此总2n/2=O(、再谈最优排序二叉树给造让期望比较次数最小的排序二叉树基本分析设结点i.i,j, 则其中wi,j=fi+如果认为根结点的代价为0, 则wi,j要减去直接计算是O(设di,j的最优决策为Ki
5、,j, 下面证明Ki,非退化的情形 i称). 下面只考虑且di,j一步地, ki,j为让di,j取最小值的决策, 下面证明ki,j=0)k在i,j+1上也更优(右=0)设k是i,j的最优值，则对于它左边的任意k, k在i,j更优可推出k在i,j+1上也更优, 因此在区间I,j+1上, k左边的值都比它大, 如下图决策单调性欲证dki,ji,j=dki,j+1i,j+1, 移项得dki,j+i,j+1=dki,j+1+i,j按定义展开, 两边消去wi,j+wi,j+1, 得di,dk,j+di,kdk,j+1=di,dk,j+1+di,kdk,j同时消去红色部分，得dk,j+dk,j+1=dk,
6、j+1+dk,j这就是k=k=jj+1时于计算di,j时决策只需从ki,举到ki+1,j即可当L=d1,L+1的决策是k1,L到k2,L+1d2,L+2的决策是k2,L+1到k3,L+2d3,L+3的决策是k3,L+2到k4,L+3总决策是从k1,L到k,n, 共O(n)对于O(n)个L, 共O(决策. 本题方程略有不同, 但也可用类似方法证明八、最优合并问题有每次可以合并两个相邻的数(相加), 代价为相加后的新数.按如何的顺序把所有的数合并成一个, 使得代价总和尽量小?分析假设数ii,j, 考虑最后一次合并, 有di,j = di,dk,j+wi,j其中wi,j = ai+aj显然wi,j是
7、凸的和增的, 因此用四边形不等式优化后时间复杂度降为O(下面进一步优化到O(误的贪心法贪心法: 每次采取代价最少的合并方案不一定得到最优解! 最优解为74分析可以把合并过程画成一棵树, 标记结点深度相容结点贪心法相容结点对: 中间没有原始结点的结点对修改的贪心法:每次合并和最小的相容结点i, j. 如果有多个, 因此让改的贪心法没有按照题目要求合并, 得到的合并树不一定是合法的答案, 但它同样能得到了一棵树, 代价和仍然是di* 其中理:用相容结点贪心法得到的树, 在保持各叶子的深度法:用修改贪心法求出深度序列, 再重组实现上的考虑合并结点用圆形表示, 原始结点用正方形表示第边的正方形组成一个结点集合i)每次合并的两个结点一定是某一个i)和次小值i)贪心过程:每次选择使i)+i)最小的i, 合并结点i)和i)分析合并操作两个圆形: 没有影响一个圆形和一个正方形: 合并两个个正方形: 三个心过程: O( 使用可并优先队列标记深度: O(n)树重组: O(n)
