动态规划：最长公共子序列

[ Description ]
(Z1.2, …是序列X= (X1,Xz, ".X.的子序列，当且仅当存在严格的序列(h,iz, i),使得j=1,2, .,.有X=Z]。例如，Z=(a, b,f.c)是X=(a, b,c,f, b,c)的子序列。
现在给出两个序列X和Y,找到X和Y的最长公共子序列，也就是找到一个最长的序列z,使得Z既是X的子序列，也是Y的子序列。
[ Input]
多组测试数据，每组一行，包含两个字符串。每个字符串长度不大于1000。
[ Output]
每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。
[ Sample Input]
abcfbc abfcab
programming contest
abcd mnp
【Sample Output】
4
2
0
问题分析：
如果用字符数组s1、s2存放两个字符串，用s1[表示s1中的第i个字符，用s2[]表示s2中的第j个字符(字符标号从1开始，不存在“第0个字符”)，用s1;表示s1的前i个字符构成的子串，s2;表示s2的前j个字符构成的子串，MaxLen (i, j) 表示s1;和s2j的最长公共子序列的长度，那么递归关系如下
if(i0||j0)
MaxLen(i,j)=0;
else if(s1[i]==s2[j])
MaxLen(i,j)=MaxLen(i-1,j1)+1;
else
MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j))
这里，MaxLen(i, i)=Max(MaxLen[i, j 1), MaxLen(i- 1, )]这个递归关系需要证明一下。用反证法来证明，MaxLen(i, i)不可能比MaxLen (i, j 1)和MaxLen (i-1, j)都大。先假设MaxLen(i, j比MaxLen(i 1,j大。如果是这样的话，那么一定是s1[起作用了，即s1[i]是s1;和s2j的最长公共子序列里的最后一个字符。同样，如果MaxLen(i, j比MaxLen(i,j-1])大，也能够推导出，s2[]是 s1; 和s2j 的最长公共子序列里的最后一个字符。即如果MaxLen(i, j比MaxLen(i, j 1]和MaxLen(i -1, j)都大，那么，s1[应该和s2[]相等。但这与应用本递归关系的前提: s1[≠s2[j]是矛盾的。因此，MaxLen[i; j不可能比MaxLen(i,j-1]和MaxLen[i- 1, j都大。MaxLen[i, j当然不会比MaxLen[i, j 1]和MaxLen(i-1, j)中的任何一个小，因此，MaxLen[, j)=Max (MaxLen(i, j 1], MaxLen(i- 1, j)必然成立。
显然，本题的状态是s1中的位置i和s2中的位置j。“值”就是MaxLen[i, j)。状态数目就是s1长度和s2长度的乘积。可以用一个二维数组来存储各个状态下的值。本问题的两个子问题和原问题形式完全一致，只不过规模小了一点。
源码如下：（相关题目---->POJ1458）

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define max 1000

int i,j;
int length_a,length_b;
string a,b;
int maxlength[max][max];


int imax(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}

int main()
{
	while(cin>>a>>b)
	{
		length_a=a.size();
		length_b=b.size();
		memset(maxlength,0,sizeof(maxlength));
		for(i=1;i<=length_a;i++)
		{
			for(j=1;j<=length_b;j++)
			{
				if(a[i-1]==b[j-1])
					maxlength[i][j]=maxlength[i-1][j-1]+1;
				else
					maxlength[i][j]=imax(maxlength[i][j-1],maxlength[i-1][j]);
			}
		}
		cout<<maxlength[length_a][length_b]<<endl;
	}
	return 1;
}