动态规划之最长公共子序列问题

问题描述

• 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列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的公共子序列。
• 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

这是一个动态规划的题目。对于可用动态规划求解的问题，一般有两个特征：①最优子结构；②重叠子问题

问题求解

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,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的最长公共子序列。

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

例如：
序列str1和序列str2
·长度分别为m和n；
·创建1个二维数组L[m][n]；
·初始化L数组内容为0
·m和n分别从0开始，m++，n++循环：
- 如果str1[m] == str2[n]，则L[m,n] = L[m - 1, n -1] + 1；
- 如果str1[m] != str2[n]，则L[m,n] = max{L[m,n - 1]，L[m - 1, n]}
·最后从L[m,n]中的数字一定是最大的，且这个数字就是最长公共子序列的长度
·从数组L中找出一个最长的公共子序列

寻找最优解

为了递归打印出最长的公共子序列，我们需要再引入一个二维数组b[i][j]。b数组的定义如下：

源程序

定义一个c[i][j]数组用来表示x[0-i]与y[0-j]的最长公共子序列的长度
定义一个b[i][j]数组用来表示c[i][j]与c[i-1][j-1]，c[i-1][j]，c[i][j-1]的关系
第一个字符串定义为char *x
第二个字符串定义为char *y

#include <iostream>
using namespace std;
int b[101][101];//表征c[][]数组的局部关系
int c[101][101];//表征x{0-i}与y{0-j}的最长公共子序列的长度
//LSC函数完成对b，c数组的填充
void LSC(int m,int n,char *x,char *y)
{
    //当其中一个字符串为空串时，最长公共子序列的长度为0
    for(int i=0;i<=m;i++) c[i][0]=0;
    //当其中一个字符串为空串时，最长公共子序列的长度为0
    for(int j=0;j<=n;j++)  c[0][j]=0;
    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;}
    }
}
//PrintLSC函数借助b数组的值递归调用打印出最长公共子序列
void PrintLSC(int i,int j,char*x,char*y)
{
    if(i==0||j==0) return;
    if(b[i][j]==1)
        {PrintLSC(i-1,j-1,x,y);cout<<x[i];}
    else if(b[i][j]==2)
        PrintLSC(i-1,j,x,y);
    else 
        PrintLSC(i,j-1,x,y);
}
int main()
{
    int m,n;
    cin>>m>>n;//用来表示字符串x,字符串y的长度
    char *x = new char[m+1];
    char *y = new char[n+1];
    for(int i=1;i<=m;i++){
        cin>>x[i];
    }
    for(int i=1;i<=n;i++){
        cin>>y[i];
    }
    LSC(m,n,x,y);
    PrintLSC(m,n,x,y);
    return 0;
}