A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. 
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. 
Input 
abcfbc abfcab
programming contest 
abcd mnp
Output 
4
2
0
Sample Input 
abcfbc abfcab
programming contest 
abcd mnp
Sample Output 
4
2
0
思路：
最长公共子序列，感觉好不容易理解...
记录个位置的序列长度，依次递推，最终结果即为最长序列长度
经过前人总结得如下递推关系：
if(s1[i]==s2[j])
dp[i+1][j+1]=dp[i][j]+1;   //相等时，序列长度+1
else
dp[i+1][j+1]=max( dp[i][j+1] , dp[i+1][j] );     //不等时，序列长度不动，选择同行的上一列或同列的上一行的最大序列长度进行记录，即目前为止的最长序列长度。
代码如下： 
#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int main()
{
    string s1,s2;
    while(cin>>s1)
    {
        cin>>s2;
        int i,j;
        int n,m;
        n=s1.length();
        m=s2.length();
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(s1[i]==s2[j])
                dp[i+1][j+1]=dp[i][j]+1;
                else
                {
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        cout<<dp[n][m]<<endl;
    }
    
}