POJ1458最长公共子序列

为了完成POJ中的一题（spell checker），要写一个最长公共子序列的程序，居然突然全给忘了，楞是没有写出来，深深的鄙视自己一下。

这也是一道动态规划的典型题。

递归实现如下（POJ提交会超时，但是确实可以实现）：

using namespace std;
#define max( a ,b ) ((a)>(b)?(a):(b))

//最长公共子序列
int maxlen( char *a, char *b)
{
        int len = 0;

        while( *a == *b && *a != '\0')
        {
                a++;
                b++;
                len++;
        }
        if( *a != '\0' && *b != '\0')
        return len + max( maxlen( a + 1, b), maxlen( a, b + 1) );
return len;
}

int main()
{
        char *a = "abcdefg";
        char *b = "bbcdfg";
        cout << "maxlen(" << a << ", " << b << " ) = " << maxlen( a, b ) << endl;

return 0;
}

下面这个程序用到了动态规划（所谓动态规划就是将一个问题分解成为子问题递归求解，并且将中间结果保存以避免重复计算，关键就是1.找边界，2.找状态转移公式）。此例乃动态规划的典型题。具体实现如下：

#include<iostream>
using namespace std;


#define MAX 1000
int ndata[ MAX ][ MAX ];

//最长公共子序列

/*
递推公式：
if( i == 0 || j == 0 ) maxlen( i, j ) = 0;
else if( s1[i] == s2[j]) maxlen( i, j) = maxlen( i - 1, j -1) + 1;
else maxlen( i, j) = max( maxlen(i, j - 1 ), maxlen( i - 1, j));
*/

int main()
{
	char a[MAX];
	char b[MAX];

	int i , j;
	int nTemp;
	while( scanf("%s%s", a + 1, b + 1) > 0)
	{
		int nLength1 = strlen( a + 1 );
		int nLength2 = strlen( b + 1 );
			
		for ( i = 0; i <= nLength1; i++)
			ndata[i][0] = 0;
		for ( j = 0; j <= nLength2; j++)
			ndata[0][j] = 0;

		for( i = 1; i <= nLength1; i++ )
			for( j = 1; j <= nLength2; j++ )
			{
				if( a[i] == b[j] )
				 ndata[i][j] = ndata[i - 1][j - 1] + 1;
				else
				{
				if( ndata[i][j - 1] > ndata[i -1][j])
					ndata[i][j] = ndata[i][j - 1];
				else
					ndata[i][j] = ndata[i - 1][j];
				}
			}
	printf("%d\n", ndata[ nLength1][nLength2]);
	}
return 0;
}