公共子序列
給定兩個字符串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];
}
閱讀更多 半杯茶的小酒杯 的文章
