LeetCode 1143 LCS 题解：C++ 动态规划 3 步构建与 2 种回溯方法

LeetCode 1143 LCS 题解C 动态规划 3 步构建与 2 种回溯方法最长公共子序列Longest Common Subsequence简称 LCS是算法面试中的经典问题也是动态规划领域的入门必修课。本文将带你从零开始用 C 实现 LeetCode 1143 题的完整解法不仅讲解动态规划的核心思想还会深入探讨两种不同的回溯方法帮助你在面试中游刃有余。1. 理解问题与动态规划基础LCS 问题的核心是在两个字符串中找到最长的子序列这个子序列不需要连续但必须保持原有字符的顺序。例如对于字符串 abcde 和 ace它们的 LCS 是 ace长度为 3。动态规划解决 LCS 的关键思路定义状态我们使用二维数组dp[i][j]表示字符串text1前 i 个字符和text2前 j 个字符的 LCS 长度。状态转移方程当text1[i-1] text2[j-1]时dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])初始化dp[0][j] 0和dp[i][0] 0表示空字符串与任何字符串的 LCS 长度为 0。基础实现代码框架int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); for(int i 1; i m; i) { for(int j 1; j n; j) { if(text1[i-1] text2[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[m][n]; }2. 动态规划表的构建与可视化理解为了更好地理解动态规划的过程我们可以将 DP 表的构建过程可视化。以字符串 abcde 和 ace 为例ace0000a0111b0111c0122d0122e0123DP 表填充的关键观察点对角线增长当字符匹配时值来自左上角加 1横向/纵向传播当字符不匹配时值来自上方或左方的最大值最终结果右下角的值即为 LCS 的长度提示在面试中如果能画出这样的表格并解释清楚会给面试官留下深刻印象。3. 回溯获取具体 LCS 内容知道 LCS 的长度很重要但有时我们需要知道具体的 LCS 是什么。这里介绍两种回溯方法方法一标准回溯法string getLCS(string text1, string text2, vectorvectorint dp) { int i text1.size(), j text2.size(); string lcs; while(i 0 j 0) { if(text1[i-1] text2[j-1]) { lcs.push_back(text1[i-1]); i--; j--; } else if(dp[i-1][j] dp[i][j-1]) { i--; } else { j--; } } reverse(lcs.begin(), lcs.end()); return lcs; }方法二处理多解情况的回溯法当dp[i-1][j] dp[i][j-1]时可能存在多个 LCS。我们需要记录所有可能的路径void findAllLCS(string text1, string text2, int i, int j, vectorvectorint dp, string current, vectorstring result) { if(i 0 || j 0) { reverse(current.begin(), current.end()); if(!current.empty()) { result.push_back(current); } return; } if(text1[i-1] text2[j-1]) { current.push_back(text1[i-1]); findAllLCS(text1, text2, i-1, j-1, dp, current, result); current.pop_back(); } else { if(dp[i-1][j] dp[i][j-1]) { findAllLCS(text1, text2, i-1, j, dp, current, result); } if(dp[i][j-1] dp[i-1][j]) { findAllLCS(text1, text2, i, j-1, dp, current, result); } } }4. 空间优化与进阶技巧标准的二维 DP 表需要 O(mn) 的空间但实际上我们可以优化到 O(min(m,n))int longestCommonSubsequence(string text1, string text2) { if(text1.size() text2.size()) { return longestCommonSubsequence(text2, text1); } int m text1.size(), n text2.size(); vectorint prev(n1, 0), curr(n1, 0); for(int i 1; i m; i) { for(int j 1; j n; j) { if(text1[i-1] text2[j-1]) { curr[j] prev[j-1] 1; } else { curr[j] max(prev[j], curr[j-1]); } } swap(prev, curr); } return prev[n]; }性能对比方法时间复杂度空间复杂度适用场景标准DPO(mn)O(mn)需要回溯具体LCS空间优化DPO(mn)O(min(m,n))仅需长度二分优化*O(nlogn)O(n)特殊序列*注二分优化适用于特殊序列如排列这里不做详细展开。5. 常见错误与边界情况在实现 LCS 算法时有几个常见的陷阱需要注意索引偏移由于 DP 表比字符串长度多一维访问字符时要记得text1[i-1]初始化DP 表的第一行和第一列必须初始化为 0空字符串处理当任一输入为空时应直接返回 0字符大小写题目是否区分大小写需要明确多解处理当存在多个 LCS 时根据题目要求返回任意一个或全部测试用例设计良好的测试用例应该覆盖以下情况// 基本测试 assert(longestCommonSubsequence(abcde, ace) 3); // 空字符串测试 assert(longestCommonSubsequence(, abc) 0); assert(longestCommonSubsequence(abc, ) 0); // 完全匹配 assert(longestCommonSubsequence(abc, abc) 3); // 无公共子序列 assert(longestCommonSubsequence(abc, def) 0); // 多解情况 assert(longestCommonSubsequence(abc, acb) 2);6. 实际应用与变种问题LCS 不仅仅是一道算法题它在实际中有广泛的应用版本控制系统Git 等工具使用 LCS 来比较文件差异生物信息学DNA 序列比对的核心算法之一拼写检查寻找与错误单词最接近的正确单词相关变种问题最短公共超序列给出两个字符串的最短字符串使得这两个字符串都是其子序列编辑距离将一个字符串转换为另一个字符串所需的最少操作数最长递增子序列可以转化为 LCS 问题来解决带权重的 LCS每个字符匹配有不同的权重求最大权重和7. 面试技巧与总结在面试中遇到 LCS 问题时可以按照以下步骤进行明确问题确认输入输出要求是否需要返回长度或具体序列提出暴力解法先给出递归思路分析复杂度引入动态规划解释重叠子问题和最优子结构构建 DP 表画出表格并解释填充过程空间优化讨论如何减少空间复杂度处理边界情况考虑空字符串等特殊情况编写代码实现完整解决方案测试验证用设计的测试用例验证代码记住LCS 是动态规划的经典案例理解它对于掌握更复杂的动态规划问题至关重要。在实际编码时要注意变量命名清晰注释关键步骤保持代码整洁易读。