动态规划经典问题内容摘要：
动态规划经典问题 动态规划经典问题刘汝佳目录一、最长公共子序列O(、最优排序二叉树O(、最长上升子序列O(、最优三角剖分O(、最大、02n, 七、最优排序二叉树O(、最优合并问题O(、最长公共子序列 析考虑前缀x1.y1. 定义ci,j = |x1. y1.|则cm,n = |x, y)|. 递推公式为很直观. 考虑xi=yj的情形:关键点一: 最优子结构为了使用动态规划, 问题需具备最优子结构(接书写的程序递归树分析关键点二: 重叠子问题为了让动态规划确实发挥功效, 问题应该包含尽量多的重叠子问题(决方法: 记忆化注意果只需要最优值, 可以用滚动数组实现按照di,j只和dj和di,及d关系，因此只需要保留相邻两行, 空间复杂度为O(m,n)更进一步的, 可以只保留一行, 每次用单独的变量j, 则递推方程为If(i=j) dj=x; x = dj; dj=d dj ;变形. 回文词给一个字符串a, 保持原字符的顺序不变, 至少要加几个字符才能变成回文词?例: Î 、绿色表示原字符, 白色为新增字符显然, 任何一个位置不可能都是白色(不需要加那个字符!)应该让红色字符尽量多! 相当于求让色)对齐, 中间的每个绿色字符都增加一个字符和它相等二、最优排序二叉树给造让期望比较次数最小的排序二叉树分析定理：最优排序二叉树的子树也是最优排序二叉树给出关键码序排列）问题：把哪个关键码做为根。 则左右子树可以递归往下做0 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是从第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,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,j+1+dk,j这就是k<=k<=j阅读剩余 0%