Longest common subsequence problem

LCS.cpp

//http://poj.org/problem?id=1458
//http://poj.org/problem?id=1159  利用了滚动数组，要不然会内存溢出
//http://poj.org/problem?id=2250  需要打印，用一个数组记录path状态
//shihongzhi ---2012.3.8
#include <stdio.h>

int dp[100][100];

int LCS(char *a, char *b, int aLen, int bLen)
{
	for (int i=0; i<100; ++i)
	{
		dp[i][0] = 0;
		dp[0][i] = 0;
	}
	for (int i=0; i<aLen; ++i)
	{
		for (int j=0; j<bLen; ++j)
		{
			if (a[i] == b[j])
				dp[i+1][j+1] = dp[i][j] + 1;
			else
				dp[i+1][j+1] = dp[i+1][j] > dp[i][j+1] ? dp[i+1][j] : dp[i][j+1];
		}
	}
	return dp[aLen][bLen];
}

int main()
{
	char a[] = "abcdefg";
	char b[] = "bdgfg";
	printf("%d\n", LCS(a, b, 7, 5));
	return 0;
}