公共子序列
给定两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符在原字符串中不要求连续，只要保持原有相对顺序即可。
例如，字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。
算法求解
动态规划问题一般具备两个特征:
1) 最优子结构；
2) 重叠子问题；
设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共子序列记为LCS(X,Y)。
最优子结构
首先考虑X的最后一个元素和Y的最后一个元素。
1) 如果 xn=ym，即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)。
LCS(Xn-1，Ym-1)就是原问题的一个子问题。为什么是最优的子问题？因为我们要找的是X
n-1 和 Ym-1 的最长公共子序列。2) 如果xn != ym，因为序列X 和 序列Y 的最后一个元素不相等，那最后一个元素不可能是最长公共子序列中的元素。因此产生了两个子问题：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)。
LCS(Xn-1，Ym)表示：最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。
LCS(Xn，Ym-1)表示：最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。
求解上面两个子问题，得到的公共子序列谁最长，那谁就是 LCS（X,Y）。用数学表示就是：
LCS=max{LCS(Xn-1，Ym)，LCS(X
n，Ym-1)}。通过1)和2)可以把原问题转化成三个规模更小的子问题。
重叠子问题
重叠子问题就是原问题转化成子问题后，子问题中有相同的问题。
原问题是LCS(X,Y)，子问题有LCS(Xn-1，Ym-1)、LCS(Xn-1，Ym)、LCS(Xn，Ym-1)。其中LCS(Xn-1，Ym) 就包含了LCS(Xn-1，Ym-1)，因为当Xn-1和Ym的最后一个元素不相同时，我们又需要将LCS(Xn-1，Y
m)进行分解成：LCS(Xn-1，Ym-1) 和 LCS(Xn-2，Ym)。也就是说在子问题的继续分解中，有些问题是重叠的。它具有重叠子问题的性质，因此用递归来求解就太不划算了，因为采用递归，它重复地求解了子问题。
最长公共子序列的递归式如下:
c[i,j]表示：(x1,x2....xi) 和 (y1,y2...yj) 的最长公共子序列的长度。
算法实现
int findLCS(const std::string& A, const std::string& B) {
size_t n = A.size();
size_t m =B.size();
std::vector<:vector>> dp(n + 1, std::vector
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i] == B[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
return dp[n][m];
}
閱讀更多 半杯茶的小酒杯 的文章
