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

《《算法艺术与信息学竞赛》标准课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、《算法艺术与信息学竞赛》标准课件动态规划(一):经典问题刘汝佳目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)五、最大m子段和O(mn)六、0-1背包问题O(min{nc,2n,n1.44n})一、最长公共子序列LongestCommonSubsequence(LCS)分析考虑前缀x[1..i]和y[1..j],定义c[i,j]=

2、LCS(x[1..i],y[1..j])

3、则c[m,n]=

4、LCS(x,y)

5、.递推公式为很直观.考虑x[i]=y[j]的情形:关键点一:

6、最优子结构为了使用动态规划,问题需具备最优子结构(OptimalSubstructure)直接书写的程序递归树分析关键点二:重叠子问题为了让动态规划确实发挥功效,问题应该包含尽量多的重叠子问题(overlappingsubproblems)解决方法:记忆化注意memoization不是memorization自底向上递推空间优化如果只需要最优值,可以用滚动数组实现按照i递增的顺序计算,d[i,j]只和d[i-1,j]和d[i,j-1]以及d[i-1,j-1]有关系，因此只需要保留相邻两行,空间复杂度为O(min{m,n})更进一步的,可以

7、只保留一行,每次用单独的变量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个关键码

8、和它们的频率，构造让期望比较次数最小的排序二叉树分析定理：最优排序二叉树的子树也是最优排序二叉树给出关键码-频率对照表（升序排列）问题：把哪个关键码做为根？则左右子树可以递归往下做ABCDE231081230FGHIJKLMNOP..514182024117222210..分析用递归来思考，但用递推来做先考虑两个结点的情形分析可以用矩阵来保存结果C[j,k]表示从j到k的关键码组成的最优排序二叉树Root[j,k]记录这棵排序二叉树的根分析考虑三个结点的情形最优值放在C[B,D]中，根放在root[B,D]中分析类似地，更新所有C[j-2

9、,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(

10、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(inti = 0; i < n; i++){i

11、ntj =lower_bound(g, g + n,a[i]) - g;d[i] = j + 1;g[j] =a[i];}变形1:航线问题有两行点,每行n个.第一行点和第二行点是一一对应的,有线连接,如下图所示选择尽量多的线,两两不交叉分析设与第1行第i个点对应的是第2行第f[i]个点假设i

12、法一:直接套用LCS算法,时间O(n2)算法二:注意到把两个排列做相同的置换,LCS不变,可以先把p1排列为1,2,3…,n1532412345即映射52,24,45,p2作同样置换5