算法 最长公共子序列.docx
版权申诉
98 浏览量
2022-05-08
11:46:06
上传
评论
收藏 14KB DOCX 举报
最长公共子序列
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()
资源评论
