动态规划经典问题
刘汝佳
目录
一、最长公共子序列O(mn)
二、最优排序二叉树三、最长上升子序列四、最优三角剖分五、最大六、七、最优排序二叉树八、最优合并问题O(n3)
O(nlogn)O(n3)m子段和O(mn)
背包问题O(min{nc, 2n, n1.44O(n2)
O(nlogn)
n})0-1一、最长公共子序列
?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)
动态规划经典问题 - 图文
动态规划经典问题刘汝佳目录一、最长公共子序列O(mn)二、最优排序二叉树三、最长上升子序列四、最优三角剖分五、最大六、七、最优排序二叉树八、最优合并问题O(n3)O(nlogn)O(n3)m子段和O(mn)背包问题O(min{nc,2n,n1.44O(n2)O(nlogn)n}
推荐度：
点击下载文档文档为doc格式
