算法知识之最长公共子序列问题(动态规划)(二)
(测试用例见结果图)
2.代码
这里涉及到一个新的问题：就是使用上面所叙述的填充表格来实现动态规划,其中c[m,n]记录的是当前序列的最长子序列长度;还需要引用一个吧b[m,n]表来寻找所有最长公共子序列,并把结果存入到result[]数组中.其中最重要的代码就是两个实现的函数,如下:
第一个LSCLength函数是求最长公共子序列长度的函数,并在该函数中填充c[m][n]和b[m][n].
[cpp]
//函数：计算最优值
//参数：m字符串X长 n字符串Y长 X字符串 Y字符串 b标志数组寻找所有字符串用
int LSCLength( int m, int n, char *X, char *Y, int b[][100] )
{
/*计算最长公共子序列的长度*/
int num[100][100];
int i,j;
int sum;
/*清零*/
for( i=0 ; i<=m ; i++ )
{
for( j=0 ; j<=n ; j++ )
{
num[i][j]=0;
b[i][j]=0;
}
}
/* 递归结构-动态规划并输出 */
for( i=1 ; i<=m ; i++ )
{
for( j=1 ; j<=n ; j++ )
{
if( X[i]==Y[j] ) {
num[i][j]=num[i-1][j-1]+1;
b[i][j]=1;
}
else if( num[i-1][j]>num[i][j-1] ) {
num[i][j]=num[i-1][j];
b[i][j]=2;
}
else if( num[i-1][j]
num[i][j]=num[i][j-1];
b[i][j]=3;
}
else {
num[i][j]=num[i][j-1];
b[i][j]=4;
}
}
}
sum = num[m][n];
printf("最长公共子序列的长度：%d\n",sum);
//输出c[m][n]表
printf("\n");
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
printf("%d ",num[i][j]);
}
printf("\n");
}
//输出b[m][n]表
printf("\n");
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
printf("%d ",b[i][j]);
}
printf("\n");
}
return sum;
}
第二个DisplayLSC函数是通过b[m][n]递归计算所有最长公共子序列,并存储至result数组中.
[cpp]
//定义全局变量用于保存结果result 结果个数保存为count
char result[100];
int count=0;
//函数：计算所有最长公共子序列
//参数：m字符串X的长度 n字符串Y的长度 b标志数组 current_len当前长度 max_len最长公共子序列长度
void DisplayLSC(int i,int j,char *X,int b[][100],int current_len,int max_len)
{
int s;
//采用递归的算法求解所有长度
if(i==0 || j==0) //为0时输出结果并返回
{
for(s=0;s
{
printf("%c ",result[s]);
}
printf("\n");
count++;
return;
}
if(b[i][j]==1)
{
current_len--;
result[current_len]=X[i];
DisplayLSC(i-1,j-1,X,b,current_len,max_len);
}
else
{
if(b[i][j]==2)
{
DisplayLSC(i-1,j,X,b,current_len,max_len);
}
else
{
if(b[i][j]==3)
{
DisplayLSC(i,j-1,X,b,current_len,max_len);
}
else
{
DisplayLSC(i,j-1,X,b,current_len,max_len);
DisplayLSC(i-1,j,X,b,current_len,max_len);
}
}
}
}
3.结果