C++ 动态规划

解题思路:将每条蓝肽序列的子序列存入字符串数组中,将问题化为寻找最长公共子序列问题

注意事项:

参考代码:

 #include<iostream>
 #include<string>
 #include<vector>
using namespace std;
string s1,s2,t;
void stor(vector<string>& temp,string s){
	int i=0,j=0;
	while(j<s.size()){
		while(j+1<s.size()&&islower(s[j+1])){
			j++;
		}
		t=s.substr(i,j-i+1);
		temp.push_back(t);
		i=j+1,j++;
	}
}
int main(){
	cin>>s1>>s2;
	vector<string> te1,te2;
	stor(te1,s1);
	stor(te2,s2);
	int m=te1.size(),n=te2.size();
	vector<vector<int> > dp(m+1,vector<int>(n+1,0));
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(te1[i-1]==te2[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<dp[m][n];
	return 0;
}