1. 最长公共子序列问题入门最长公共子序列Longest Common Subsequence简称LCS是计算机科学中一个经典的问题。简单来说给定两个序列我们需要找到它们共有的、长度最长的子序列。这里需要注意子序列和子串的区别子序列不要求元素在原序列中连续只要保持相对顺序即可。举个例子假设我们有两个字符串序列XABCBDAB序列YBDCABA它们的公共子序列有BCA、BCBA、BDAB等其中最长的公共子序列是BDAB或BCBA长度都是4。LCS问题在实际中有很多应用场景文本比较工具如Git的diff命令DNA序列比对语音识别版本控制系统理解LCS的关键在于掌握它的两个重要特性最优子结构问题的最优解包含其子问题的最优解重叠子问题在递归求解过程中会重复计算相同的子问题2. 动态规划解法详解2.1 DP表构建原理动态规划是解决LCS问题的最佳方法。我们使用一个二维数组dp来记录中间结果其中dp[i][j]表示序列X前i个字符和序列Y前j个字符的LCS长度。构建DP表的规则很简单初始化dp[0][j] 0和dp[i][0] 0空序列与任何序列的LCS长度都是0递推关系如果X[i-1] Y[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])让我们用实际例子来说明。假设XABCBDABYBDCABA构建的DP表如下Ø B D C A B A Ø 0 0 0 0 0 0 0 A 0 0 0 0 1 1 1 B 0 1 1 1 1 2 2 C 0 1 1 2 2 2 2 B 0 1 1 2 2 3 3 D 0 1 2 2 2 3 3 A 0 1 2 2 3 3 4 B 0 1 2 2 3 4 42.2 C实现代码下面是用C实现DP表构建的完整代码#include iostream #include vector #include algorithm using namespace std; int lcsLength(const string X, const string Y) { int m X.length(); int n Y.length(); vectorvectorint dp(m1, vectorint(n1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (X[i-1] Y[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; } int main() { string X ABCBDAB; string Y BDCABA; cout Length of LCS is lcsLength(X, Y) endl; return 0; }这段代码的时间复杂度和空间复杂度都是O(mn)其中m和n分别是两个输入字符串的长度。3. 回溯获取LCS内容3.1 单解回溯方法知道LCS的长度很有用但通常我们还需要知道具体的LCS内容。回溯是从DP表中提取LCS的过程基本思路是从dp[m][n]开始逆向追踪到dp[0][0]。回溯规则如果X[i-1] Y[j-1]则该字符属于LCS移动到dp[i-1][j-1]否则移动到dp[i-1][j]和dp[i][j-1]中较大的那个如果两者相等可以选择任意方向这会导致不同的LCS下面是单解回溯的C实现string getOneLCS(const string X, const string Y, const vectorvectorint dp) { int i X.length(); int j Y.length(); string lcs; while (i 0 j 0) { if (X[i-1] Y[j-1]) { lcs.push_back(X[i-1]); --i; --j; } else if (dp[i-1][j] dp[i][j-1]) { --i; } else { --j; } } reverse(lcs.begin(), lcs.end()); return lcs; }3.2 多解回溯策略当DP表中出现dp[i-1][j] dp[i][j-1]且X[i-1] ! Y[j-1]时说明存在多个LCS。为了获取所有可能的LCS我们需要探索所有可能的路径。实现多解回溯的关键是使用递归在遇到相等值时同时探索两个方向。下面是C实现void getAllLCS(const string X, const string Y, int i, int j, const vectorvectorint dp, string current, vectorstring result) { if (i 0 || j 0) { if (!current.empty()) { reverse(current.begin(), current.end()); result.push_back(current); reverse(current.begin(), current.end()); } return; } if (X[i-1] Y[j-1]) { current.push_back(X[i-1]); getAllLCS(X, Y, i-1, j-1, dp, current, result); current.pop_back(); } else { if (dp[i-1][j] dp[i][j-1]) { getAllLCS(X, Y, i-1, j, dp, current, result); } if (dp[i][j-1] dp[i-1][j]) { getAllLCS(X, Y, i, j-1, dp, current, result); } } } vectorstring getAllLCS(const string X, const string Y) { int m X.length(); int n Y.length(); vectorvectorint dp(m1, vectorint(n1, 0)); // 构建DP表同上 // ... vectorstring result; string current; getAllLCS(X, Y, m, n, dp, current, result); return result; }4. 优化与扩展4.1 空间优化技巧标准的DP解法需要O(mn)空间但实际上我们可以优化到O(min(m,n))。因为计算dp[i][j]时只需要当前行和上一行的数据。下面是空间优化后的C实现int lcsLengthOptimized(const string X, const string Y) { if (X.length() Y.length()) return lcsLengthOptimized(Y, X); int m X.length(); int n Y.length(); vectorvectorint dp(2, vectorint(n1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (X[i-1] Y[j-1]) { dp[i%2][j] dp[(i-1)%2][j-1] 1; } else { dp[i%2][j] max(dp[(i-1)%2][j], dp[i%2][j-1]); } } } return dp[m%2][n]; }4.2 实际应用中的变种LCS问题在实际中有多种变体常见的有最长公共子串要求子序列必须连续带权重的LCS每个字符匹配有不同的权重多序列LCS扩展到三个或更多序列的比较以最长公共子串为例它的DP递推关系稍有不同int longestCommonSubstring(const string X, const string Y) { int m X.length(); int n Y.length(); vectorvectorint dp(m1, vectorint(n1, 0)); int result 0; for (int i 1; i m; i) { for (int j 1; j n; j) { if (X[i-1] Y[j-1]) { dp[i][j] dp[i-1][j-1] 1; result max(result, dp[i][j]); } else { dp[i][j] 0; } } } return result; }在实际编码面试中理解这些变种问题并能快速实现是非常重要的。建议读者可以尝试自己实现这些变种加深对LCS问题的理解。