《算法艺术和信息学竞赛》标准课件.ppt

《算法艺术与信息学竞赛》标准课件 动态规划(一): 经典问题 刘汝佳 目录 一、最长公共子序列O(mn) 二、最优排序二叉树O(n3) 三、最长上升子序列O(nlogn) 四、最优三角剖分O(n3) 五、最大m子段和O(mn) 六、0-1背包问题O(min{nc, 2n, n1.44n}) 一、最长公共子序列 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个关键码和它们的频率，构造让期望比较次数最小的排序二叉树 分析 定理：最优排序二叉树的子树也是最优排序二叉树 给出关键码-频率对照表（升序排列） 问题：把哪个关键码做为根？则左右子树可以递归往下做 分析 用递归来思考，但用递推来做 先考虑两个结点的情形 分析 可以用矩阵来保存结果 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) 变形1: 航线问题 有两行点, 每行n个. 第一行点和第二行点是一一对应的, 有线连接, 如下图所示 选择尽量多的线, 两两不交叉 分析 设与第1行第i个点对应的是第2行第f[i]个点 假设ij, 两条线(i, f[i])和(j, f[j])的充要条件是f[i]f[j], 因此问题变成了 求f的最长上升子序列 时间复杂度为O(nlogn) 变形2: 两排列的LCS 给1~n的两个排列p1, p2 求p1和p2的最长公共子序列 例: 1 5 3 2 4 ? 5 3 4 2 1 分析 算法一: 直接套用LCS算法, 时间O(n2) 算法二: 注意到把两个排列做相同的置换, LCS不变, 可以先把p1排列为1,2,3…,n 1 5 3 2 4 ? 1