算法艺术与信息学竞赛标准.ppt
47页
《算法艺术与信息学竞赛》标准课件动态规划(一): 经典问题刘汝佳 目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)五、最大m子段和O(mn)六、0-1背包问题O(min{nc, 2nn}) 一、最长公共子序列•Longest Common Subsequence(LCS) 分析•考虑前缀x[1..i]和y[1..j], 定义c[i,j] = |LCS(x[1..i], y[1..j])|•则c[m,n] = |LCS(x, y)|. 递推公式为•很直观. 考虑x[i]=y[j]的情形: 关键点一: 最优子结构•为了使用动态规划, 问题需具备最优子结构最优子结构(Optimal Substructure) 直接书写的程序 递归树分析 关键点二: 重叠子问题•为了让动态规划确实发挥功效, 问题应该包含尽量多的重叠子问题重叠子问题(overlapping subproblems) 解决方法: 记忆化•注意memoization不是memorization 自底向上递推 空间优化•如果只需要最优值, 可以用滚动数组实现•按照i递增的顺序计算, d[i,j]只和d[i-1,j]和d[i,j-1]以及d[i-1,j-1]有关系，因此只需要保只需要保留相邻两行留相邻两行, 空间复杂度为O(min{m,n})•更进一步的, 可以只保留一行, 每次用单独的变量x保留d[i-1,j], 则递推方程为If(i==j) d[j]=x; else { x = d[j]; d[j]=max{d[j-1], d[j]} }; 变形. 回文词•给一个字符串a, 保持原字符的顺序不变, 至少要加几个字符才能变成回文词?•例: abfcbfa afbcfcbfa 分析•红、绿色表示原字符, 白色为新增字符•显然, s和s’在任何一个位置不可能都是白色(不需要加那个字符!)•应该让红色字符尽量多! 相当于求相当于求s和逆序串和逆序串s’的的LCS, 让LCS中的对应字符(红色)对齐, 中间的每个绿色字符都增加一个字符和它相等 二、最优排序二叉树•给n个关键码和它们的频率，构造让期望比较次数最小的排序二叉树 分析•定理：定理：最优排序二叉树的子树也是最优排序二叉树•给出关键码-频率对照表（升序排列）•问题：把哪个关键码做为根？则左右子树可以递归往下做ABCDE23 10812 30FGHIJKLMNOP..514 18 202411722 22 10.. 分析•用递归来思考，但用递推来做•先考虑两个结点的情形 分析•可以用矩阵来保存结果•C[j,k]表示从j到k的关键码组成的最优排序二叉树•Root[j,k]记录这棵排序二叉树的根 分析•考虑三个结点的情形•最优值放在C[B,D]中，根放在root[B,D]中 分析•类似地，更新所有C[j-2,j]和root[j-2,j] 分析•四个结点的情形（如A-D） 分析•最终计算结果为 分析•可以利用root矩阵递归地构造出最优树 分析•时间复杂度：计算每个C[i,j]和root[i,j]需要枚举根结点，故为O(n3)•空间复杂度：需要两个n*n矩阵，O(n2) 三、最长上升子序列•最长上升子序列问题（最长上升子序列问题（LIS））给一个序列，求它的一个递增子序列，使它的元素个数尽量多。
例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7（还有其他的，这里略去） 分析•定义d[i]是从第1个元素到第i个元素为止的最长子序列长度, 则状态转移方程为•直接使用这个方程得到的是O(n2)算法•下面把它优化到O(nlogn) 状态的组织•d值相同的a值只需要保留最小的只需要保留最小的, 因此用数组g[i]表示d值为i的数的a最小值, 显然g[1]<=g[2]<=…<=g[k]•计算计算d[i]: 需要在g中找到大于等于a[i]的第一个数j, 则d[i]=j•更新更新g: 由于g[j]>a[i], 需要更新g[j]=a[i] 代码•使用STL的lower_bound可以直接求出比a[i]大的第一个数, 用二分查找实现, 每次转移时间O(logn), 总时间O(nlogn)fill(g, g + n, infinity);for(int i = 0; i < n; i++){ int j = lower_bound(g, g + n, a[i]) - g; d[i] = j + 1; g[j] = a[i];} 变形1: 航线问题•有两行点, 每行n个. 第一行点和第二行点是一一对应的, 有线连接, 如下图所示•选择尽量多的线, 两两不交叉 分析•设与第1行第i个点对应的是第2行第f[i]个点•假设i 每场比赛在某相邻两人间进行，败者退出圈子，紧靠败者右边的人成为与胜者直接相邻的人•任意两人之间决斗的胜负都将在一矩阵中给出（如果A[i,j]=1则i与j决斗i总是赢，如果A[i,j]=0则i与j决斗时i总是输），•求出所有可能可能赢得整场决斗的人的序号 分析•首先把圈想象成一条链•设d[i,j]表示i是否能和j相遇, 则相遇的充要条件是存在k, i和k, k和j都能相遇, 且i或或j能打败k•同样是O(n2)个状态, 决策O(n), 总O(n3) 五、最大m子段和•给一个序列a1, a2, …, an•求m个不相交不相交(可以相接)的连续序列, 总和尽量大•例如m=2, 1 2 -3 4 5 -6 7 分析•设d[i,j]为以j项结尾的i段和的最大值, 则需要枚举此段开头y和上一段结尾x, 即d[i,j]=max{d[i-1,x] + a[y..j]}•每次需要枚举x
