C++如何用动态规划求解最长公共子序列？一文讲透LCS算法

最长公共子序列（Longest Common Subsequence，简称LCS）是动态规划领域一道绕不开的经典题。给定两个字符串，求出它们最长的公共子序列长度，这里的子序列不要求字符连续，但必须保持相对顺序。比如字符串ABCBDAB和BDCABA的最长公共子序列是BCBA或BDAB，长度都是4。这个问题看似简单，却蕴含了动态规划的核心思维，也是很多字符串比较问题的基础模型。

解决LCS问题，最直接的暴力思路是枚举其中一个字符串的所有子序列，然后逐一判断它是否也是另一个字符串的子序列。但一个长度为n的字符串拥有2^n个子序列，这种指数级复杂度在实际应用中完全不可行。贪心策略在这里同样失效，因为局部最优的选择未必能带来全局最优的公共子序列。动态规划之所以适用，是因为这个问题天然具备最优子结构和重叠子问题的特性。

LCS的DP状态定义与递推公式推导

动态规划的第一步是定义状态。对于两个字符串s1和s2，我们设dp[i][j]表示s1的前i个字符与s2的前j个字符所形成的最长公共子序列长度。注意这里的i和j代表的是前缀长度，而不是下标索引。当i或j为0时，表示其中一个字符串为空串，此时LCS长度必然是0，这就是DP表的初始状态。

有了状态定义，接下来推导状态转移方程。考虑s1的第i个字符（下标为i-1）和s2的第j个字符（下标为j-1）是否相等，会产生两种情况。如果s1[i-1]等于s2[j-1]，那么这个字符一定可以加入公共子序列中，此时dp[i][j]等于dp[i-1][j-1]加1，也就是说在去掉这两个末尾字符的前缀基础上，最长公共子序列又延长了一位。这个决策是确定的，不会产生分歧。

如果s1[i-1]不等于s2[j-1]，情况稍微复杂一些。这两个字符不可能同时出现在公共子序列的末尾，所以需要舍弃其中一个，看看哪种舍弃方式能保留更长的公共子序列。具体来说，要么忽略s1的最后一个字符，保留s1前i-1个字符与s2前j个字符的LCS结果；要么忽略s2的最后一个字符，保留s1前i个字符与s2前j-1个字符的LCS结果。取两者的较大值即可。很多人在这里会有一个直觉上的疑问：为什么不能同时忽略两个字符，也就是考虑dp[i-1][j-1]？其实dp[i-1][j-1]的结果一定不会比dp[i-1][j]和dp[i][j-1]更大，因为前缀越短，LCS长度只会越小或不变，所以dp[i-1][j-1]被前两种情况天然覆盖，不需要单独比较。

递推公式可以简洁地写出来：当s1[i-1]等于s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1；当两者不相等时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这张二维DP表按照从上到下、从左到右的顺序逐行填充，最终dp[n][m]就是整个问题的答案，其中n和m分别是两个字符串的长度。

C++完整实现与代码细节解析

把上面的递推逻辑转成C++代码并不复杂，但有几个实现细节值得注意。最基本的方法是用一个二维vector来存储DP表，外层循环遍历s1的每一个字符，内层循环遍历s2的每一个字符，按照递推公式填入数值。以下是基础版本的完整代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int longestCommonSubsequence(const string& s1, const string& s2) {
    int n = s1.size();
    int m = s2.size();
    // dp[i][j] 表示 s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[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[n][m];
}

int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCABA";
    cout << "LCS长度: " << longestCommonSubsequence(s1, s2) << endl;
    return 0;
}

代码中dp表的大小是(n+1)行、(m+1)列，多出来的第一行和第一列全部初始化为0，正好对应“空串与任意字符串的LCS长度为0”这个边界条件。循环变量i和j从1开始，对应的字符下标为i-1和j-1，这个偏移关系要特别留意。如果搞混了下标，访问字符时越界或者取错位置，结果就会完全错误。

上面这段代码的时间复杂度是O(n*m)，空间复杂度也是O(n*m)。对于字符串长度在几千以内的场景，这个复杂度完全够用。但如果字符串长度达到十万级别，二维数组的内存占用就会成为瓶颈，需要进一步优化。

仅求长度时的空间优化：滚动数组方案

观察递推公式可以发现，dp[i][j]的值只依赖三个来源：正上方的dp[i-1][j]、左方的dp[i][j-1]以及左上方的dp[i-1][j-1]。换句话说，计算当前行时只需要上一行的数据。这意味着我们不需要保存整张二维表，用两行滚动数组就足够了，甚至可以用一行数组配合一个临时变量来实现。

用两行数组的实现思路比较直观：定义prev表示上一行，curr表示当前行，每一行计算完毕后交换两者。但更精炼的写法是只用一个一维数组，再额外用一个变量pre保存左上角的值。遍历顺序必须从左到右，因为计算dp[j]时需要用到当前行左侧刚刚更新过的dp[j-1]和上一行还没被覆盖的dp[j]。关键点在于，当s1[i-1]与s2[j-1]相等时，需要用到的左上角值dp[i-1][j-1]在上一轮循环中已经被覆盖了，所以必须提前用变量保存下来。以下是优化后的代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int longestCommonSubsequenceOptimized(const string& s1, const string& s2) {
    int n = s1.size();
    int m = s2.size();
    vector<int> dp(m + 1, 0);
    
    for (int i = 1; i <= n; ++i) {
        int prev = 0; // 保存左上角 dp[i-1][j-1]
        for (int j = 1; j <= m; ++j) {
            int temp = dp[j]; // 记录当前 dp[j] 在被覆盖之前的值，供下一轮作为左上角使用
            if (s1[i - 1] == s2[j - 1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
            prev = temp; // 更新左上角为旧 dp[j]
        }
    }
    return dp[m];
}

int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCABA";
    cout << "优化后LCS长度: " << longestCommonSubsequenceOptimized(s1, s2) << endl;
    return 0;
}

这段优化代码中，dp[j]在更新之前代表上一行的dp[i-1][j]，dp[j-1]已经更新为当前行的值。temp变量保存的是即将被覆盖的旧dp[j]，也就是下一轮循环中需要的左上角dp[i-1][j-1]。这个临时变量的存在是单数组实现能否正确的核心，很多人在手写滚动数组时漏掉这一步，导致相等分支拿到错误的上左值。空间复杂度从O(n*m)降到了O(m)，在长字符串场景下内存占用大幅下降。

回溯输出最长公共子序列的具体内容

有时候我们不仅需要知道LCS的长度，还需要输出具体的子序列。长度可以通过数值直接获得，但子序列本身需要从DP表中回溯构造。回溯的基本思路是从右下角的dp[n][m]出发，倒推每一步是如何决策的。如果s1[i-1]与s2[j-1]相等，说明这个字符是LCS的一部分，将它记录下来，然后向左上方移动到dp[i-1][j-1]继续回溯。如果两个字符不相等，就要看dp[i-1][j]和dp[i][j-1]哪一个更大，向较大的方向移动。如果两者相等，走哪一边都不会影响长度，任选一条即可。

回溯得到的字符顺序是逆序的，因为是从末尾向开头构造的，最后需要反转一下字符串。下面是结合二维DP表输出具体LCS的完整代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string getLCS(const string& s1, const string& s2) {
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // 先填 DP 表
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 回溯构造 LCS
    string lcs;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs.push_back(s1[i - 1]);
            --i;
            --j;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

int main() {
    string s1 = "ABCBDAB";
    string s2 = "BDCABA";
    string result = getLCS(s1, s2);
    cout << "LCS长度: " << result.size() << endl;
    cout << "LCS内容: " << result << endl;
    return 0;
}

回溯时注意一个细节：当dp[i-1][j]与dp[i][j-1]相等时，选择任意方向都可行，但不同的选择可能输出不同的LCS，因为最长公共子序列本身可能并不唯一。例如ABCBDAB和BDCABA这两个字符串的LCS就有BCBA和BDAB两种。如果需要输出所有LCS，回溯逻辑会变得更加复杂，需要递归地遍历所有可能的分支路径。

除了字符串匹配，LCS的思想在生物信息学中用于DNA序列比对，在版本控制系统中用于计算文件差异，在文本查重领域也有应用。理解LCS的DP递推模型，再去学习编辑距离、最长回文子序列、正则表达式匹配等问题，会发现它们的DP设计思路高度相似，本质上都是在二维表格上刻画两个序列之间的关系。

C++最长公共子序列动态规划DP修改时间：2026-09-17 15:13:10