求最长公共子序列(序列型DP) 解题日志

求最长公共子序列(lcs

【问题描述】

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij = yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

对给定的两个字符序列,求出他们最长的公共子序列。

【输入格式】

第1行为第1个字符序列,都是大写字母组成,以.结束。长度小于5000。

第2行为第2个字符序列,都是大写字母组成,以.结束,长度小于5000。

【输出格式】

输出上述两个最长公共自序列的长度。

【输入输出样例】

lcs.in

ABCBDAB.

BACBBD.

 

lcs.out

4

 

dp[i][j]表示X的前i个字符比对到Y的前j个字符的最长公共子序列

dp[i][j]= max(dp[i-1][j-1]+1(xi==yj), dp[i-1][j], dp[i][j-1] )

初始化:dp[0][0]=0;

输出:dp[n][m];

char X[];

scanf(“%s”, X+1);

n=strlen(X+1);  //求长度。

【代码日志】

#include<bits/stdc++.h>
using namespace std;
void FUCK(string name){
	string i=name+".in";
	string o=name+".out";
	freopen(i.c_str(),"r",stdin);
	freopen(o.c_str(),"w",stdout);
}
string a,b;
int dp[5001][5001];
int main(){
	FUCK("lcs");
	//program here
	cin>>a>>b;
	dp[0][0]=0;
	for(int i=1;i<a.size();i++){
		for(int j=1;j<b.size();j++){
			dp[i][j]=0;
			if(a[i-1]==b[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}
			if(dp[i-1][j]>dp[i][j]){
				dp[i][j]=dp[i-1][j];
			}
			if(dp[i][j-1]>dp[i][j]){
				dp[i][j]=dp[i][j-1];
			}
		}
	}
	cout<<dp[a.size()-1][b.size()-1]<<endl;
	return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注