最长公共子序列（LCS）
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。
一个字符串的 子序列 是指这样一个新字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是。
示例
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
循序渐进讲解
第一步：理解问题核心
我们的目标是找到两个字符串中都出现的一个序列，这个序列在原字符串中不需要连续，但必须保持原有的先后顺序。暴力解法是枚举一个字符串的所有子序列，检查它是否也是另一个字符串的子序列，但这样时间复杂度是指数级的，不可行。
第二步：引入动态规划思路
动态规划非常适合解决这种具有重叠子问题和最优子结构的问题。我们定义一个二维数组（或称DP表）dp[i][j]，其含义是：
dp[i][j] 表示 text1 的前 i 个字符（即 text1[0..i-1]）和 text2 的前 j 个字符（即 text2[0..j-1]）的最长公共子序列的长度。
第三步：建立DP表并初始化
我们创建一个大小为 (len(text1)+1) x (len(text2)+1) 的二维数组 dp。多出来的一行一列（即 i=0 或 j=0 的行和列）表示空字符串的情况。
- 初始化：
dp[0][j] = 0（text1是空字符串，与任何text2的子序列长度都是0） - 初始化：
dp[i][0] = 0（text2是空字符串，与任何text1的子序列长度都是0）
第四步：推导状态转移方程
现在我们要思考如何根据已知状态推导出 dp[i][j]。这里有两种情况：
-
text1[i-1]等于text2[j-1](注意，因为我们的i和j是从1开始计数的，所以对应字符下标是i-1和j-1)。
这意味著我们找到了一个公共字符。这个字符一定属于最长公共子序列。那么，text1[0..i-1]和text2[0..j-1]的LCS长度，就等于text1[0..i-2]和text2[0..j-2]的LCS长度再加1。
公式：dp[i][j] = dp[i-1][j-1] + 1 -
text1[i-1]不等于text2[j-1]。
这意味著当前两个字符不能同时出现在公共子序列中。那么，text1[i-1]和text2[j-1]就不可能同时出现在LCS中。我们需要考虑两种子情况：- LCS可能来自于
text1[0..i-1]和text2[0..j-2]（即忽略text2的当前字符）。 - LCS也可能来自于
text1[0..i-2]和text2[0..j-1]（即忽略text1的当前字符）。
我们应该取这两种可能中的最大值，以保证找到的是“最长”的公共子序列。
公式：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- LCS可能来自于
第五步：填表过程示例
让我们用示例 text1 = "abcde", text2 = "ace" 来手动填表。
初始化的DP表如下（- 表示空字符串）：
| - | a | c | e | |
|---|---|---|---|---|
| - | 0 | 0 | 0 | 0 |
| a | 0 | |||
| b | 0 | |||
| c | 0 | |||
| d | 0 | |||
| e | 0 |
现在我们按行（或按列）填充：
i=1, j=1: text1[0]='a', text2[0]='a'，相等。dp[1][1] = dp[0][0] + 1 = 0+1 = 1i=1, j=2: text1[0]='a', text2[1]='c'，不等。dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1i=1, j=3: text1[0]='a', text2[2]='e'，不等。dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 1) = 1
第一行填完：
| - | a | c | e | |
|---|---|---|---|---|
| - | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | |||
| c | 0 | |||
| d | 0 | |||
| e | 0 |
继续填充：
i=2, j=1: 'b' 和 'a' 不等。dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1i=2, j=2: 'b' 和 'c' 不等。dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1i=2, j=3: 'b' 和 'e' 不等。dp[2][3] = max(dp[1][3], dp[2][2]) = max(1, 1) = 1
以此类推，最终填满的DP表如下：
| - | a | c | e | |
|---|---|---|---|---|
| - | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
右下角的值 dp[5][3] = 3 就是我们的答案。
第六步：算法实现（Python）
根据上述思路，我们可以写出代码。
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# 创建 (m+1) x (n+1) 的DP表，初始化为0
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 从1开始遍历，因为0行0列已经初始化好了
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
# 字符匹配，长度加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]
第七步：复杂度分析
- 时间复杂度：O(m * n)，其中 m 和 n 分别是两个字符串的长度。我们需要填充一个 m x n 的DP表。
- 空间复杂度：O(m * n)，用于存储DP表。可以通过滚动数组优化到 O(min(m, n))。
总结
解决最长公共子序列问题的核心是定义清晰的DP状态，并推导出正确的状态转移方程。关键在于理解当末尾字符相等时，LCS长度可以加1；当不等时，需要从两个可能的子问题中选取最优解。通过自底向上填表，最终得到答案。