题意：给定两个字符串，让你找出它们之间最长公共子序列（LCS）的长度。
析：很明显是个DP,就是LCS，一点都没变。设两个序列分别为，A1，A2，...和B1，B2..，d（i, j）表示两个字符串LCS长度。
当A[i] = B[j] 时，这个最长度就是上一个长度加1，即：d(i, j) = d(i-1, j-1) + 1;
当A[i] != B[j] 时，那就是前面的最长长度（因为即使后面的不成立，也不会影响前面的），即：d(i, j) = max{d(i-1, j), d(i, j-1)}。
时间复杂度为mn，其中m，n分别为两个序列的长度。
代码如下：
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio> using namespace std;
const int maxn = 1000 + 10;
char s1[maxn], s2[maxn];
int d[maxn][maxn]; int main(){
while(~scanf("%s", s1+1)){
scanf("%s", s2+1);
int len1 = strlen(s1+1);
int len2 = strlen(s2+1); memset(d, 0, sizeof(d));
for(int i = 1; i <= len1; ++i)
for(int j = 1; j <= len2; ++j)
if(s1[i] == s2[j]) d[i][j] = d[i-1][j-1] + 1;
else d[i][j] = max(d[i-1][j], d[i][j-1]); printf("%d\n", d[len1][len2]);
}
return 0;
}