动态规划经典问题

《动态规划经典问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划经典问题刘汝佳目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)五、最大m子段和O(mn)六、0-1背包问题O(min{nc,2n,n1.44n})七、最优排序二叉树O(n2)八、最优合并问题O(nlogn)一、最长公共子序列•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})•更进一步的,可以只保留一行,每次用单独的变量x保留d[i-1,j],

7、则递推方程为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、优排序二叉树•给出关键码-频率对照表（升序排列）•问题：把哪个关键码做为根？则左右子树可以递归往下做ABCDEFGHIJKLMNOP..231081230514182024117222210..分析•用递归来思考，但用递推来做•先考虑两个结点的情形分析•可以用矩阵来保存结果•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矩阵递

9、归地构造出最优树分析•时间复杂度：计算每个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[

10、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

11、尽量多的线,两两不交叉分析•设与第1行第i个点对应的是第2行第f[i]个点•假设i