动态规划(一).ppt

文档介绍：《算法艺术与信息学竞赛》标准课件
动态规划(一): 经典问题
刘汝佳
目录
一、最长公共子序列O(mn)
二、最优排序二叉树O(n3)
三、最长上升子序列O(nlogn)
四、最优三角剖分O(n3)
一、最长公共子序列
mon 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
自底向上递推