算法 最长公共子序列

算法 最长公共子序列

最长公共子序列

1题目分析

两个序列的最长公共子序列的长度为最优值，利用动态规划法

2算法构造

引入二维数组C[i,j]记录Xi = < xl,x2 , … , xi>和Yj =二< y1 ;y2 , ,…, yj > 根据子问题最优值的递归关系，可自底向上建立递推关系如下：

当 i = 0 , j = 0 时 , c[i][j] = 0

当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1

当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

3算法实现

#include <iostream>

#include <string>

using namespace std;

//计算最优值

void LCSLength(int m,int n,char *y,char *x,int **c,int **b)

{

int i,j;

for(i=1;i<=m;i++)c[i][0]=0;

for(j=0;j<=n;j++)c[0][j]=0;

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

for(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;}

}

}

//构造最长公共子序列

void LCS(int i,int j,char *x,int**b)

{

if(i==0||j==0)return;

if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}

else if(b[i][j]==2)LCS(i-1,j,x,b);

else LCS(i,j-1,x,b);

}

//主函数

int main()

{