心血来潮写个递归的。

#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
int dp[1000][1000];
string s1,s2;
int lcs( int i, int j )
{
	if ( i == -1 && j >= -1 ) return 0;
	else if ( j == -1 && i >= -1 ) return 0;
	else
	{
		if ( s1[i] == s2[j] ) 
		{
			if ( dp[i-1][j-1] == -1 )
				dp[i-1][j-1] = lcs( i-1, j-1 );
			return dp[i-1][j-1]+1;
		}
		else
		{
			if ( dp[i][j-1] == -1 ) dp[i][j-1] = lcs( i, j-1 );
			if ( dp[i-1][j] == -1 ) dp[i-1][j] = lcs( i-1, j );
			return dp[i][j-1] > dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
		}
	}
}
int main()
{
	int i, j;
	while ( cin>>s1>>s2 )
	{
		memset ( dp,  -1, sizeof(int)*1000000 );
		cout<<lcs( s1.size()-1, s2.size()-1 )<<endl;
	}
	return 1;
}
以上代码在POJ WA（为啥不是RE），在ZOJ AC（为啥可以AC？）
但上面的代码在我机器上的GCC4.3.3中可以给出正确结果，可是程序中会出现dp[-1][-1]的情况，囧啊！

修改成如下后，在POJ AC
#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
int dp[1000][1000];
string s1,s2;
long int t;
int lcs( int i, int j )
{
	if ( i==0 && j >= 0 ) return 0;
	else if ( j==0 && i >= 0 ) return 0;
	else
	{
		if ( s1[i] == s2[j] ) 
		{
			if ( dp[i-1][j-1] == -1 )
				dp[i-1][j-1] = lcs( i-1, j-1 );
			return dp[i-1][j-1]+1;
		}
		else
		{
			if ( dp[i][j-1] == -1 ) dp[i][j-1] = lcs( i, j-1 );
			if ( dp[i-1][j] == -1 ) dp[i-1][j] = lcs( i-1, j );
			return dp[i][j-1] > dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
		}
	}
}
int main()
{
	int i, j;
	while ( cin>>s1>>s2 )
	{
		s1 = "1"+s1;
		s2 = "1"+s2;
		memset ( dp,  -1, sizeof(int)*1000000 );
		t = 0;
		cout<<lcs( s1.size()-1, s2.size()-1 )<<endl;
	}
	return 1;
}