最长公共子序列

周子力大约 5 分钟教学文档动态规划-二维动态规划

题目描述

解题思路

这是一个经典的 最长公共子序列（LCS）问题，属于二维动态规划（双序列 DP）。

✅ 解题思路

设 text1 长度为 m，text2 长度为 n。

定义 dp[i][j] 表示：

text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度。

状态转移方程：

如果 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（空字符串与任何字符串的 LCS 为 0）
dp[i][0] = 0

最终答案：dp[m][n]

✅ 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)]
    
    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]

✅ 示例验证

print(longestCommonSubsequence("abcde", "ace"))   # 输出: 3
print(longestCommonSubsequence("abc", "abc"))     # 输出: 3
print(longestCommonSubsequence("abc", "def"))     # 输出: 0

全部符合题目要求。

⏱️ 复杂度分析

时间复杂度：O(m × n)
空间复杂度：O(m × n)

若需要优化空间，可使用滚动数组将空间压缩到 O(n)，但本题 m, n ≤ 1000，O(mn) 完全可接受。

✅ 此解法清晰、高效，是解决 LCS 问题的标准方法。

一、该 LCS 代码的注意事项（易错点 & 实践细节）

1. 索引偏移问题

dp[i][j] 对应的是 text1[0:i] 和 text2[0:j]（即前 i 个、前 j 个字符）。
因此比较字符时要用 text1[i-1] 和 text2[j-1]，不要写成 text1[i]，否则会越界或逻辑错误。

✅ 建议：始终明确 DP 表是否“多开一行一列”，这是处理字符串 DP 的常见技巧。

2. DP 表初始化方式

使用 [[0] * (n+1) for _ in range(m+1)] 是正确的。
❌ 错误写法：[[0] * (n+1)] * (m+1) —— 这会导致所有行共享同一个列表对象，修改一行会影响所有行。

✅ 启示：在 Python 中创建二维列表时，务必用列表推导式，避免浅拷贝陷阱。

3. 边界条件自动满足

由于我们初始化了第 0 行和第 0 列为 0，无需额外处理空字符串情况。
这种“哨兵”（sentinel）设计简化了主循环逻辑。

✅ 建议：在序列类 DP 中，主动增加边界维度（如长度+1）往往能大幅降低代码复杂度。

4. 字符比较的效率

题目保证只含小写字母，无需考虑 Unicode 或编码问题。
但在实际工程中，若涉及大文本或频繁比较，可考虑预处理（如转为整数数组）以加速。

5. 空间优化的可能性

当前使用 O(mn) 空间，但观察转移方程：

dp[i][j] 只依赖 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]

→ 可用滚动数组优化到 O(n) 空间：

prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m+1):
    for j in range(1, n+1):
        if text1[i-1] == text2[j-1]:
            curr[j] = prev[j-1] + 1
        else:
            curr[j] = max(prev[j], curr[j-1])
    prev, curr = curr, prev  # 复用数组
return prev[n]

虽然本题不需要，但这是面试中常被追问的优化点。

二、由本题得到的算法启发

1. 子序列 vs 子串：本质区别

子序列：不要求连续，关注相对顺序 → 适合 DP，状态表示“前缀匹配”。
子串：必须连续 → 通常用滑动窗口、KMP 或带“断点重置”的 DP（如 dp[i][j] = dp[i-1][j-1] + 1 if match else 0）。

✅ 启发：看到“子序列”，优先考虑前缀 DP；看到“子串”，考虑连续性约束。

2. 双序列问题的通用建模方法

凡是涉及两个序列的匹配、对齐、转换等问题，dp[i][j] 表示两个序列前缀的状态 是标准套路。
典型应用还包括：
- 编辑距离（插入/删除/替换）
- 最长重复子数组（注意：这是子串！）
- 交错字符串判定
- 序列对齐（生物信息学）

✅ 启发：掌握“双序列 DP 模板”，能快速迁移解决一类问题。

3. 动态规划的本质：状态定义决定一切

本题若错误地定义 dp[i][j] 为“以 text1[i] 和 text2[j] 结尾的 LCS”，就会陷入无法处理“跳过字符”的困境。
正确的状态定义（前缀而非后缀）天然支持“跳过”操作（通过 max(dp[i-1][j], dp[i][j-1])）。

✅ 启发：花 80% 时间思考状态定义，20% 写转移方程。

4. LCS 是许多高级问题的基础

文件 diff 工具（如 git diff）底层基于 LCS 或其变种。
在自然语言处理中，用于衡量句子相似度（虽然现在更多用语义模型，但 LCS 仍是 baseline）。
在生物信息学中，DNA 序列比对也源于此类思想。

✅ 启发：基础算法往往是现实系统的核心组件。

5. DP 与递归+记忆化的等价性

本题也可用递归 + @cache 实现：

@cache
def dfs(i, j):
    if i < 0 or j < 0:
        return 0
    if text1[i] == text2[j]:
        return dfs(i-1, j-1) + 1
    return max(dfs(i-1, j), dfs(i, j-1))
return dfs(len(text1)-1, len(text2)-1)

这种写法更直观，但可能栈溢出（Python 递归深度限制），且常数较大。
迭代 DP 更稳定，适合竞赛和工程。

✅ 启发：递归自顶向下便于理解，迭代自底向上便于优化。

总结

维度	关键点
实现注意	索引偏移、二维列表创建、边界处理、空间优化
算法启发	子序列建模、双序列 DP 通用框架、状态定义优先、LCS 的广泛应用

掌握这些细节和思想，不仅能正确解出 LCS，还能举一反三，应对更复杂的序列动态规划问题。