网站开发的工作职责,国内免费无版权视频素材网站,免费个人网页空间ftp,wordpress手机投稿题目描述 现有两个字符串s1与s2#xff0c;求s1与s2的最长公共子序列的长度#xff08;子序列可以不连续#xff09;。 输入描述 第一行为字符串s1#xff0c;仅由小写字母组成#xff0c;长度不超过100#xff1b; 第一行为字符串s2…题目描述 现有两个字符串s1与s2求s1与s2的最长公共子序列的长度子序列可以不连续。 输入描述 第一行为字符串s1仅由小写字母组成长度不超过100 第一行为字符串s2仅由小写字母组成长度不超过100。 输出描述 输出一个整数表示最长公共子序列的长度。 样例1
输入 sadstory adminsorry 输出 6 解释 最长公共子序列为adsory长度为6。 #includebits/stdc.h
using namespace std;
const int MAXN 100;
string s;
string t;
int dp[MAXN][MAXN];//记录子问题的解dp[i][j]表示字符串s的前i个字符和字符串t的前j个字符的最长公共子序列长度
int main(){cin s t;int ls s.length();int lt t.length();for(int i1;ils;i)//填表方式用i和j作为索引访问数组时候从1开始for(int j1;jlt;j){//两层循环遍历s和t的每个字符比较是否相等if(s[i-1] t[j-1]){//第i-1个和第j-1个相等dp[i][j] dp[i-1][j-1] 1;//表示当前位置位置的最长公共子序列长度比前一个位置多1}else if(s[i-1] ! t[j-1]){//如果字符不相等dp[i][j] max(dp[i-1][j],dp[i][j-1]);//表示当前位置的最长公共子序列长度与前一个位置保持一致}}}printf(%d,dp[ls][lt]);//即s1和s2的最长公共子序列长度}
