子序列就是子序列中的元素是母序列的子集，且子序列中元素的相对顺序和母序列相同。
题目要求便是寻找两个字符串的最长公共子序列。
dp[i][j]表示字符串s1左i个字符和s2左j个字符的公共子序列的最大长度。
注意s1第i个字符为s1[i-1]
于是有递推公式：
对于abcfbc和abfcab两个字符串，求公共子串的最大长度的过程如图：
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1010; 8 char s1[maxn], s2[maxn]; 9 int dp[maxn][maxn]; 10 11 int main(void) 12 { 13 #ifdef LOCAL 14 freopen("1458in.txt", "r", stdin); 15 #endif 16 17 while(cin >> s1 >> s2) 18 { 19 int Lenth1 = strlen(s1); 20 int Lenth2 = strlen(s2); 21 memset(dp, 0, sizeof(dp)); 22 23 int i, j; 24 for(i = 1; i <= Lenth1; ++i) 25 for(j = 1; j <= Lenth2; ++j) 26 { 27 if(s1[i-1] == s2[j-1]) 28 dp[i][j] = dp[i-1][j-1] + 1; 29 else 30 dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 31 } 32 33 printf("%d ", dp[Lenth1][Lenth2]); 34 } 35 return 0; 36 }