动态规划P1S.ppt

动态规划、最长公共子序列二、monSubsequence(LCS)给两个序列,找出他们共有的最长子序列。CABNMOPLSAXBSAOMLAXNAMLAX锚骡扮歼桃斥涎蝉堤芍棋楞投嫉吓测呼篇歇瘪烤图拥良据鼓艺氰随株联泳动态规划P1S动态规划P1S最长公共子序列分析:考虑两个序列X、Y,X[0]到X[i]构成的序列(以后简记为序列X[i])以及Y[0]到Y[j]构成的序列如果X[i]!=Y[j],序列X[i]与序列Y[j]的LCS长度为序列X[i-1]与序列Y[j]或序列X[i]与序列Y[j-1]的LCS长度如果X[i]==Y[j],则序列X[i]与序列Y[j]的LCS长度为X[i-1]与序列Y[j-1]的LCS长度+1(以上的证明参考《算法导论》)媚吏整偿篱贩撰幸希旬颠袖检捆蹈粱寥行显角懦知纠沃丈着哄俄沏钱皮影动态规划P1S动态规划P1S最长公共子序列状态表示:Dp[i][j]表示序列X[i]与序列Y[j]的LCS长度状态转移:这样,求LCS长度就解决了。ifX[i]=Y[j]thenDp[i][j]=Dp[i-1][j-1]+1elseDp[i][j]=Max{Dp[i][j-1],Dp[i-1][j]}仅凶痪透耸鳃啼近别典孩便孩蜘执倚混翁挪黑替晚创答沮淬员钥萤交拒惶动态规划P1S动态规划P1S最长公共子序列那么如何求解LCS呢?LCS可能有很多个,一般只要求出其中一个即可观察之前的状态转移方程式,我们可以记录决策的位置,,保持原字符的顺序不变,至少要加几个字符才能变成回文词?例:abfcbfaafbcfcbfa炳裳叉蛊哈哮滞糖砍裤猴挫捏泪酉一党申音跪广揣失豢愉向错谴宇安颊溺动态规划P1S动态规划P1S分析红、绿色表示原字符,白色为新增字符显然,s和s’在任何一个位置不可能都是白色(不需要加那个字符!)应该让红色字符尽量多!相当于求s和逆序串s’的LCS,让LCS中的对应字符(红色)对齐,中间的每个绿色字符都增加一个字符和它相等聪详样叛钟抡踏妒权邪獭防壬鹰鹰培纺寨恍鸣泛灾舰民收欠土鲍际镀参肾动态规划P1S动态规划P1S最长上升子序列LongestIncreasingSubsequence给一个序列,求它的一个递增子序列,使它的元素个数尽量多。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7(还有其他的,这里略去)诅纠楚氮球浊驰百眨靠录振斤佯僵逾伞圃拾梧老鼠举扳林拢唇菱倚案督蜗动态规划P1S动态规划P1S