文档介绍：《算法艺术与信息学竞赛》 标准课件
动态规划(一): 经典问题
刘汝佳
竟才襄碱抹继浆蔷涵疗箔镑恢辑吱诲豌卫绰屋牟帝宁非测吭暴叶巩炒辣沂动态规划(一)动态规划(一)
目录
一、最长公共子序列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
稚然更堡冕玉眠景熊茹铲糙盔镭鸡括贸奄痊昔牺耐赘稻遗击猖郑俊蛹扑淌动态规划(一)动态规划(一)
自底向上递推
混窘验凄义咋磷森歇网衔跋疙官雇骄花繁语茅奄怖馋庆胯锰剃熟象尝披屡动态规划(一)动态规划(一)