【数据结构与算法】再次全面了解LCS底层

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者先上例题#includeiostream #includevector #includealgorithm using namespace std; int main() { string s; cin s; string t s; reverse(s.begin(), s.end()); int n s.size(); vectorvectorintdp(n 1, vectorint(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给定两个字符串找到它们所有公共子序列中长度最长的那个就是我们要求的结果。举个例子字符串 1abcde字符串 2ace它们的最长公共子序列就是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表开n1行m1列预留0行0列 vectorint dp(nint(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, stringint 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; }