【算法导论】动态规划之最长公共子序列-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】动态规划之最长公共子序列

简介:         子序列:一个给定序列的子序列就是该给定序列去掉零个或者多个元素后的序列。例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列。
+关注继续查看

        子序列:一个给定序列的子序列就是该给定序列去掉零个或者多个元素后的序列。例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列。注意顺序不能改变

        公共子序列:既是序列X的子序列,又是序列Y的子序列。例如:X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},则序列{B,C,A}是X和Y的一个公共子序列,长度为4;序列{B,C,B,A}是X和Y的一个最长公共子序列(LCS),长度为4.

        当然,我们可以查用穷举法来解决问题,但是,对于一个长度为n的序列,其子序列为2^n,因此时间复杂度为指数形式,当n很大时,显然不合实际。由观察和推导可知,最长公共子序列具有最优子结构性质和重叠子问题性质。因此我们可以通过动态规划算法来找到最长公共子序列,其时间复杂度为O(mn+m+n)。(m,n分别为两个序列的元素个数)

        在下面的程序实现中,我假设两个序列为上面提到的X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},数组b对应于在计算c[i][j]时所选择的最优子问题的解,数组c[i][j]为Xi和Yj的一个LCS的长度,Xi为序列的前i个元素组成的序列,Yj为序列的前j个元素组成的序列.

具体程序如下:

#include<stdio.h>

void Lcs_Length(char *X,char *Y,int n1,int n2,int b[][7],int c[][7]);
void Print_Lcs(char *X,int b[][7],int i,int j);

void main()
{
	char X[]={'A','B','C','B','D','A','B'};
	char Y[]={'B','D','C','A','B','A'};
	int n1=sizeof(X)/sizeof(char);
	int n2=sizeof(Y)/sizeof(char);
	
	int b[8][7]={0};//b[i][j]对应于在计算c[i][j]时所选择的最优子问题的解
	int c[8][7]={0};//c[i][j]为Xi和Yi的一个LCS的长度
	
	Lcs_Length(X,Y,n1,n2,b,c);
	printf("最长公共子序列为:");
    Print_Lcs(X,b,n1,n2);
    printf("\n");
}
/*******************************************************************\
函数功能:计算最长公共子序列的长度,并将结果存储在数组c中
输入:    两个序列X、Y 待存储的数组b,c
输出:    无
\*******************************************************************/
void Lcs_Length(char *X,char *Y,int n1,int n2,int b[][7],int c[][7])
{
	
	for(int i=0;i<n1;i++)
		c[i][0]=0;
	for(int i=0;i<n2;i++)
		c[0][i]=0;
	for(int i=1;i<=n1;i++)
		for(int j=1;j<=n2;j++)
		{
			if(X[i-1]==Y[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;//b用于做标记,便于打印
			}
			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;
			}
		}
}


/*******************************************************************\
函数功能:打印最长公共子序列
输入:    原始序列X、已存储的数组b,i j表示是求X的前i个元素和Y的前j个元素的LCS
输出:    无
\*******************************************************************/
void Print_Lcs(char *X,int b[][7],int i,int j)
{
	if(i==0||j==0)
		return;
	if(b[i][j]==1)
	{
		Print_Lcs(X,b,i-1,j-1);//递归打印
		printf("%c ",X[i-1]);
	}
	else if(b[i][j]==2)
        Print_Lcs(X,b,i-1,j);
	else
		Print_Lcs(X,b,i,j-1);
	
}

上面程序得到的结果数组c和b如下图:

上表中的数字代表长度,例如c[7][6]=4代表序列X的前7个元素组成的序列和序列Y前6个元素组成的序列的最长公共子序列的长度为4.

在程序中为了方便起见,b数组用数字1,2,3分别代表↖,↑,←。


原文:http://blog.csdn.net/tengweitw/article/details/16950673

作者:nineheadedbird



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
动态规划之最长公共子序列求解
关于最长公共子序列(LCS) 最长公共子序列和最长公共子串是有区别的,之前我一直把它们混淆。 最长公共子串举例:假设S1={A,D,C,B,E,X,Q},S2={H,P,D,C,B,E,M,L}那么它们的最长公共子串就是{D,C,B,E}。
2241 0
哈理工oj 1116 解题报告 动态规划-依次输出最长公共子序列的位置
哈理工OJ 1116 选美大赛 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1116 这道题目其实跟其他 2星 求最长递增子序列的题目没什么区别,但标记为2星半,总是有一些提升的,即是在最长递增子序列长度后面再求出子序列的位置  The number is 2: 2 3  我这里有两种方法 第一种,用求最长公共子序列的方法求最长递增子序列,并用路径数组记录位置。
967 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
4065 0
leetcode算法题解(Java版)-15-动态规划(斐波那契)
两种思路,都是递归。第一种是递归的判断每个节点的左右子树的深度是否只相差一以内。第二种做了剪枝处理,当判断到一个子树已经不满足时就返回结果。
2099 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4477 0
【算法与数据结构】最大子序列和问题
(转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目      给定一个数字序列,其中有正有负,确定最大子序列和。用穷举法最好的结果也是时间复杂度O(n²)。后来看到一个聪明的方法,直接使时间复杂度变为O(n)。 2.解法 (1)穷举法        把所有序列都算出来找到最大的。 /* 最大序列和问题的求解,一组数列有正有负
705 0
算法笔记之动态规划(4)
用动态分析解决0-1背包问题 有n个物品,每个物品的重量为w[i],价值为v[i],购物车容量为W。选若干个物品放入购物车,在不超过容量的前提下使获得的价值最大。 问题分析 (1)分析最优解的结构特征(2)建立具有最优值的递归式可以对每个物品依次检查是否放入或者不放入,对于第i个物品的处理状态:用ci表示前i件物品放入一个容量为j的购物车可以获得的最大价值。
1338 0
算法起步之动态规划LCS
原文: 算法起步之动态规划LCS             前一篇文章我们了解了什么是动态规划问题,这里我们再来看动态规划另一个经典问题,最长公共子序列问题(LCS),什么是子序列,我们定义:一个给定序列将其中的0个或者多个元素去掉之后得到的序列就是他的子序列。
910 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
3227 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载