最长公共子序列求解DP

Question

题目 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X和Y，使得对所有的
j
=
0
,
1
,
⋯
 
,
k
−
1
j=0,1,⋯,k−1 ，有
x
i
j
=
y
j
x
ij
​
=y
j
​
。例如，
X
=
"ABCBDAB"
X="ABCBDAB" ，
Y
=
"BCDB"
Y="BCDB" 是 X 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。X 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。
##**这道题的解析里面假如S1的最后一个元素与S2的最后一个元素相等，那么S1和S2的LCS就等于{S1减去最 后一个元素}与{S2减去最后一个元素} 的LCS再加上S1和S2相等的最后一个元素（如下图）

S1 A B C B D A B S2 B D C A B A

假如S1的最后一个元素与S2的最后一个元素不等（本例子就是属于这种情况），那么 S1和S2的LCS就等于：{S1减去最后一个元素}与S2的LCS， {S2减去最后一个元素}与S1的 LCS 中的最大的那个序列。**请问啥意思啊？

Answer 1

温馨提醒：如果我的回答对你有帮助，请点击旁边的采纳按钮，谢谢

（1）子序列：一个序列X ＝ x1x2...xn,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。
例如：对序列 1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。在这里需要提醒大家，子序列不是子集，它和原始序列的元素顺序是相关的。

（2）公共子序列：如果序列Z既是序列X的子序列，同时也是序列Y的子序列，则称它为序列X和序列Y的公共子序列。空序列是任何两个序列的公共子序列。

 （3）最长公共子序列：X和Y的公共子序列中长度最长的（包含元素最多的）叫做X和Y的最长公共子序列。

  这个问题如果用穷举法时间，最终求出最长公共子序列时，时间复杂度是Ο（2mn），是指数级别的复杂度，对于长序列是不适用的。因此我们使用动态规划法来求解。

刻画最长公共子序列问题的最优子结构
设X=x1x2…xm和Y=y1y2…yn是两个序列，Z=z1z2…zk是这两个序列的一个最长公共子序列。

  1.      如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1，Yn-1的一个最长公共子序列；

  2.      如果xm≠yn，那么zk≠xm，意味着Z是Xm-1，Y的一个最长公共子序列；

  3.      如果xm≠yn，那么zk≠yn，意味着Z是X，Yn-1的一个最长公共子序列。

  从上面三种情况可以看出，两个序列的LCS包含两个序列的前缀的LCS。因此，LCS问题具有最优子结构特征。

递归的定义最优值
从最优子结构可以看出，如果xm=yn，那么我们应该求解Xm-1，Yn-1的一个LCS，并且将xm=yn加入到这个LCS的末尾，这样得到的一个新的LCS就是所求。

  如果xm≠yn，我们需要求解两个子问题，分别求Xm-1，Y的一个LCS和X，Yn-1的一个LCS。两个LCS中较长者就是X和Y的一个LCS。

  可以看出LCS问题具有重叠子问题性质。为了求X和Y的一个LCS，我们需要分别求出Xm-1，Y的一个LCS和X，Yn-1的一个LCS，这几个字问题又包含了求出Xm-1，Yn-1的一个LCS的子子问题。（有点绕了。。。晕没晕。。。。）

   根据上面的分析，我们可以得出下面的公式；

所以：S1和S2的LCS就等于：{S1减去最后一个元素}与S2的LCS， {S2减去最后一个元素}与S1的 LCS 中的最大的那个序列