动态规划法(十)最长公共子序列(LCS)问题
问题介绍 给定一个序列X=<x1,x2,....,xm>X=<x1,x2,....,xm>,另一个序列Z=<z1,z2,....,zk>Z=<z1,z2,....,zk>满足如下条件时称为X的子序列:存在一个严格递增的X的下标序列<i1,i2,...,ik><i1,i2,...,ik>,对所有的j=1,2,...,kj=1,2,...,k满足xij=zj.xij=zj. 给定两个序列XX和YY,如果ZZ同时是XX和YY的子序列,则称ZZ是XX和YY的公共子序列。最长公共子序列(LCS)问题指的是:求解两个序列XX和YY的长度最长的公共子序列。例如,序列X=<A,B,C,B,D,A,B>X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>Y=<B,D,C,A,B,A>的最长公共子序列为<B,C,B,A><B,C,B,A>,长度为4。 本文将具体阐释如何用动态规划法(Dynamic Programming)来求解最长公共子...