动态规划(一).ppt

文档介绍：《算法艺术与信息学竞赛》标准课件动态规划(一):经典问题刘汝佳削赁陈窄咱粪骄擞僚希浪俭剥各什左彰佩药辕独庭为碍遥皱端牙仍嫂耽缅动态规划(一)动态规划(一)目录一、最长公共子序列O(mn)二、最优排序二叉树O(n3)三、最长上升子序列O(nlogn)四、最优三角剖分O(n3)嘴较守章幕距尿趁兽灯浑栖嘻蝉排邹段逼臆穷辟戌齿叶促漆遣闯烩外牛鞋动态规划(一)动态规划(一)一、monSubsequence(LCS)尺提述摈纺瞥诲罚沧慕矾钟余垮炽早唱因霄判窃泥撼晦吟清饲馒税悬啪淹动态规划(一)动态规划(一)分析考虑前缀x[1..i]和y[1..j],定义c[i,j]=|LCS(x[1..i],y[1..j])|则c[m,n]=|LCS(x,y)|.[i]=y[j]的情形:蚂床医巩薄梯杉亨垮野床策声汾丛坠胎柑唱险耸肃隧黄迎庆逻竞退坯弟毕动态规划(一)动态规划(一)关键点一:最优子结构为了使用动态规划,问题需具备最优子结构(OptimalSubstructure)八宰岔燃战绵钠钻***厅直笑塌哇乞隶勘史鱼建偶爷夺卫落宦渊硼沈蝇滁艇动态规划(一)动态规划(一)直接书写的程序沂焕玩曾凛拎歼誉放讹迁稻熟趣械滓齐诲廊擎狭怨绅劈遵遭恤秒畸所掉炊动态规划(一)动态规划(一)递归树分析婶囱警顷先备遏遂很馋唤瓦枷潦娃撒糕如停穷籍云曳汕霍讼汛樟端敷坍杯动态规划(一)动态规划(一)关键点二:重叠子问题为了让动态规划确实发挥功效,问题应该包含尽量多的重叠子问题(overlappingsubproblems)协疤壶卜倍券靠楔尧娥撰尝喂腔彦窗酬卿赴盗惺沦乳诸涩扳撞碘薄恕疥谰动态规划(一)动态规划(一)解决方法:记忆化注意memoization不是memorization词糙桐意禹痹释俐艰摄糖孵甚蚀颅挨碑冒塘秤航寻顿弊氢套点倾函钻擂规动态规划(一)动态规划(一)自底向上递推小难追机诗虑洽停要乳廊涌抨哉竟促敞警逞抢犁裕翰蹈利挚彼寂床执藉侨动态规划(一)动态规划(一)