算法--- 动态规划之最长公共子序列问题_最长公共子序列的递归结构如下:它的动态规划算法lcslength以x={,,...,}和y={,,.

一.概念梳理

 

二.动态规划

1.最长公共子序列的结构

设序列X={Y1,Y2,...Yn}和Y={Y1,Y2,...Ym}的最长公共子序列为 Z= {Z1,Z2,...Zk},则

（1）若Xm=Yn, 则Zk = Xm = Yn ,且Zk-1 是 Xm-1 和Y n-1 的最长公共子序列。

（2）若Xm!=Yn ,且Zk!=Xm,则Z是Xm-1和Y的最长公共子序列。

（3）若Xm!=Yn ,且Zk!=Yn,则Z是X和Yn-1的最长公共子序列。

LCS问题具有最优子结构 

2.子问题的递归结构

    由最长公共子序列问题的最优子结构性质可知，要找出X={X1,X2,...Xn}和Y={Y1,Y2,...Ym}的最长公共子序列，可按以下方式递归进行。当Xm= Yn 时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上 Xm(=Yn)  即可得X和Y的最长公共子序列，当 Xm !=Yn时，必须解两个子问题，既找出 Xm 和 Yn 的一个最长公共子序列及 X 和 Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的最长公共子序列。

    由此递归结构容易看到，最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算X和Yn-1及Xm-1的最长公共子序列。而这两个子问题都包括一个公共子问题，既计算Xm-1和Yn-1的最长公共子序列。

首先建立子问题最优值的递归关系。用C[ i ][ j ] 记录序列Xi和 Yj的最长公共子序列的长度。其中，X={X1,X2,...Xn}和Y={Y1,Y2,...Ym}。当i=0 或 j=0 时，空序列是 Xi 和 Yj 的最长公共子序列。故此C[ i ][ j ] = 0. 其他情况下，由最优子结构性质可建立递归关系如下：

四.计算最优值

    直接利用递归容易写出计算C[ i ][ j ]的递归算法， 但其计算时间是随输入长度指数增长的，由于在所考虑的子问题空间中，共有0（m,n）个不同的 子问题，因此，用动态规划算法自顶向上计算最优值能提高算法效率。

    计算最长刚刚子序列长度的动态规划算法LCSlength以序列X = {X1,X2,...Xn}和Y = { Y1,Y2,... Ym} 作为输入，输入两个数组C 和B，其中C [ I ][ J ]储存Xi 和 Yj 的最长公共子序列的长度， B [ i ][ j ]记录 C [ i ][ j ]的值是由哪个子问题解得到的，这在构造最长公共子序列时要用到。问题的最优值， 既 X 和 Y 的最长公共子序列的长度记录 C [ M ] [ N  ]中。

void LCSlength(int m , int n, char *x, char *y ,int c[][MAX],int b[][MAX])
{
	int i,j;
	for(i=0;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-1]==y[j-1])
		{
			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;
			 }
		}
		
	}
} 

 五.构造最长公共子序列

    由算法LCSlength计算得到的数组 B 可以用于快速构造序列 X = {X1,X2,...Xn}和Y = { Y1,Y2,... Ym} 的最长公共子序列。首先从      b [ m ] [ n ] 开始，依次在数组b中搜索。当在 b[ i ][ j ] = 1 时，表示Xi 和 Yj 的最长公共子序列是由 X i-1 和 Y j-1 的最长公共子序列在尾部加上 Xi 所得到的子序列。当 b [ i ] [ j ]  = 2 时，表示Xi 和 Y j  的最长公共子序列与 Xi-1 和Y i的最长公共子序列相同。

当 b [ i ] [ j ]  = 3 时，表示Xi 和 Y i  的最长公共子序列与 Xi-1 和Y j-1 的最长公共子序列相同。

    下面的算法LCS实现依据 b的内容打印出Xi 和Yj 的最长公共子序列。通过算法调用LCS 便可打印出序列X和Y的最长公共子序列。

void LCS(int i,int j , char *x,int b[][MAX])
{
	if(i==0||j==0)
		 return ;
	if(b[i][j]==1)
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i-1]<<" ";
	}
	else if (b[i][j]==2)
	{
	LCS(i-1,j,x,b);
	}
		else
		 LCS(i,j-1,x,b); 
	
}

        可见我们在计算长度LCS的时候只要多记录一些信息，就可以利用这些信息恢复出一个最长公共子序列来。就好比我们在迷宫里走路，走到每个位置的时候记录下我们时从哪个方向来的，就可以从终点回到起点一样。

代码一：

#include<iostream>
#include<cstring>
#define MAX 50
using namespace std;
//1  x[m]==y[n]==z[k] z[k-1]是X[m-1] Y[n-1]的最长公共子序列
//2  x[m]!=y[n]  且z[k]！=x[m] Z是x[m-1]与Y的最长公共子序列	
//3  x[m]!=y[n]  且z[k]!= y[n] Z是X和y[n-1]的最长公共子序列 
void LCSlength(int m , int n, char *x, char *y ,int c[][MAX],int b[][MAX])
{
	int i,j;
	for(i=0;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-1]==y[j-1])
		{
			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[][MAX])
{
	if(i==0||j==0)
		 return ;
	if(b[i][j]==1)
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i-1]<<" ";
	}
	else if (b[i][j]==2)
	{
	LCS(i-1,j,x,b);
	}
		else
		 LCS(i,j-1,x,b); 
	
}
int main()
{
	 char x[MAX]={"ABCBDAB"};
	 char y[MAX]={"BDCABA"} ; 
	 int b[MAX][MAX],c[MAX][MAX] ;
	 int m,n;
	 m=strlen(x);
	 n=strlen(y);
	 LCSlength(m,n,x,y,c,b);
	 LCS(m,n,x,b) ;
	return 0;
}

代码二：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int LCSLength(char* str1, char* str2, int **b)
{
	int i,j,length1,length2,len;
	length1 = strlen(str1);
	length2 = strlen(str2);
 
	//双指针的方法申请动态二维数组
	int **c = new int*[length1+1]; //共有length1+1行
	for(i = 0; i < length1+1; i++)
		c[i] = new int[length2+1];//共有length2+1列
 
	for(i = 0; i < length1+1; i++)
		c[i][0]=0;        //第0列都初始化为0
	for(j = 0; j < length2+1; j++)
		c[0][j]=0;        //第0行都初始化为0
 
	for(i = 1; i < length1+1; i++)
	{
		for(j = 1; j < length2+1; j++)
		{
			if(str1[i-1]==str2[j-1])//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=0;          //输出公共子串时的搜索方向
			}
			else if(c[i-1][j]>c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=1;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=-1;
			}
		}
	}
	/*
	for(i= 0; i < length1+1; i++)
	{
	for(j = 0; j < length2+1; j++)
	printf("%d ",c[i][j]);
	printf("\n");
	}
	*/
	len=c[length1][length2];
	for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
		delete[] c[i];
	delete[] c;
	return len;
}
void PrintLCS(int **b, char *str1, int i, int j)
{
	if(i==0 || j==0)
		return ;
	if(b[i][j]==0)
	{
		PrintLCS(b, str1, i-1, j-1);//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串
		printf("%c",str1[i-1]);//c[][]的第i行元素对应str1的第i-1个元素
	}
	else if(b[i][j]==1)
		PrintLCS(b, str1, i-1, j);
	else
		PrintLCS(b, str1, i, j-1);
}
 
int main(void)
{
	char str1[100],str2[100];
	int i,length1,length2,len;
	printf("请输入第一个字符串：");
	gets(str1);
	printf("请输入第二个字符串：");
	gets(str2);
	length1 = strlen(str1);
	length2 = strlen(str2);
	//双指针的方法申请动态二维数组
	int **b = new int*[length1+1];
	for(i= 0; i < length1+1; i++)
		b[i] = new int[length2+1];
	len=LCSLength(str1,str2,b);
	printf("最长公共子序列的长度为：%d\n",len);
	printf("最长公共子序列为：");
	PrintLCS(b,str1,length1,length2);
	printf("\n");
	for(i = 0; i < length1+1; i++)//释放动态申请的二维数组
		delete[] b[i];
	delete[] b;
	system("pause");
	return 0;
}

代码三：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int max1(int m,int n)
{
	if(m>n)
		return m;
	else
		return n;
}
int max2(int x,int y,int z,int k,int m,int n)
{
	int max=-1;
	if(x>max)
		max=x;
	if(y>max)
		max=y;
	if(z>max)
		max=z;
	if(k>max)
		max=k;
	if(m>max)
		max=m;
	if(n>max)
		max=n;
	return max;
}
int LCSLength(char* str1, char* str2, char* str3) //求得三个字符串的最大公共子序列长度并输出公共子序列
{
	int i,j,k,length1,length2,length3,len;
	length1 = strlen(str1);
	length2 = strlen(str2);
	length3 = strlen(str3);
 
	//申请动态三维数组
	int ***c = new int**[length1+1];      //共有length1+1行
	for(i = 0; i < length1+1; i++)
	{
		c[i] = new int*[length2+1];      //共有length2+1列
		for(j = 0; j<length2+1; j++)
			c[i][j] = new int[length3+1];
	}
 
	for(i = 0; i < length1+1; i++)
	{
		for(j = 0; j < length2+1; j++)
			c[i][j][0]=0;
	}
	for(i = 0; i < length2+1; i++)
	{
		for(j = 0; j < length3+1; j++)
			c[0][i][j]=0;
	}
	for(i = 0; i < length1+1; i++)
	{
		for(j = 0; j < length3+1; j++)
			c[i][0][j]=0;
	}
 
	for(i = 1; i < length1+1; i++)
	{
		for(j = 1; j < length2+1; j++)
		{
			for(k = 1; k < length3+1; k++)
			{
				if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
					c[i][j][k]=c[i-1][j-1][k-1]+1;
				else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
					c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]);
				else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
					c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]);
				else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
					c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]);
				else
				{
					c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]);
				}
			}
		}
	}
	len=c[length1][length2][length3];
	for(i = 1; i < length1+1; i++) //释放动态申请的三维数组
	{
		for(j = 1; j < length2+1; j++)
			delete[] c[i][j];
		delete[] c[i];
	}
	delete[] c;
	return len;
}
 
int main(void)
{
	char str1[100],str2[100],str3[100];
	int len;
 
	printf("请输入第一个字符串：");
	gets(str1);
	printf("请输入第二个字符串：");
	gets(str2);
	printf("请输入第三个字符串：");
	gets(str3);
	len=LCSLength(str1,str2,str3);
	printf("最长公共子序列的长度为：%d\n",len);
	system("pause");
	return 0;
}

代码二是让你输入两个序列，然后输出最长公共子序列和长度。