【数据结构与算法】再次全面了解LCS底层
👨💻 关于作者：会编程的土豆
“不是因为看见希望才坚持，而是坚持了才看见希望。”
你好，我是会编程的土豆，一名热爱后端技术的Java学习者。
📚正在更新中的专栏：
《数据结构与算法》😊😊😊
《leetcode hot 100》🥰🥰🥰🤩🤩🤩
《数据库mysql》
💕作者简介：后端学习者
先上例题
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { string s; cin >> s; string t = s; reverse(s.begin(), s.end()); int n = s.size(); vector<vector<int>>dp(n + 1, vector<int>(n + 1, 0)); for (int i = 1; i <=n; i++) { for (int j = 1; j <=n; j++) { if (s[i - 1] == t[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 << n - dp[n][n] << endl; return 0; }为什么 DP 表要从 1 开始循环？为什么比较字符要用 i-1 和 j-1？字符不同为什么要取左上和上边的最大值？折腾了好久终于彻底吃透，今天把整个理解过程、原理和代码完整写出来，帮和我一样的新手少走弯路！
一、先搞懂：什么是最长公共子序列？
首先区分两个易混概念，别搞反：
- 子串：要求字符连续
- 子序列：字符按顺序出现，不要求连续
最长公共子序列（LCS）：给定两个字符串，找到它们所有公共子序列中长度最长的那个，就是我们要求的结果。
举个例子：字符串 1：abcde字符串 2：ace它们的最长公共子序列就是ace，长度为 3。
二、核心：DP 表的定义（关键！）
我们用动态规划表（二维数组 dp）来解决，首先要明确 dp 数组的含义：dp[i][j]：表示字符串 1 的前 i 个字符和字符串 2 的前 j 个字符的最长公共子序列长度。
这里重点：前 i 个字符，不是第 i 个字符！这是理解后续所有逻辑的基础。
前i个其实更感觉像是个虚的，因为要给dp最前面初始化为0（方便后面左上角加1时用到），然后后面的下标1其实是求字符串第一个字母（下标为0）的公共子序列；
三、一步步拆解 DP 状态转移
1. 两种核心情况
情况 1：当前字符相同
当字符串 1 的第 i 个字符 = 字符串 2 的第 j 个字符时→ 这个字符可以加入公共子序列→ 最优解就是「两个字符串都去掉当前字符的最优解」+1→dp[i][j] = dp[i-1][j-1] + 1
情况 2：当前字符不同
当两个字符不相等时，当前字符无法同时加入公共子序列→ 只能二选一：丢掉字符串 1 的当前字符，或丢掉字符串 2 的当前字符→ 取两种情况里结果更大的那个→dp[i][j] = max(dp[i-1][j], dp[i][j-1])
2. 新手最疑惑：为什么 DP 表从 1 开始，比较用 i-1/j-1？
这是我当初卡最久的点！其实道理超简单：
- C++ 字符串下标从 0 开始，而我们的 DP 表需要预留0 行 0 列表示空字符串
- 空字符串和任何字符串的 LCS 长度都是 0，不用额外处理边界
- 如果直接从 0 开始循环，第一个字符比较时，左上角没有值，会出现数组越界！
简单说：DP 表整体往后挪一位，0 号位放空串，1 号位对应字符串的 0 号下标，也就是：dp[i]对应字符串的s[i-1]dp[j]对应字符串的t[j-1]
这样设计，代码完全不用处理边界问题，所有状态转移都能顺畅执行！
四、完整 C++ 代码实现
1. 求 LCS 长度
<iostream> #include <string> #include <vector> using namespace std; // 求最长公共子序列长度 int lcsLength(string s, string t) { int n = s.size(); int m = t.size(); // DP表开n+1行m+1列，预留0行0列 vector<int>> dp(n<int>(m + 1, 0)); // 循环从1开始 for (int i =<= n; i++) { for (int j = <= m; j++) { // 比较i-1和j-1，对齐字符串下标 if (s[i - 1] == t[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, s2;< "请输入字符串1："; cin >> s1;< "请输入字符串2："; cin >> s2;< "最长公共子序列长度："< lcsLength(s1< endl; return 0; }2. 拓展：输出具体的 LCS 序列
通过回溯 DP 表，就能拿到完整的最长公共子序列：
// 回溯获取LCS字符串 string getLCS(string s, string<int>>& dp) { int i = s.size(), j = t.size(); string res; while (i > 0 && j > 0) { if (s[i - 1] == t[j - 1]) { // 字符相同，加入结果，往左上角回溯 res += s[i - 1]; i--; j--; } else { // 字符不同，往值更大的方向回溯 if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } } // 逆序输出 reverse(res.begin(), res.end()); return res; }