最长公共子序列-动态规划

定义描述

 若给定序列X={$x_1$,$x_2$,…,$x_m$}，则另一序列Z={$z_1$,$z_2$,…,$z_k$} 是X的子序列，是指存在一个严格递增下标序列{$i_1$,$i_2$,…,$i_k$}使得对于所有j=1,2,…,k有：$z_j$ = $x_{i_j}$ 。

 例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}

 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

 最长公共子序列：例如，序列X={A，B，C，B，D，A，B}，Y={B，D，C，A，B，A} ，{B，C，A}是X与Y的公共子序列，但不是最长公共子序列；{B，C，B，A}也是X与Y的公共子序列，但它是X与Y的最长公共子序列，因为X与Y没有长度大于4的公共子序列。

问题描述

  给定2个序列X={$x_1$,$x_2$,…,$x_m$}和 Y={$y_1$,$y_2$,…,$y_n$}，找出X和Y的最长公共子序列。

分析最优解的结构

 设序列X={$x_1$,$x_2$,…,$x_m$}和Y={$y_1$,$y_2$,…,$y_n$}的最长公共子序列为Z={$z_1$,$z_2$,…,$z_{k-1}$,$z_k$} ，则：

• 2个序列的最长公共子序列包含了它们前缀的最长公共子序列。
• 最长公共子序列问题具有最优子结构性质。
  最优子结构性质：问题最优解，是否包含了子问题的最优解。

(1)当$x_m$=$y_n$

 子问题变为Xm-1 ={$x_1$,$x_2$,…,$x_{m-1}$}和Yn-1 ={$y_1$,$y_2$,…,$y_{n-1}$}的最长公共子序列。

 为了验证整个问题最优解Z是否包含子问题Xm-1和Yn-1最优解，就要验证$Z_{k-1}$={$z_1$,$z_2$,…,$z_{k-1}$}是否是子问题Xm-1和Yn-1的最长公共子序列（即： 验证Zk-1是否是Xm-1和Yn-1长度为k-1的公共子序列）。

 证明：若Xm-1和Yn-1有长度大于k-1的公共子序列W，则将xm加在W尾部产生X和Y的长度大于k的公共子序列，与题干中X和Y的最长公共子序列长度为k矛盾，故Zk-1是Xm-1和Yn-1的最长公共子序列

(2)当$x_m$≠$y_n$,且$z_k$≠$x_m$

 子问题变为Xm-1 ={$x_1$,$x_2$,…,$x_{m-1}$}和Y ={$y_1$,$y_2$,…,$y_n$}的最长公共子序列。

 为了验证整个问题最优解Z是否包含子问题Xm-1和Y最优解，就要验证$Z_k$={$z_1$,$z_2$,…,$z_k$是否是子问题Xm-1和Y的最长公共子序列（即： 验证Z是否是Xm-1和Y长度为k的公共子序列）。

 证明：若Xm-1和Y有长度大于k的公共子序列W，则W也是X和Y的长度大于k的公共子序列，这与Z是X和Y的最长公共子序列矛盾。

(3)当$x_m$≠$y_n$,且$z_k$≠$y_n$

 子问题变为X ={$x_1$,$x_2$,…,$x_m$}和$Y_{n-1}$ ={$y_1$,$y_2$,…,$y_{n-1}$}的最长公共子序列。

 就要验证$Z_k$={$z_1$,$z_2$,…,$z_k$是否是子问题X和Yn-1的最长公共子序列

 证明过程与（2）相似。

2个序列的最长公共子序列包含了它们前缀的最长公共子序列
最长公共子序列问题具有最优子结构性质

子问题的递归结构

 找序列X={$x_1$,$x_2$,…,$x_m$}和Y={$y_1$,$y_2$,…,$y_n$}的最长公共子序列为Z={$z_1$,$z_2$,…,$z_{k-1}$,$z_k$} ，递归执行如下：

(1)若$x_m$=$y_n$

(2)若$x_m$≠$y_n$

a）和 b）这两个公共子序列中较长者即为X和Y的最长公共子序列。

递归结构

 由最优子结构性质建立子问题最优值的递归关系

 用c[i][j]记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中， $X_i$={$x_1$,$x_2$,…,$x_i$}； $Y_j$={$y_1$,$y_2$,…,$yj$}

 当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故C[i][j]=0。

 由最优子结构性质可建立递归关系如下：

子问题重叠性质

 最长公共子序列问题具有子问题重叠性质；

 例如，若xm≠yn，找X和Y的最长公共子序列，要计算Xm-1和Y以及X和Yn-1的最长公共子序列，而这两个都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。

计算最优值

• 子问题空间中，共有θ(mn)个不同的子问题.
• 用动态规划算法自底向上地计算最优值能提高算法的效率。
• 用c[i][j]记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中， $X_i$={$x_1$,$x_2$,…,$x_i$}； $Y_j$={$y_1$,$y_2$,…,$yj$}
• b[i][j]记录c[i][j]由哪一个子问题得到。

核心算法

• 用c[i][j]记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中， $X_i$={$x_1$,$x_2$,…,$x_i$}； $Y_j$={$y_1$,$y_2$,…,$yj$}
• b[i][j]记录c[i][j]由哪一个子问题得到。

三种情况下b[i][j]的取值

构造最长公共子序列

 LCSLength只是计算出最优值，并未给出最优解，然而数组b可用于快速构造两个序列的最长公共子序列：

• b[i][j]=1时表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列加上xi所得到；
• b[i][j]=2时表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同；
• b[i][j]=3时表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。

 根据b的内容打印出最长公共子序列

核心算法

例子

 给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略。求出其最长公共子序列，要求给出过程。

算法的改进

 算法lcsLength和lcs中，可进一步将数组b省去。

• 事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。
• 对于给定的数组元素c[i][j]，可仅借助于c本身确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。

 给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。

参照算法分析：

for (i = 1; i <= m; i++)
     for (j = 1; j <= n; j++) {
         if (x[i]==y[j]) { 
               c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
         else if (c[i-1][j]>=c[i][j-1]) {
               c[i][j]=c[i-1][j]; b[i][j]=2;}
         else {
               	c[i][j]=c[i][j-1]; b[i][j]=3;}
      }
}
1
2
3
4
5
6
7
8
9
10

1. [4,4]开始，此时为2。比较[4,3]和[3,4]，与[4,4]的值相同，说明没有新增公共字符。又[3,4]=[4,3]，从算法中可以看出此时下一步应该是[i-1,j],即[3,4]
2. [3,4]开始,此时为2。比较[3,3]和[2,4]，与[3,4]的值相同，说明没有新增公共字符。又[3,3]=[2,4]，从算法中可以看出此时下一步应该是[i-1,j],即[2,4]
3. [2,4]开始,此时为2。比较[2,3]和[1,4]，有一个与[2,4]相同，说明没有新增公共字符。又[2,3]>[1,4]，从算法中可以看出此时下一步应该是[i,j-1],即[2,3]
4. [2,3]开始,此时为2。比较[2,2]和[1,3]，都与[2,3]不同，说明此时新增了公共字符。从算法中可以看出此时下一步应该是[i-1,j-1],即[1,2]
5. [1,2]开始,此时为2。比较[1,1]和[0,2]，都与[1,2]不同，说明此时新增了公共字符。从算法中可以看出此时下一步应该是[i-1,j-1],即[0,1]
6. 此时x=0,算法结束.

最长公共子序列：｛ＢＣ｝

扩展

 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。

• 事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。
• 用2行的数组空间就可以计算出最长公共子序列的长度。
• 进一步的分析还可将空间需求减至O(min(m,n))。

完整算法

#include<bits/stdc++.h>
using namespace std;
char x[1020], y[1020], z[1020];
int c[1020][1020], b[1020][1020];
int m, n;
void LCSLength()
{
    memset(c, 0, sizeof(c));
    memset(b, 0, sizeof(b));
    for(int i = 1; i <= m; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(x[i] == y[j])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            }
            else if(c[i - 1][j] >= c[i][j - 1])
            {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2;
            }
            else
            {
                 c[i][j] = c[i][j - 1];
                 b[i][j] = 3;
            }
        }
    }
}
void LCS(int i, int j)
{
   if(i == 0 || j == 0)
        return ;
   if(b[i][j] == 1)
   {
       LCS(i - 1, j - 1);
       cout << x[i];
   }
   else if(b[i][j] == 2)
   {
       LCS(i - 1, j);
   }
   else
   {
       LCS(i, j - 1);
   }
}
void Input()
{
    cout<<"请输入第一个序列(字母中间不要空格)：";
    gets(x);

    cout<<"请输入第二个序列(字母中间不要空格)：";
    gets(y);

    m = strlen(x);
    n = strlen(y);
    strcpy(x + 1, x);//为了方便，0号位置不放元素
    strcpy(y + 1, y);
}
int main()
{
  Input();
  LCSLength();
  LCS(m, n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

测试用例

输入
请输入第一个序列(字母中间不要空格)：BCDA
请输入第二个序列(字母中间不要空格)：ABCB

输出
BC