最长公共子序列问题的定义如下：设有两个序列S1[1..m]和S2[1..n]，需要寻找它们之间的一个最长公共子序列。
例如，我们有如下两个序列：
S1：INTHEBEGINNING
S2：ALLTHINGSARELOST
则S1和S2的一个最长公共子序列为THING。
这里需注意的是，一个子序列不一定必须是连续的，即中间可以被其他字符分开，但它们的顺序必须正确的。另外，最长公共子序列不一定只有一个，而我们要寻找的是其中一个。

一、第一种解法：蛮力策略

⑴ 检查S1[1..m]里面每一个序列。
⑵ 看看其是否也是S2[1..n]里的子序列。
⑶ 在每一步记录当前找到的子序列里面最长的子序列。
分析其运行效率，对每一个子序列的检查需要时间O(n)，而总共有2^m子序列需要检查，因此本算法的最坏时间复杂性是O(n×2^m)。

二、动态规划
利用动态规划寻找最长公共子序列的步骤如下：
⑴ 先寻找最长公共子序列的长度。
⑵ 扩展寻找长度的算法来获得最长公共子序列。
策略：考虑序列S和S的前缀序列。
设c[i,j] = |LCS(S1[1..i], S2[1..j])|，则有c[m,n] = |LCS(S1, S2)|
由此可以总结出通式：

如果设LCS(S1, S2,i,j)表示S1[1..i]和S2[1..j]的最长公共子序列的长度，则有：

计算最长公共子序列长度的动态规划算法如下：

代码：

#include<iostream>
#include<cstring>
//  poj1458/hduoj1159
using namespace std;
const int maxlen = 20;
void LCS(int m[][maxlen], int b[][maxlen], char x[], char y[], int xlen, int ylen)
{
	int i, j;
	for(i=0; i<=ylen; ++i)
		m[0][i] = 0;
	for(i=0; i<=ylen; ++i)
		m[i][0] = 0;
	memset(b,0,sizeof(b));
	for(i=1; i<=ylen; ++i){
		// 1 - leftup  2 - up 3 - down
		for(j=1; j<=xlen; ++j){
			if(x[j-1]!=y[i-1]){
				if(m[i-1][j]>m[i][j-1]){
					m[i][j] = m[i-1][j];
					b[i][j] = 2;
				}else{
					m[i][j] = m[i][j-1];
					b[i][j] = 3;
				}
			}else{
				m[i][j] = m[i-1][j-1] + 1;
				b[i][j] = 1;
			}
		}
	}
}
void printLCS(int b[][maxlen], char x[], int row, int col)
{
	if(row==0 || col==0)
		return;
	if(b[row][col]==1){
		printLCS(b,x,row-1,col-1);
		cout << x[col-1];
	}
	else if(b[row][col]==2){
		printLCS(b,x,row-1,col);
	}else{
		printLCS(b,x,row,col-1);
	}
	return;
}
int main()
{
	char x[maxlen] = "INTHEBEGINNING";
	char y[maxlen] = "ALLTHINGSARELOST";
	int xlen = strlen(x), ylen = strlen(y);
	int m[maxlen][maxlen], b[maxlen][maxlen];
	int i, j;
	
	memset(b,0,sizeof(b));
	LCS(m,b,x,y,xlen,ylen);
	printLCS(b,x,ylen,xlen);
	cout << endl;
	/*for(i=0; i<=ylen; ++i){
		for(j=0; j<=xlen; ++j){
			cout << b[i][j] << " ";
		}
		cout << endl;
	}*/
	return 0;
}