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

LCS最长公共子序列从理解到实现一次讲透在字符串和动态规划的学习中LCSLongest 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 控制 s1j 控制 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(); vectorvectorint dp(n 1, vectorint(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]可以优化成一维数组vectorint 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; } }常见应用场景LCS不仅是模板题还经常出现在判断字符串相似度编辑距离的变形问题DNA序列分析diff工具代码对比一些容易踩的坑把子序列当成子串dp数组下标错位i-1 / j-1忘记初始化为0回溯时路径走错总结LCS其实可以用一句话总结两个字符串在“允许跳过字符”的情况下最长能匹配多少核心就三点状态定义dp[i][j]状态转移相等 1不等取max回溯输出可选最后如果你刚学动态规划LCS是一个非常好的练习题不复杂结构清晰适合反复练建议你自己手推一遍 dp 表再写代码会比直接背模板收获大得多。