题目描述
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 11 至 55 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
输入描述
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
其中有 ，两个字符串的长度均不超过 10001000。
输出描述
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
输入输出样例
示例
输入
LanQiaoBei
LanTaiXiaoQiao
copy
输出
2
copy
运行限制
最大运行时间：1s
最大运行内存: 128M
#include<iostream> #include<string> #include<vector>//用vector容器存放 using namespace std; string s1,s2,t; void stor(vector<string>& temp,string s)//将s中每个子序列提取出来保存在temp容器中 { int i=0,j=0; while(j<s.size()) { while(j+1<s.size()&&islower(s[j+1]))//islower函数，判断字符串某一位是否是小写字母 { j++; } t=s.substr(i,j-i+1);//将字符串s的从i位开始到j-i+1个字母赋值给t temp.push_back(t);//将t加入temp容器中 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));//二维dp数组进行动态规划 for(int i=1;i<=m;i++)//计算最长公共子序列公式：1.如果两个子序列不相同，就选择左方或者上方最大的数字。2.如果两个序列相同就选择左上方的数+1 { 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; }
主要还是最长公共子序列的动态规划问题
