《github一天一道算法题》：动态规划法解决最长公共子序列（LCS）有关问题的最简单方法

《github一天一道算法题》：动态规划法解决最长公共子序列（LCS）问题的最简单方法

<pre name="code" class="cpp">/*
 * copyleft@hustyangju
 * 问题：longest common subsequece problem
 * 思路：从底往上，利用动态规划，划分子问题，利用LCS子问题的长度变化，求得LCS
 * 时间复杂度O（m*n）
 * 空间复杂度O（m*n）
*/
#include <iostream>
//#include <string>
using namespace std;

class lcs
{
  public:
    lcs(char *a,int m, char *b, int n):_a(a),a_length(m),_b(b),b_length(n)//传递两个字符串，并传递其长度
    {
        for(int i=0;i<100;i++)
        {
            for(int j=0;j<100;j++)
                count[i][j]=0;
        }
        if(max(sizeof(a),sizeof(b))>100)
            cout<<"error! count[100][100] too small!"<<endl;

    }
    ~lcs()
    {
        if(_a!=NULL)
        {
            delete _a;
            _a=NULL;
        }
        if(_b!=NULL)
        {
            delete _b;
            _b=NULL;
        }
    }
void get_lcs();
private:
    char *_a;                //字符串一
    int a_length;             //长度
    char *_b;                //字符串二
    int b_length;            //长度
    int count[100][100];     //LCS长度二维状态数组
};

/*              0                                  i=0 or j=0
 *
 *count[i][j]=  count[i-1][j-1]+1                  X[i-1]==Y[j-1] and i ,j>0
 *
 *              max(count[i-1][j],count[i][j-1])   X[i-1]!=Y[j-1] and i ,j>0
*/
void lcs::get_lcs()
{
    int m=a_length;
    int n=b_length;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
           if(*(_a+i-1)==*(_b+j-1))
           {
               count[i][j]=count[i-1][j-1]+1;
           }
           else if(count[i-1][j]>=count[i][j-1])
           {
               count[i][j]=count[i-1][j];
           }
           else
               count[i][j]=count[i][j-1];
        }//for
    }
    /*打印LCS长度二维数组*/
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<count[i][j]<<" ";
        cout<<endl;
    }
    /*LCS 长度*/
    cout<<"LCS length:"<<count[m][n]<<endl;
    /*输出LCS，这里有一个技巧，就是分别增加一个字符串的长度和另外一整个个字符串比较，LCS长度增加1，说明该位置是LCS的一个字符*/
    cout<<"LCS is:"<<endl;
    for(int p=1;p<=n;p++)
    {
        if(count[m][p]-count[m][p-1]==1)
            cout<<*(_b+p-1)<<" ";
    }
    cout<<endl;
}

int main()
{
    char a[]="ABCBDAB";
    cout<<a<<endl;
    char b[]="BECBD";
    cout<<b<<endl;
    lcs mylcs(a,sizeof(a)-1,b,sizeof(b)-1);
    mylcs.get_lcs();

}

结果：