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 的关键思路

1. 定义状态：我们使用二维数组dp[i][j]表示字符串text1前 i 个字符和text2前 j 个字符的 LCS 长度。
2. 状态转移方程：
   • 当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])
3. 初始化：dp[0][j] = 0和dp[i][0] = 0，表示空字符串与任何字符串的 LCS 长度为 0。

基础实现代码框架

int longestCommonSubsequence(string text1, string text2) { int m = text1.size(), n = text2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 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" 为例：

DP 表填充的关键观察点

1. 对角线增长：当字符匹配时，值来自左上角加 1
2. 横向/纵向传播：当字符不匹配时，值来自上方或左方的最大值
3. 最终结果：右下角的值即为 LCS 的长度

提示：在面试中，如果能画出这样的表格并解释清楚，会给面试官留下深刻印象。

3. 回溯获取具体 LCS 内容

知道 LCS 的长度很重要，但有时我们需要知道具体的 LCS 是什么。这里介绍两种回溯方法：

方法一：标准回溯法

string getLCS(string& text1, string& text2, vector<vector<int>>& 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, vector<vector<int>>& dp, string current, vector<string>& 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(); vector<int> prev(n+1, 0), curr(n+1, 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]; }

性能对比

*注：二分优化适用于特殊序列（如排列），这里不做详细展开。

5. 常见错误与边界情况

在实现 LCS 算法时，有几个常见的陷阱需要注意：

1. 索引偏移：由于 DP 表比字符串长度多一维，访问字符时要记得text1[i-1]
2. 初始化：DP 表的第一行和第一列必须初始化为 0
3. 空字符串处理：当任一输入为空时，应直接返回 0
4. 字符大小写：题目是否区分大小写需要明确
5. 多解处理：当存在多个 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 不仅仅是一道算法题，它在实际中有广泛的应用：

1. 版本控制系统：Git 等工具使用 LCS 来比较文件差异
2. 生物信息学：DNA 序列比对的核心算法之一
3. 拼写检查：寻找与错误单词最接近的正确单词

相关变种问题

1. 最短公共超序列：给出两个字符串的最短字符串，使得这两个字符串都是其子序列
2. 编辑距离：将一个字符串转换为另一个字符串所需的最少操作数
3. 最长递增子序列：可以转化为 LCS 问题来解决
4. 带权重的 LCS：每个字符匹配有不同的权重，求最大权重和

7. 面试技巧与总结

在面试中遇到 LCS 问题时，可以按照以下步骤进行：

1. 明确问题：确认输入输出要求，是否需要返回长度或具体序列
2. 提出暴力解法：先给出递归思路，分析复杂度
3. 引入动态规划：解释重叠子问题和最优子结构
4. 构建 DP 表：画出表格并解释填充过程
5. 空间优化：讨论如何减少空间复杂度
6. 处理边界情况：考虑空字符串等特殊情况
7. 编写代码：实现完整解决方案
8. 测试验证：用设计的测试用例验证代码

记住，LCS 是动态规划的经典案例，理解它对于掌握更复杂的动态规划问题至关重要。在实际编码时，要注意变量命名清晰，注释关键步骤，保持代码整洁易读。