【動态規劃】最長公共子序列問題

題目&&問題分析

給定兩個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},求X和Y的一個最長公共子序列。

算法

動态規劃 vs分治

分治是将一個問題分解為若幹個規模差不多的子問題，然後分别求解，最後把各個問題的解合并得到最終解。動态規劃也是将問題分解，但是不同之處在于動态規劃是先求最小子問題的解，然後在求解較大子問題的時候可以直接用之前的結果。舉個栗子可能會好了解一點，比如你想造一輛車，分治呢就是有了圖紙，然後對着圖紙找需要的零件，最後把零件拼起來就好啦。而動态規劃呢，是先把可能用到的零件找全了，然後開始造車，需要什麼零件直接取就可以。

算法核心

（這部分有參考《趣學算法》，當然也有很多自己的了解和想法，如有bug，歡迎批評指正）

這個問題采用動态規劃，就是先求解出兩個子序列到每一位的子序列的最長公共子序列的長度，就是求{x1}和{y1},{y1,y2},{y1,y2,…}，{x1,x2}和{y1},{y1,y2},{y1,y2,…}…以此類推直到求到X和Y的最長公共子序列。

c[][]:c[i][j]存放的是a[:i]和b[:j]的最長子序列的長度；

a,b:兩個待求解序列；

s:a和b的最長公共子序列；

sk:s的最後一位;

s’:s去掉最後一位所得序列；

其中求解子問題也就是求子序列的最長子序列的長度最重要的就是遞推公式：

if a[i-1]==b[j-1],c[i][j]=c[i-1][j-1]+1;

if a[i-1]!=b[i-1],c[i][j]=max(c[i][j-1],c[i-1][j]);

以上兩個公式均可由反證法得出，

（1）s為a和b的最長公共子序列，當a和b最後一位相同且等于sk的時候，假設s’不是a（m-1）和b(n-1)的最長公共子序列,那麼一定存在一個長度大于|s’|的序列t’為這兩個子序列的最長公共子序列，又因為最後一位相同，那麼t’+{sk}就是a和b的最長公共子序列，可知它的長度一定大于s,那麼t’+{sk}即為a和b的最長公共子序列，與s是a和b的最長公共子序列沖突。可得s’為a(m-1)和b(n-1)的最長公共子序列，是以c[i][j]=c[i-1][j-1]+1;

（2）s為a和b的最長公共子序列，當a和b的最後一位不同且a的最後一位與sk相同時，假設s不是a和b（n-1）的最長公共子序列，那麼一定存在長度大于|s|的序列t為這兩個序列的最長公共子序列，因為b(n-1)加上b的最後一位不會影響最長公共子序列，是以t也是a和b的最長公共子序列，這與s為a和b的最長公共子序列沖突，是以假設不成立。同理可證當a和b的最後一位不同且b的最後一位與sk相同時，s是a(m-1)和b的最長公共子序列。可得c[i][j]=max(c[i-1][j],c[j-1][i])。

算法流程

首先呢需要一個求解子問題也就是各個子序列的最長公共子序列長度的數組c[][],還有記錄c[i][j]計算方法的數組d[][],以便之後得到最長公共子序列。先把這兩個數組的第一行和第一列初始化為0，然後用雙重循環求c[][],同時用d[][]記錄c[][]的計算方法：1表示c[i-1][j-1]+1,2表示c[i][j]=c[i][j-1],3表示c[i][j]=c[i-1][j]。之後用output(int i,int j)通過b[i][j]的值得到c[i][j]的來源，如果b[i][j]==1,就調用output(i-1,j-1),然後輸出a[i-1] (或者是b[j-1]); 如果b[i][j]==2,就調用output(i,j-1);如果b[i][j]==3,就調用output(i-1,j),這樣即可得到最長公共子序列了。

代碼實作

#include<iostream>
using namespace std;
const int maxn=105;

int c[maxn][maxn];//c[i][j]記錄的是a[:i]和b[:j]的最長公共子序列的長度
int d[maxn][maxn];//最長公共子序列的來源，以便最後得到最長公共子序列
string a,b;//存放兩個待比較序列

void LongestSubstr()
{
    int m=a.size(),n=b.size();//兩個序列的長度
    int i,j;
    for(i=0; i<=m; ++i)//将第一行和第一列初始化為0
    {
        c[i][0]=0;
        d[i][0]=0;
    }
    for(j=0; j<=n; ++j)
    {
        c[0][j]=0;
        d[0][j]=0;
    }
    for(i=1; i<=m; ++i)
        for(j=1; j<=n; ++j)
        {
            if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
                d[i][j]=1;//表示最長子序列長度由左上角一位加1得到
            }
            else//當字元不相同的時候
            {
                if(c[i][j-1]>c[i-1][j])//左側大于上側
                {
                    c[i][j]=c[i][j-1];
                    d[i][j]=2;//表示從左側而來
                }
                else//上側大于左側
                {
                    c[i][j]=c[i-1][j];
                    d[i][j]=3;//表示從上側而來
                }
            }
        }
}

void output(int i,int j)
{
          if(i==0||j==0)
                    return ;
          if(d[i][j]==1)
          {
                    output(i-1,j-1);
                    cout<<a[i-1];
          }
          else if(d[i][j]==2)
                    output(i,j-1);
          else
                    output(i-1,j);
}

int main()
{
    cout<<"請輸入第一個序列:";
    cin>>a;
    cout<<"請輸入第二個序列:";
    cin>>b;
    LongestSubstr();
    //cout<<c[a.size()][b.size()]<<endl;
    output(a.size(),b.size());
    return 0;
}

           

一點想法

其實還可以不用d[][]數組來記錄來源，直接在輸出函數中判斷c[i][j]的來源也可以。剛開始我是直接寫的數值判斷，但是這種方法是錯誤的，就像下面這樣：

#include<iostream>
using namespace std;
const int maxn=105;

int c[maxn][maxn];//c[i][j]記錄的是a[:i]和b[:j]的最長公共子序列的長度
//int d[maxn][maxn];//最長公共子序列的來源，以便最後得到最長公共子序列
string a,b;//存放兩個待比較序列

void LongestSubstr()
{
    int m=a.size(),n=b.size();//兩個序列的長度
    int i,j;
    for(i=0; i<=m; ++i)//将第一行和第一列初始化為0
    {
        c[i][0]=0;
        //d[i][0]=0;
    }
    for(j=0; j<=n; ++j)
    {
        c[0][j]=0;
        //d[0][j]=0;
    }
    for(i=1; i<=m; ++i)
        for(j=1; j<=n; ++j)
        {
            if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
                //d[i][j]=1;//表示最長子序列長度由左上角一位加1得到
            }
            else//當字元不相同的時候
            {
                if(c[i][j-1]>c[i-1][j])//左側大于上側
                {
                    c[i][j]=c[i][j-1];
                    //d[i][j]=2;//表示從左側而來
                }
                else//上側大于左側
                {
                    c[i][j]=c[i-1][j];
                    //d[i][j]=3;//表示從上側而來
                }
            }
        }
        for(i=1;i<=m;++i)
        {
                  for(j=1;j<=n;++j)
                    cout<<c[i][j]<<" ";
                  cout<<endl;
        }
}

void output(int i,int j)//WA寫法!!!
{
          if(i==0||j==0)
                    return ;
          if(c[i][j]==c[i-1][j-1]+1)//隻是數值相等不不能保證一定是從左上角而來
          {
                    output(i-1,j-1);
                    cout<<a[i-1];
          }
          else if(c[i][j]==c[i][j-1])
                    output(i,j-1);
          else
                    output(i-1,j);
}

int main()
{
    cout<<"請輸入第一個序列:";
    cin>>a;
    cout<<"請輸入第二個序列:";
    cin>>b;
    LongestSubstr();
    //cout<<c[a.size()][b.size()]<<endl;
    output(a.size(),b.size());
    return 0;
}
           

這種方法為什麼錯誤呢，是因為可能會出現c[i][j]=c[i][j-1]或者是c[i-1][j]而且又有c[i][j]==c[i-1][j-1]+1的情況，在這種情況下，先判斷c[i][j]和c[i-1][j-1]+1是否相等，相等之後進入第一個分支，但是是應該進入第二個或者是第三個分支的，是以會出現錯誤。舉個栗子可能會好了解一點：

a:asd;

b:as;

c[][]:

c 0 1 2

0 0 0 0

1 0 1 1

2 0 1 2

3 0 1 2

我們可以看到c[3][2]==c[2][1]+1,但是其實c[3][2]的來源是c[2][2],直覺的錯誤就是不應該輸入a[2]也就是d,但是卻輸出了，就是因為判斷的時候由于數值巧合地相等是以進入了第一個分支，導緻了輸出錯誤。要解決這個問題，可以直接用循環中決定c[i][j]來源的方法，如下所示：

void output(int i,int j)
{
          if(i==0||j==0)
                    return ;
          if(a[i-1]==b[j-1])//從左上角而來
          {
                    output(i-1,j-1);
                    cout<<a[i-1];
          }
          else if(c[i][j-1]>c[i-1][j])//從上側而來
                    output(i,j-1);
          else
                    output(i-1,j);
}