求教,求解LCS长度
  • 板块学术版
  • 楼主_pwl
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/9/25 15:46
  • 上次更新2023/11/5 12:39:21
查看原帖
求教,求解LCS长度
250609
_pwl楼主2020/9/25 15:46

RT,是一道模板题 问题在代码中

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
inline void read(int &x){
	int f=1;
	char ch=getchar();
	x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
int len1,len2;
int dp[1001][1001]={0};
string str1,str2;
inline void LCS(int p,int q){
	for(int i=1;i<=p;i++){
		for(int j=1;j<=q;j++){
			if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;	//请问为什么是i-1和j-1 
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
}
int main(){
	cin>>str1>>str2;
	len1=str1.size();
	len2=str2.size();
	LCS(len1,len2);
	printf("%d",dp[len1][len2]);
	return 0;
}

谢谢

2020/9/25 15:46
加载中...