最长公共子序列问题
Description
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

Input
输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

Output
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

Sample
Input
ABCBDAB
BDCABA
Output
4

思路：
乍一看的话不知如何下手，那就暴力出奇迹，考虑两个串最后一个字符，如果相等则说明存在公共子序列长度+1，序列长度各自-1，然后继续递归解决子问题，如果不相等，那么我我们可以删掉一个字符，然后继续递归解决，删除哪边都需要考虑，从这两边中取一个最大值，等到处理到存在空串就可以返回了，空串不存在公共子序列。
递归写法：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 10;
char a[maxn],b[maxn];
int lcs(int len1,int len2){
	if(len1 == 0 || len2 == 0)return 0;
	if(a[len1] == b[len2]){
		return 1 + lcs(len1-1,len2-1);
	}else{
		return max(lcs(len1-1,len2),lcs(len1,len2-1));
	}
}
int main(){
	while(scanf("%s%s",a+1,b+1)!=EOF){
		cout<<lcs(strlen(a+1),strlen(b+1))<<endl;
	}
	return 0;
}

递归深度太高，铁定超时，考虑dp。。
dp[i][j]:串A前i个字符和串B前J个字符的最大公共子序列
转移方程:
dp[i][j] = max(dp[i][j-1],dp[i-1][j]) (a[i] != b[j])
dp[i][j] = 1 + dp[i-1][j-1] (a[i] == b[j])
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 10;
char a[maxn],b[maxn];
int dp[maxn][maxn];
//dp[i][j]:串A前i个字符和串B前J个字符的最大公共子序列
//转移方程:
//dp[i][j] = max(dp[i][j-1],dp[i-1][j]) (a[i] != b[j])
//dp[i][j] = 1 + dp[i-1][j-1] (a[i] == b[j])
int main(){
	while(scanf("%s%s",a + 1,b + 1)!=EOF){
		memset(dp,0,sizeof(dp));
		int n = strlen(a + 1);
		int m = strlen(b + 1);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(a[i] != b[j])
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]) ;
				else dp[i][j] = 1 + dp[i-1][j-1];
			}
		}
		cout<<dp[n][m]<<endl;
	}
	return 0;
}