在两个字符串中，有些字符会一样，可以形成的子序列也有可能相等，因此，长度最长的相等子序列便是两者间的最长公共字序列，其长度可以使用动态规划来求。

以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。

借用《算法导论》中的推导图：

创建 DP数组C[][];

         图中的空白格子需要填上相应的数字（这个数字就是c[i][j]的定义，记录的LCS的长度值）。填的规则依据递归公式，简单来说：如果横竖（i,j）对应的两个元素相等，该格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化该表：

dp[i][j]代表了字符串A里i之前的字符串 和 字符串B里j之前的字符串的最大公共子序列的

s a d        s t o r   y

   a d min s   o r r y  

红色的为匹配的情况，我们发现，当Xi=Yi时，为dp[i][j]+1;

当不相等时，为max( dp[i][j-1] , dp[i-1][j] ),例如当d和m不匹配时，就会寻找前面最大匹配情况，为max( 2 , 1 )这时就会选择a d a d这组匹配值向后叠加使用，直到出现更大的值来替换他（dp[i][j]代表了字符串A里i之前的字符串 和 字符串B里j之前的字符串的最大公共子序列的，这代表应该向后赋值和叠加的情况）

         

          然后，一行一行地从上往下填：

         

          S1的元素3 与 S2的元素3 相等，所以 c[2,1] = c[1,0] + 1。继续填充：

          

            S1的元素3 与 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])，图中c[1,2] 和 c[2,1] 背景色为浅黄色。

            继续填充：

            

            

             

               中间几行填写规则不变，直接跳到最后一行：

              

                          

 

                至此，该表填完。根据性质，c[8,9] = S1 和 S2 的 LCS的长度，即为5。

得到公式

代码
 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
 
const int MAXN = 1005;
 
int DP[MAXN][MAXN];
 
int main()
{
	string a;
	string b;
	while(cin >> a >> b)
	{
		int l1 = a.size();
		int l2 = b.size();
		memset(DP, 0, sizeof(DP)); 
		for(int i = 1; i <= l1; i++)
			for(int j = 1; j <= l2; j++)
				if(a[i - 1] == b[j - 1])
					DP[i][j] = max(DP[i][j], DP[i - 1][j - 1] + 1);
				else
					DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]);
		printf("%d\n", DP[l1][l2]);
	}
	return 0;
}