技术教程 编程教程 动态规划 最长公共子序列 LCS,最长单独递增子序列，最长公共子串 正文

动态规划 最长公共子序列 LCS,最长单独递增子序列，最长公共子串

2023-04-28,,

LCS：给出两个序列S1和S2，求出的这两个序列的最大公共部分S3就是就是S1和S2的最长公共子序列了。公共部分

必须是以相同的顺序出现，但是不必要是连续的。

选出最长公共子序列。对于长度为n的序列，其子序列共有2的n次方个，这样的话这种算法的时间复杂度就为指数级

了，这显然不太适合用于序列很长的求解了。

解法二：既然学到了动态规划，就来看看能否用动态规划的思想来解决这个问题。要使用动态规划，必须满足两个条

件：有最优子结构和重叠子问题。为了便于学习，我们先来了解下这两个概念。

如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。当一个递归算法不断地调用同一问题

时，我们说该最优问题包含重叠子问题。

说明：动态规划要求其子问题既要独立又要重叠，这初看上去貌似存在矛盾，其实不然。只是这里说的是两个不同的

概念。独立指的是同一问题的两个子问题不共享资源。而重叠子问题指的是子问题可以作为不同的问题的子问题出

现。

设X = <x1,x2...xm>, Y = <y1,y2...yn>为两个序列，并设Z = <z1,z2...zk>为X和Y的任意一个LCS。可以得出：

1、如果xm = yn，那么zk = xm = yn而且Z(k-1)是X(m-1)和Y(n-1)的一个LCS；

2、如果xm != yn，那么zk != xm蕴含Z是X(m-1)和Y的一个LCS；

3、如果xm != yn，那么zk != yn蕴含Z是X和Y(n-1)的一个LCS。

注：上面的Z(k-1)表示序列Z<z1,z2...zn>,其中n=k-1。其它的X()和Y()也是一样的。

很容易证明上述三点是成立的，详细证明见算法导论。所以LCS具有最优子结构。从上面也可以看出LCS问题中的重

叠子问题的性质。所以我们可以用动态规划来解决LCS问题。由LCS问题的最优子结构可得出递归式：

代码：

#include<iostream>

using namespace std;

#define M 7

#define N 6  

int lcs(char *x,char *y,int c[M+][N+],int b[M+][N+])

{

    int m=M,n=N;

    for(int i=;i<=m;i++)

        c[i][]=;

    for(int j=;j<=n;j++)

        c[][j]=;

    for(int i=;i<=m;i++)

    {

        for(int j=;j<=n;j++)

        {

            if(x[i]==y[j])

            {

                c[i][j]=c[i-][j-]+;

                b[i][j]=;

            }

            else if(c[i-][j]>=c[i][j-])

            {

                c[i][j]=c[i-][j];

                b[i][j]=;

            }

            else

            {

                c[i][j]=c[i][j-];

                b[i][j]=-;

            }

        }

    }

    return c[m][n];

}

void printLcs(int b[][],char *x,int i,int j)

{

    if(i==||j==)

    {

        return;

    }

    if(b[i][j]==)

    {

        printLcs(b,x,i-,j-);

        cout<<x[i];

    }

    else if(b[i][j]==)

    {

        printLcs(b,x,i-,j);

    }

    else

    {

        printLcs(b,x,i,j-);

    }

}

int main()

{

    char x[M+]={'','A','B','C','B','D','A','B'};

    char  y[N+]={'','B','D','C','A','B','A'};

    int c[M+][N+];//注意大小要为strlen+1;因为要存0

    int b[M+][N+];

    cout<<lcs(x,y,c,b)<<endl;

    cout<<"X:"<<x<<endl;

    cout<<"y:"<<y<<endl;

    for(int i=;i<=;i++)

    {

        for(int j=;j<=;j++)

        {

            cout<<b[i][j]<<ends;

        }

        cout<<endl;

    }

    cout<<"最长子序列为:"<<endl;

    printLcs(b,x,,);

}

注意我们的b[0][i] b[i][0]没有存储任何东西。

输出:4

BCBA.

一个问题：

按照这种方式：

char x[M+1]={'0','A','B','C','B','D','A','B'}; //M+1=8

cout<<x输出什么？

答：每次运行都会不同，如X:0ABCBDAB烫烫b'灤?。

为什么，因为用char x[] 这种方式系统不会主动添加字符串结束符\0。如果我们改为

char x[8]="0ABCBDAB";

提示数组越界，为什么？因为用直接用字符串赋值的方式，系统会自动在末尾添加\0，这样，就有了9个字符所有越界了。

上面的代码写的很烂，原因是赋值的方式太烂了，

char x[M+1]={'0','A','B','C','B','D','A','B'}; //M+1=8

需要一个一个赋值。这么做是为了是数组中的x[1]为A。前面的0纯属占位符

下面的代码更好一点：

#include<iostream>

using namespace std;

int c[][];

int b[][];

int lcs(char x[],char y[])

{

    int m=strlen(x);

    int n=strlen(y);

    for(int i=;i<=m;i++)

        c[i][]=;

    for(int j=;j<=n;j++)

        c[][j]=;

    for(int i=;i<=m;i++)

    {

        for(int j=;j<=n;j++)

        {

            if(x[i-1]==y[j-1]) //这是关键点。

            {

                c[i][j]=c[i-][j-]+;

                b[i][j]=;

            }

            else if(c[i-][j]>=c[i][j-])

            {

                c[i][j]=c[i-][j];

                b[i][j]=;

            }

            else

            {

                c[i][j]=c[i][j-];

                b[i][j]=-;

            }

        }

    }

    return c[m][n];

}

void printLcs( char x[],int i,int j)

{

    if(i==||j==)

    {

        return;

    }

    if(b[i][j]==)

    {

        printLcs(x,i-,j-);

        cout<<x[i-1];

    }

    else if(b[i][j]==)

    {

        printLcs(x,i-,j);

    }

    else

    {

        printLcs(x,i,j-);

    }

}

int main()

{

    char x[]="ABCBDAB";

    char y[]="BDCABA";

    cout<<lcs(x,y)<<endl;

    cout<<"X:"<<x<<endl;

    cout<<"y:"<<y<<endl;

    for(int i=;i<=;i++)

    {

        for(int j=;j<=;j++)

        {

            cout<<b[i][j]<<ends;

        }

        cout<<endl;

    }

    cout<<"最长子序列为:"<<endl;

    printLcs(x,,);

}

程序画红线的地方值得注意，因为开始写的时候花了很长时间找错误。

算法导论后面有2个习题：

最长递增子序列：注意没有公共，即只有一个序列。

14.4-5 请给出一个O(n^2)时间的算法，使之能找出n个数的序列中最长的单调递增子序列。

答案：

monotonic：单调的.

序列为X=(x1,x2,x3,x4...)，首先排序X得到X',找出X和X'的最长公共子序列即可。

另一种思维:

　先回顾经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1到i这一段中以i结尾的最长上升子序列的长度（也就是说F[i]代表的串一定要包含第i个字符)，初始时设F[i] = 0(i = 1, 2, ..., len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。

代码：

int main()

{

     char *a="abcdaaabb";

     int n=strlen(a);

     int *c=new int[n];

       c[0]=1;//初始化，以a[0]结尾的最长递增子序列为1

     for(int i=;i<n;i++)

     {

         c[i]=;//c[i]的最小值

         for(int j=;j<i;j++)

         {

             if(a[j]<=a[i] && c[j]+>c[i])

                c[i]=c[j]+;

         }

     }

     int max=;

     for(int i=;i<n;i++)

         if(c[i]>max)

             max=c[i];

     cout<<max<<endl;

     for(int i=;i<=n-;i++)

     {

         cout<<c[i]<<ends;

     }

}

输出: 6

1 2 3 4 2 3 4 5 6         (abcdaaabb)

仔细看c[i]的结果,c[i]表示已a[i]结尾的最大长度。

　　现在，我们仔细考虑计算F[i]时的情况。假设有两个元素A[x]和A[y]，满足

　　　(1)x < y < i (2)A[x] < A[y] < A[i] (3)F[x] = F[y]

　　此时，选择F[x]和选择F[y]都可以得到同样的F[i]值，那么，在最长上升子序列的这个位置中，应该选择A[x]还是应该选择A[y]呢？

　　很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[i-1]这一段中，如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。

　　再根据条件(3)，我们会得到一个启示：根据F[]的值进行分类。对于F[]的每一个取值k，我们只需要保留满足F[i] = k的所有A[i]中的最小值。设D[k]记录这个值，即D[k] = min{A[i]} (F[i] = k)。

　　注意到D[]的两个特点：

　　(1)　D[k]的值是在整个计算过程中是单调不上升的。
　　(2)　D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。

　　利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[i]与D[len]。若A[i] > D[len]，则将A[i]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A[i]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[i]。令k = j + 1，则有D[j] < A[i] <= D[k]，将A[i]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = A[i]。最后，len即为所要求的最长上升子序列的长度。

　　在上述算法中，若使用朴素的顺序查找在D[1]..D[len]查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来的算法相比没有任何进步。但是由于D[]的特点(2)，我们在D[]中查找时，可以使用二分查找高效地完成，则整个算法的时间复杂度下降为O(nlogn)，有了非常显著的提高。需要注意的是，D[]在算法结束后记录的并不是一个符合题意的最长上升子序列！

　　这个算法还可以扩展到整个最长子序列系列问题，整个算法的难点在于二分查找的设计，需要非常小心注意。

（个人觉得上面说的不好理解，下面是好理解一点的：

O（nlgn）的算法。
对于序列Sn，考虑其长度为i的单调子列(1<=i<=m)，这样的子列可能有多个。我们选取这些子列的结尾元素（子列的最后一个元素）的最小值。用Li表示。易知L1<=L2<=…<=Lm {如果Li>Lj(i<j)；那么去掉以Lj结尾的递增子序列的最后j-i个元素，得到一个长度为i的子序列，该序列的结尾元素ak<=Lj<Li;这与Li标识了长度为i的递增子序列的最小结尾元素相矛盾，于是证明了上述结论。}

现在，我们来寻找Sn对应的L序列，如果我们找到的最大的Li是Lm，那么m就是最大单调子列的长度。下面的方法可以用来维护L。
从左至右扫描Sn，对于每一个ai，它可能
(1) ai<L1,那么L1=ai
(2) ai>=Lm，那么Lm+1=ai，m=m+1 (其中m是当前见到的最大的L下标)
(3) Ls<=ai<Ls+1（1<=s<=m)，那么Ls+1=ai；
扫描完成后，我们也就得到了最长递增子序列的长度。从上述方法可知，对于每一个元素，我们需要对L进行查找（类似折半查找）操作，由于L有序，所以这个操作为lgn，于是总的复杂度为O(nlogn)。）

int find2(char L[],int len,char key)//若返回值为x，则a[x]>=key

{

     int low,high,mid;

     low=,high=len;

     while(low<=high)

     {

         mid=(low+high)/;

         if(L[mid]==key)

             return mid;

         else if(L[mid]<key)

             low=mid+;

         else

             high=mid-;

     }

     return low;

}

int main()

{

    char *a="abcdaaabb";

     int n=strlen(a);

       char *L=new char[n];

     int len=;//新开一变量len,用来储存每次循环结束后c中已经求出值的元素的最大下标

       L[]=-;//很巧妙，这里把L[0]设置-1

     L[]=a[];

     len=;///此时只有L[0]求出来，最长递增子序列的长度为1

     int j;

     for(int i=;i<n;i++)

     {

         j=find2(L,len,a[i]);

         L[j]=a[i];

         if(j>len)

             len=j;

     }

     cout<<len<<endl;

}

char *a="abcdaaabb";

输出:4

如果我们求序列,输出L[i]:

for(int i=1;i<=len;i++) { cout<<L[i]<<ends;  }

结果是:abcd

abcdaaabbcdefgh

输出8.

L：abcdefgh

若要递增，非严格，不能采用此种方法。

举例：如aab 采用上面的,错误。

更多：

http://my.oschina.net/leejun2005/blog/117167

动态规划 最长公共子序列 LCS,最长单独递增子序列，最长公共子串的相关教程结束。

《动态规划 最长公共子序列 LCS,最长单独递增子序列，最长公共子串.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!