《动态规划(一)》由会员分享，可在线阅读，更多相关《动态规划(一)（34页珍藏版）》请在金锄头文库上搜索。
1、算法艺术与信息学竞赛 标准课件,动态规划(一): 经典问题 刘汝佳,目录,一、最长公共子序列O(mn) 二、最优排序二叉树O(n3) 三、最长上升子序列O(nlogn) 四、最优三角剖分O(n3),一、最长公共子序列,Longest Common Subsequence(LCS),分析,考虑前缀x1i和y1j, 定义 ci,j = |LCS(x1i, y1j)| 则cm,n = |LCS(x, y)|. 递推公式为很直观. 考虑xi=yj的情形:,关键点一: 最优子结构,为了使用动态规划, 问题需具备最优子结构(Optimal Substructure),直接书写的程序,递归树分析,关键点二:
2、 重叠子问题,为了让动态规划确实发挥功效, 问题应该包含尽量多的重叠子问题(overlapping subproblems),解决方法: 记忆化,注意memoization不是memorization,自底向上递推,空间优化,如果只需要最优值, 可以用滚动数组实现 按照i递增的顺序计算, di,j只和di-1,j和di,j-1以及di-1,j-1有关系，因此只需要保留相邻两行, 空间复杂度为O(minm,n) 更进一步的, 可以只保留一行, 每次用单独的变量x保留di-1,j, 则递推方程为 If(i=j) dj=x; else x = dj; dj=maxdj-1, dj ;,变形. 回文词
3、,给一个字符串a, 保持原字符的顺序不变, 至少要加几个字符才能变成回文词? 例: abfcbfa afbcfcbfa,分析,红、绿色表示原字符, 白色为新增字符 显然, s和s在任何一个位置不可能都是白色(不需要加那个字符!) 应该让红色字符尽量多! 相当于求s和逆序串s的LCS, 让LCS中的对应字符(红色)对齐, 中间的每个绿色字符都增加一个字符和它相等,二、最优排序二叉树,给n个关键码和它们的频率，构造让期望比较次数最小的排序二叉树,分析,定理：最优排序二叉树的子树也是最优排序二叉树 给出关键码-频率对照表（升序排列） 问题：把哪个关键码做为根？则左右子树可以递归往下做,分析,用递归来
4、思考，但用递推来做 先考虑两个结点的情形,分析,可以用矩阵来保存结果 Cj,k表示从j到k的关键码组成的最优排序二叉树 Rootj,k记录这棵排序二叉树的根,分析,考虑三个结点的情形 最优值放在CB,D中，根放在rootB,D中,分析,类似地，更新所有Cj-2,j和rootj-2,j,分析,四个结点的情形（如A-D）,分析,最终计算结果为,分析,可以利用root矩阵递归地构造出最优树,分析,时间复杂度：计算每个Ci,j和rooti,j需要枚举根结点，故为O(n3) 空间复杂度：需要两个n*n矩阵，O(n2),三、最长上升子序列,最长上升子序列问题（LIS）给一个序列，求它的一个递增子序列，使它
5、的元素个数尽量多。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7（还有其他的，这里略去）,分析,定义di是从第1个元素到第i个元素为止的最长子序列长度, 则状态转移方程为直接使用这个方程得到的是O(n2)算法 下面把它优化到O(nlogn),状态的组织,d值相同的a值只需要保留最小的, 因此用数组gi表示d值为i的数的a最小值, 显然 g1ai, 需要更新gj=ai,代码,使用STL的lower_bound可以直接求出比ai大的第一个数, 用二分查找实现, 每次转移时间O(logn), 总时间O(nlogn),fill(g, g + n, infinity); for(int
6、i = 0; i n; i+) int j = lower_bound(g, g + n, ai) - g; di = j + 1; gj = ai; ,变形1: 航线问题,有两行点, 每行n个. 第一行点和第二行点是一一对应的, 有线连接, 如下图所示 选择尽量多的线, 两两不交叉,分析,设与第1行第i个点对应的是第2行第fi个点 假设ij, 两条线(i, fi)和(j, fj)的充要条件是fifj, 因此问题变成了 求f的最长上升子序列 时间复杂度为O(nlogn),变形2: 两排列的LCS,给1n的两个排列p1, p2 求p1和p2的最长公共子序列 例: 1 5 3 2 4 5 3 4
7、2 1,分析,算法一: 直接套用LCS算法, 时间O(n2) 算法二: 注意到把两个排列做相同的置换, LCS不变, 可以先把p1排列为1,2,3,n 1 5 3 2 4 1 2 3 4 5 即映射52, 24, 45, p2作同样置换 5 3 4 2 1 2 3 5 4 1 与1,2,3n的LCS显然是最长上升子序列, 时间降为O(nlogn),四、最优三角剖分,给一个n个顶点的凸多边形, 有很多方法对它进行三角剖分(polygon triangulation) 每个三角形有一个权计算公式(如周长, 顶点权和), 求总权最小(大)的三角剖分方案,分析,用di,j表示由顶点i, i+1, , j组成的多边形(注意i可以大于j) 的最小代价 方案一: 枚举三个顶点, 组成一个三角形, 决策是O(n3)的 方案二: 边(i,j)一定属于一个唯一的三角形, 设第三个顶点为k, 则决策仅为O(n) 采用方案二, 状态O(n2), 决策O(n), 总O(n3),分析,确定k后, 最优方案应该是di,k+dk,j+w(i,k,j) 因此转移方程di,j=maxdi,k+dk,j+w(i,k,j),
