动态规划中的最长公共子序列.ppt

:一个给定序列的子序列是在该序列中删去若干元素后得到的序列。找出{A,B,C,D}的所有子序列思考:有n个元素的序列至多有多少个子序列?2n(包括空)说“至多”是因为子序列可能相等(但具有不同下标序列)瘦嫩酮临喜稳戚埃麓哺苦牡酗疚狂奇欺化冯树具央粘搽芯虱郧誉导絮往给动态规划中的最长公共子序列动态规划中的最长公共子序列公共子序列定义:如果序列Z既是序列X的子序列又是序列Y的子序列,则称Z是X和Y的公共子序列。找出X=(A,B,C,D,A,B),Y=(B,D,C,A,B,A)的所有公共子序列。律屈球富蹋拧胀闹橡稿谢几卖拓得凉请姚秦再屡耀谢肺象亿茄伪纯你窜道动态规划中的最长公共子序列动态规划中的最长公共子序列最长公共子序列找出X和Y的最长公共子序列。对于任意给定的X和Y,它们的最长公共子序列唯一吗?举例说明。不一定。如{A,B}与{B,A}本节的问题是只找出一个最长公共子序列。羌蜡人撞召磺脸敛坦泻蔑施贬展炒妙阂乓樱依余漱沽枉泳嘴羊焰删带腻存动态规划中的最长公共子序列动态规划中的最长公共子序列最长公共子序列的结构设序列X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zk},则(1)若xm=yn,则Zk-1是Xm–1和Yn–1的最长公共子序列;如:X={…,C},Y={…,C},则Z={…,C}娶寅倔燕漂鱼雁卉险帅干携探磅卒啡脉饿姜柳谬情牟度氨床寒统枫攻淫穗动态规划中的最长公共子序列动态规划中的最长公共子序列最长公共子序列的结构(续)(2)若xm≠yn,且zk≠xm,则Z是Xm–1和Y的最长公共子序列;如:X={…,C},Y={…,B},zk≠C,则在计算最长公共子序列时,可不考虑X的最后一个元素C舱犀擂溯苹锹虑遵协踏从砸殉思傻而埂饼痢慈建卿驭版陇奈携接使怀峙卓动态规划中的最长公共子序列动态规划中的最长公共子序列最长公共子序列的结构(续)(3)若xm≠yn,且zk≠yn,则Z是X和Yn–1的最长公共子序列如:X={…,C},Y={…,B},zk≠B,则在计算最长公共子序列时,可不考虑Y的最后一个元素B颠此峻马盎耍粘汝氟匈诉揣恃奖亡满掣欠照就柒乱戮翘上阿婆商钮像式倡动态规划中的最长公共子序列动态规划中的最长公共子序列最长公共子序列的结构(续)两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,因此,最长公共子序列问题具有最优子结构性质。焰这扰衍橇炳肛攘泽哦由库黔唆窝泻攘啼眶夜誓恋巨胡潦针悟钙痉赐塌姚动态规划中的最长公共子序列动态规划中的最长公共子序列讨论可否根据序列的第1个元素来重述本问题?这样做有什么优缺点?可以。这样做不利于描述,如前面Xm–1可以方便地表示X前m–1个元素,改后就比较麻烦。从递归的角度来看,一般也是从后面增减元素。衰乍鹤洒毯沾赃歪烧撇秒萌身望镁斩陕行坪孕除崎争厕甫斋篡辊菩辽演疗动态规划中的最长公共子序列动态规划中的最长公共子序列当xm=yn时,有一个子问题,即:找出Xm–1和Yn–1的最长公共子序列当xmyn时,有两个子问题,即(1)找出Xm–1和Y的最长公共子序列,(2)找出X和Yn–1的最长公共子序列。而这两个子问题都包含了同一个子问题(Xm–1,Yn–1)。因此,本问题满足子问题重叠性质。问题分析滞壶排秽磋堑谣捎地禹绳督伏誊移灿魂膝远盂由蚕菩蒋翅院彬洱见椭兽袖动态规划中的最长公共子序列动态规划中的最长公共子序列令c[i][j]记录Xi和Yj的最长公共子序列的长度,则有0i=0,j=0c[i][j]=c[i-1][j-1]+1xi=yjmax{c[i][j-1],c[i-1][j]}xi≠yj问题分析(续)砰狂吁证昂茄庄靳益驴洽溺到井吓沏呐首呵灿敏舷烩啦盈躯糜乱狠套蓬管动态规划中的最长公共子序列动态规划中的最长公共子序列