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

最长公共子序列（LCS）——从零开始的动态规划

news 2026/3/26 18:34:49

LCS最长公共子序列：从理解到实现，一次讲透

在字符串和动态规划的学习中，LCS（Longest Common Subsequence，最长公共子序列）是一个绕不开的经典问题。很多人一开始觉得它和“最长公共子串”差不多，但真正做题的时候才发现完全不是一回事。

这篇文章就从最基础的概念出发，把LCS的思路、状态转移、代码实现以及一些常见误区讲清楚。

什么是LCS；先别急着写代码

给定两个字符串：

s1 = ABCBDAB s2 = BDCABA

我们要找的是：

在不改变相对顺序的前提下，两个字符串的“最长公共子序列”

注意两个关键词：

子序列：可以不连续
顺序不能变

例如：

BCBA

就是一个合法答案。

子序列 vs 子串；别再混了

这是最常见的坑。

子序列：可以跳着选
子串：必须连续

举个例子：

ABCDEF

子序列可以是：ACE
子串只能是：ABC、BCD、DEF 这种连续的

一句话记住：

LCS可以“跳”，最长公共子串不能跳

为什么LCS适合用动态规划

如果用暴力去做：

每个字符串都有 2^n 种子序列
两个字符串组合起来，复杂度直接爆炸

但LCS有一个很明显的特征：

大问题可以拆成小问题

这正是动态规划的典型应用场景。

核心思路；状态是怎么定义的

我们定义：

dp[i][j] = s1前i个字符 和 s2前j个字符 的LCS长度

也就是说：

i 控制 s1
j 控制 s2

最终答案就是：

dp[n][m]

状态转移；真正关键的地方

分两种情况：

1. 当前字符相等

if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;

理解：

既然两个字符一样，那就可以加入公共子序列

2. 当前字符不相等

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

理解：

要么丢掉 s1 的当前字符
要么丢掉 s2 的当前字符

取更优的那种情况。

完整代码实现；最标准写法

#include <iostream> #include <vector> using namespace std; int main() { string s1 = "ABCBDAB"; string s2 = "BDCABA"; int n = s1.size(); int m = s2.size(); 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]); } } } cout << "LCS长度: " << dp[n][m] << endl; return 0; }

如果不只是长度；还想输出序列

很多题目不仅要求长度，还要输出具体的LCS。

思路是：

从 dp[n][m] 反向回溯

大致逻辑：

如果字符相等 → 加入答案，往左上走
否则 → 往较大的方向走

示例代码：

string res = ""; int i = n, j = m; while (i > 0 && j > 0) { if (s1[i - 1] == s2[j - 1]) { res = s1[i - 1] + res; i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } cout << "LCS: " << res << endl;

空间优化；从二维到一维

观察状态转移：

dp[i][j] 只依赖： dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

可以优化成一维数组：

vector<int> dp(m + 1, 0); for (int i = 1; i <= n; i++) { int prev = 0; for (int j = 1; j <= m; j++) { int temp = dp[j]; if (s1[i - 1] == s2[j - 1]) { dp[j] = prev + 1; } else { dp[j] = max(dp[j], dp[j - 1]); } prev = temp; } }