资源描述:
《《算法艺术与信息学竞赛》标准课件.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,保持原字符的顺序不变,至少要加几个字符才能变成回文词?例:abfcbfaafbcfcbfa分析红、绿色表示原字符,白色为新增字符显然,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]个点假设i12、法一:直接套用LCS算法,时间O(n2)算法二:注意到把两个排列做相同的置换,LCS不变,可以先把p1排列为1,2,3…,n1532412345即映射52,24,45,p2作同样置换5