A1476 最长公共子序列LCS

思路老师讲过了，不过多赘述，具体看实操

#include<bits/stdc++.h>
using namespace std;
int dp[4016][4016];//dp数组，dp[a][b]表示第一个序列的第一~第a个数组成的子序列与第二个序列的第一——第b个数组成的子序列的LCS长度（怎么感觉语法有点绕？）
string s,t,ans="";//因为我们最后要根据dp数组推回，所以我们需要提前备好字符串ans
int main(){
	cin>>s>>t;//输入两个字符串
	int n=s.length();//长度
	int m=t.length();
	dp[0][0]=0;//当两个字符串长度均为0时，不用说，LCS肯定为0
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i-1]==t[j-1]){//这里可以省去将字符串整体后移一位这一步
				dp[i][j]=dp[i-1][j-1]+1;//若相同，则LCS长度+1
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//自己靠不住了，找个大的连上
			}
		}
	}
	int i=n,j=m;
	while(i&&j){
		if(s[i-1]==t[j-1]){
			ans=s[i-1]+ans;
			i--;j--;//如果等于，那么毫无疑问，这里就是LCS的一部分（注意不要把s[i-1]和ans写反，不然还得字符串逆序），再两个字符串同时逆推
		}
		else if(dp[i-1][j]==dp[i][j]){
			i--;//如果上面两者相等，说明i-1时和i时是等效的，因此可以直接过渡
		}
		else if(dp[i][j-1]==dp[i][j]){
			j--;//道理同上
		}
	}//根据dp数组来推，当i，j还不为0时，LCS所包含的字符总有以上三种情况
	cout<<ans<<endl;//输出（endl可以不加）
	return 0;
}

copy一次一个赞，如果这个题解对你有帮助的话，也不妨点个赞啊o(￣▽￣)ｄ