1. 最长公共子序列（LCS）与最长递增子序列（LIS）概述
在算法领域，子序列问题一直是经典且实用的课题。最长公共子序列（Longest Common Subsequence, LCS）和最长递增子序列（Longest Increasing Subsequence, LIS）是两个密切相关但又各具特点的问题。
LCS要解决的问题是：给定两个序列，找出它们共有的、最长的子序列。这里的子序列不要求连续，但必须保持原始顺序。例如，"ABC"和"AC"都是"ABCD"的子序列。这个问题在文本相似度比较、版本控制、生物信息学等领域有广泛应用。
LIS则是针对单个序列的问题：找出一个子序列，使得元素严格递增，并且这个子序列尽可能长。例如，序列[10,9,2,5,3,7,101,18]的LIS是[2,3,7,101]，长度为4。这个问题在任务调度、股票分析等领域很常见。
2. LCS的经典动态规划解法
2.1 状态定义与转移方程
LCS的标准解法采用动态规划，其核心在于状态定义和转移方程的设计。我们定义dp[i][j]表示序列A前i个元素和序列B前j个元素的LCS长度。
转移方程分为两种情况：
- 当A[i] == B[j]时：dp[i][j] = dp[i-1][j-1] + 1
- 当A[i] != B[j]时：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这个方程直观地反映了：当当前元素匹配时，LCS长度可以增加1；否则，我们需要考虑舍弃A或B的当前元素，取较大值。
2.2 实现细节与优化
基础实现通常使用二维数组存储状态，空间复杂度为O(mn)。对于较长的序列，可以采用滚动数组优化，将空间复杂度降至O(min(m,n))。
def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): 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]注意：在实际编码时，边界条件处理很重要。通常我们会让dp数组的维度比字符串长度大1，以方便处理空串的情况。
3. LIS的多种解法比较
3.1 动态规划解法
最直观的解法也是动态规划。定义dp[i]表示以第i个元素结尾的LIS长度：
def lengthOfLIS(nums: List[int]) -> int: if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)这种方法时间复杂度为O(n²)，适合小规模数据。
3.2 贪心+二分查找优化
更高效的解法结合了贪心策略和二分查找，时间复杂度可降至O(nlogn)。其核心思想是维护一个最小尾部数组：
def lengthOfLIS(nums: List[int]) -> int: tails = [] for num in nums: idx = bisect.bisect_left(tails, num) if idx == len(tails): tails.append(num) else: tails[idx] = num return len(tails)这种方法不仅计算长度，还可以还原出具体的LIS序列。
4. 实际应用与变种问题
4.1 LCS的应用场景
- 文本相似度比较：Git等版本控制系统用LCS来显示文件差异
- 生物信息学：DNA序列比对
- 抄袭检测：比较代码或文档的相似性
4.2 LIS的变种问题
- 最长非递减子序列：允许相等元素
- 二维LIS问题：如信封嵌套问题
- 带权LIS：每个元素有权重，求最大权重和
5. 常见错误与调试技巧
5.1 边界条件处理
- 空输入处理
- 所有元素相同的情况
- 严格递增与非严格递增的区分
5.2 性能优化
- 对于LCS，如果只需要长度，可以优化空间
- 对于LIS，优先考虑O(nlogn)解法
- 避免不必要的状态计算
5.3 调试建议
- 先用小规模数据测试
- 打印中间状态矩阵
- 对比暴力解法的结果
6. 扩展思考
6.1 LCS与LIS的关系
有趣的是，LIS问题可以转化为LCS问题：将原序列排序后，与原序列求LCS就是LIS。这种转化展示了算法问题之间的内在联系。
6.2 更高效的算法
对于特定场景，如小字母集的字符串LCS，可以使用位运算等技巧进一步优化。而LIS问题在特定条件下也有O(n)解法。
在实际工程中，选择算法时需要权衡：
- 数据规模
- 是否需要具体序列而不仅是长度
- 时间与空间限制
掌握这些经典算法不仅能解决特定问题，更能培养解决问题的思维方式。建议读者在理解基本原理后，尝试在LeetCode等平台练习相关题目，如：
- #1143 最长公共子序列
- #300 最长递增子序列
- #354 俄罗斯套娃信封问题
通过实践来加深理解，并思考如何将这些算法应用到自己的项目中。
