当前位置：首页 > news >正文

最长公共子序列（LCS）动态规划 C++ 实现与多解回溯详解

news 2026/7/16 23:18:47

1. 最长公共子序列问题入门

最长公共子序列（Longest Common Subsequence，简称LCS）是计算机科学中一个经典的问题。简单来说，给定两个序列，我们需要找到它们共有的、长度最长的子序列。这里需要注意子序列和子串的区别：子序列不要求元素在原序列中连续，只要保持相对顺序即可。

举个例子，假设我们有两个字符串：

序列X："ABCBDAB"
序列Y："BDCABA"

它们的公共子序列有"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])

让我们用实际例子来说明。假设X="ABCBDAB"，Y="BDCABA"，构建的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 4

2.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(); vector<vector<int>> dp(m+1, vector<int>(n+1, 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 vector<vector<int>> &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 vector<vector<int>> &dp, string &current, vector<string> &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); } } } vector<string> getAllLCS(const string &X, const string &Y) { int m = X.length(); int n = Y.length(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 构建DP表（同上） // ... vector<string> 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(); vector<vector<int>> dp(2, vector<int>(n+1, 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(); vector<vector<int>> dp(m+1, vector<int>(n+1, 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问题的理解。

查看全文

http://www.jsqmd.com/news/1202999/