51Nod 1006-最长公共子序列Lcs

1006 最长公共子序列Lcs 

基准时间限制：1 秒 空间限制：131072 KB 分值: 0  难度：基础题

题目链接

 收藏

 关注

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出最长的子序列，如果有多个，随意输出1个。

abcicba
abdkscab

abca

题解：动态规划的基础题，白皮书上写的有一个是求最长公共子序列的个数，这个是输出最大子序列。做法就是先打一个表，再判断是否可以满足a[i]=b[j]的条件。我有一个地方卡了很久，就是那个判断是否相等的条件，因该是a[i-1]，之前我写成a[i]。

#include<bits/stdc++.h>
using namespace std;
int dp[1000+50][1000+50];
int main()
{
	char a[1000+50];
	char b[1000+50];
	char c[1000+50];
	scanf("%s",a);
	scanf("%s",b);
	int len1=strlen(a),len2=strlen(b);
	for(int i=0;i<len1;i++)
	{
		for(int j=0;j<len2;j++)
		{
			if(a[i]==b[j])
			{
				dp[i+1][j+1]=dp[i][j]+1;
			}
			else
			{
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
			}
		}
	}
	int i=len1,j=len2,k=0;
	while(i>0&&j>0)
	{
		if(a[i-1]==b[j-1])
		{
			c[k++]=a[i-1];
			i--;
			j--;
		}else
		if(dp[i-1][j]>dp[i][j-1])
		{
			i--;
		}else
		{
			j--;
		}
	}
	for(int ii=k-1;ii>=0;ii--)
	printf("%c",c[ii]);
	return 0;
}