[LintCode]Longest Common Subsequence

经典的DP问题，解法也可以扩展到很多其他的题目。假设输入字符串为s1和s2，我们用DP[i][j]表示s1中前i个字符和s2中前j个字符的LCS，我们有递推公式：

• DP[i][j] = DP[i - 1][j - 1] + 1, if s1[i] == s2[j]
• else, DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])

假设输入串长度分别为n和m，时间和空间复杂度均为O(m * n)，代码如下：

	class Solution {
	public:
	/**
	* @param A: A string
	* @param B: A string
	* @return: The length of longest common subsequence of A and B
	*/
	int longestCommonSubsequence(string &A, string &B) {
	// write your code here
	int lenA = A.size(), lenB = B.size();
	//dp[i][j] represents LCS in first i chars in A and first j chars in B;
	//dp[i][j] = dp[i - 1][j - 1] + 1, if A[i] == B[j]
	//otherwise, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	//base case: dp[i][0] = 0, dp[0][j] = 0
	vector<vector<int>> dp(lenA + 1, vector<int>(lenB + 1, 0));
	for(int i = 0; i < lenA; ++i)
	{
	for(int j = 0; j < lenB; ++j)
	{
	dp[i + 1][j + 1] = A[i] == B[j]? dp[i][j] + 1: max(dp[i + 1][j], dp[i][j + 1]);
	}
	}
	return dp[lenA][lenB];
	}
	};

view raw Longest Common Subsequences_dp.cpp hosted with ❤ by GitHub

和Longest Common Substring类似，我们可以用滚动数组进行优化，空间可以优化到O(n)，代码入下：

	class Solution {
	public:
	/**
	* @param A: A string
	* @param B: A string
	* @return: The length of longest common subsequence of A and B
	*/
	int longestCommonSubsequence(string &A, string &B) {
	// write your code here
	int lenA = A.size(), lenB = B.size(), e = 1;
	//dp[i][j] represents LCS in first i chars in A and first j chars in B;
	//dp[i][j] = dp[i - 1][j - 1] + 1, if A[i] == B[j]
	//otherwise, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	//base case: dp[i][0] = 0, dp[0][j] = 0
	vector<vector<int>> dp(2, vector<int>(lenB + 1, 0));
	for(int i = 0; i < lenA; ++i, e ^= 1)
	{
	for(int j = 0; j < lenB; ++j)
	{
	dp[e][j + 1] = A[i] == B[j]? dp[e ^ 1][j] + 1: max(dp[e][j], dp[e ^ 1][j + 1]);
	}
	}
	return dp[e ^ 1][lenB];
	}
	};

view raw Longest Common Subsequences_dp_with_rolling_array.cpp hosted with ❤ by GitHub