Problem Description 给定两个序列X= Input 输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。 Output 每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。 Sample Input ABCBDAB BDCABA Sample Output 4
这算是动态规划最经典的一道题目了，还有矩阵链乘法。
#include<stdio.h> #include<memory.h> #include<iostream> using namespace std; int s[502][502]; string s1, s2; /* 关键在于对于两个序列的某一点s1[i]与s2[j]， 如果两者相等，那么到i,j为止，最长子序列等于s1(0~i-1) 与 s2(0~j-1) 的最长子序列（LCS） + 1； 如果两者不相等，那么到i,j为止，最长子序列等于 LCS(s1(0~i-1),s2(0,j))或者LCS(s1(0~i),s2(0~j-1)) 至于取哪一个，自然是取之中较大的那一个了 */ int main(){ while(cin>>s1){ cin>>s2; int l1 = s1.length(); int l2 = s2.length(); s1 = ' ' + s1; s2 = ' ' + s2; //这样只是为了让s1[1]就是s1的第一个字符，表示比较清楚，也可以不使用这种方式 memset(s, 0, sizeof(s)); for(int i=0; i<=l1; i++) s[i][0] = 0; for(int i=0; i<=l2; i++) s[0][i] = 0; for(int i=1; i<=l1; i++){ for(int j=1; j<=l2; j++){ if(s1[i]==s2[j]) s[i][j] = s[i-1][j-1] + 1; else s[i][j] = max(s[i-1][j], s[i][j-1]); } } /*for(int i=0;i<=l1;i++){ for(int j=0; j<=l2; j++) cout<<s[i][j]<<" "; cout<<endl; }*/ //这个矩阵就是整个的过程 cout<<s[l1][l2]<<endl; } }