解决最长公共子序列问题：

求解的方法如图所示：

例如，设所给的两个序列为X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS计算出的结果如下图所示：

其模板可以写成

void lcss(){    int i,j;    int sizex=str1.length();    int sizey=str2.length();    for(i=0;i<=sizex;i++)        lcs[i][0]=0;    for(i=0;i<=sizey;i++)         lcs[0][i]=0;        for(i=1;i<=sizex;i++)            for(j=1;j<=sizey;j++)            {                if(str1[i-1]==str2[j-1])                    lcs[i][j]=lcs[i-1][j-1]+1;                else                    lcs[i][j]=lcs[i-1][j]>=lcs[i][j-1]?lcs[i-1][j]:lcs[i][j-1];            }                          cout<<lcs[sizex][sizey]<<endl;  }  

View Code

也可以将数组进行压缩：

memset(lcs,0,sizeof(lcs));        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)            {                if(str1[i-1]==str2[j-1])                    lcs[i%2][j]=lcs[(i-1)%2][j-1]+1;                else                    lcs[i%2][j]=lcs[(i-1)%2][j]>lcs[i%2][j-1]?lcs[(i-1)%2][j]:lcs[i%2][j-1];            }    printf("%d\n",lcs[n%2][n]) ; 

View Code

 

 

训练题目：

http://acm.hdu.edu.cn/diy/contest_show.php?cid=24575

8月26———动态规划lcs