《算法笔记》11.4小节——动态规划专题-＞最长公共子序列（LCS） 问题 A: 最长公共子序列
题目描述
给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？
输入
输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。
输出
对于每组输入，输出两个字符串的最长公共子序列的长度。
样例输入 复制
abcfbc abfcab
programming contest
abcd mnp样例输出 复制
4
2
0分析：不妨设现在是第一个串 s1 的第 i 位，与第二个串 s2 的第 j 位在进行比较。
当 s1[i] == s2[j] 时，可以继续比较 i+1 和 j+1位，最长公共子序列长度 +1。
当 s1[i] != s2[j] 时，问题转化为比较 s1[i-1] 和 s2[j], 以及 s1[i] 和 s2[j-1]，答案取这两个中的较大值。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);clock_t start=clock();#endif //testchar s1[110],s2[110];while(~scanf("%s%s",s1+1,s2+1)){int l1,l2;l1=l2=0;int dp[110][110];for(int i=1;s1[i];++i,++l1)dp[i][0]=0;for(int j=1;s2[j];++j,++l2)dp[0][j]=0;dp[0][0]=0;for(int i=1;s1[i];++i){for(int j=1;s2[j];++j){if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}printf("%d\n",dp[l1][l2]);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}