Geeks面试题： Longest Common Subsequence (LCS)

递归法：

int lcs(char *c1, int m, char *c2, int n)
{
	if (m == 0 || n == 0) return 0;

	if (c1[m-1] == c2[n-1])
	{
		return 1 + lcs(c1, m-1, c2, n-1);
	}
	else
	{
		return max(lcs(c1, m-1, c2, n), lcs(c1, m, c2, n-1));
	}
}

int lcsDP(char *c1, int m, char *c2, int n)
{
	vector<vector<int> > ta(m+1, vector<int>(n+1));

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (c1[i] == c2[j]) ta[i+1][j+1] = ta[i][j]+1;
			else
			{
				ta[i+1][j+1] = max(ta[i][j+1], ta[i+1][j]);
			}
		}
	}
	return ta[m][n];
}

int lcsDP2(char *c1, int m, char *c2, int n)
{
	vector<vector<int> > ta(2, vector<int>(n+1));
	bool flag = false;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (c1[i] == c2[j])
			{
				ta[flag][j+1] = ta[!flag][j] + 1;
			}
			else
			{
				ta[flag][j+1] = max(ta[!flag][j+1], ta[flag][j]);
			}
		}
		flag = !flag;
	}
	return ta[!flag][n];
}

int lcsDP3(char *c1, int m, char *c2, int n)
{
	vector<int> ta(n+1);
	int t1 = 0;
	int t2 = 0;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			t2 = ta[j+1];
			if (c1[i] == c2[j])
			{
				ta[j+1] = t1+1;
			}
			else
			{
				ta[j+1] = max(ta[j], t2);
			}
			t1 = t2;
		}
		t1 = 0;
	}
	return ta[n];
}

int main()
{
	char X[] = "AGGTAB";
	char Y[] = "GXTXAYB";

	int m = strlen(X);
	int n = strlen(Y);

	printf("Length of LCS is %d\n", lcsDP2( X, m, Y, n ) );

	system("pause");
	return 0;
}