最长公共子序列（LCS）与最长递增子序列（LIS） - 数据结构与算法-学习笔记-上海佼艾

一、概述

最长公共子序列（Longest Common Subsequence, LCS）与最长递增子序列（Longest Increasing Subsequence, LIS）是序列型动态规划（DP）中最经典的两大问题。它们不仅是算法面试的高频考点，更在工程实践中有着广泛应用——从 DNA 序列比对到文本 diff 工具，从数据压缩到推荐系统，处处可见二者的身影。

本讲将全面深入地剖析这两个问题：从基础定义出发，逐步推导 DP 递推公式，再到空间优化和进阶算法，最后讨论二者之间的内在联系与工程实践。通过对比学习，你将发现看似不同的 LCS 和 LIS 在数学结构上有着惊人的相似性。

前置知识：动态规划基本概念（最优子结构、重叠子问题）、数组与字符串操作、大 O 复杂度分析。

学习目标：① 掌握 LCS 的二维 DP 解法及路径回溯；② 掌握 LIS 的 O(n²) 和 O(n log n) 两种解法；③ 理解 LCS 与 LIS 之间的转化关系；④ 能够将算法应用到实际问题中。

二、最长公共子序列（LCS）

2.1 子序列 vs 子串——本质区别

在深入 LCS 之前，必须严格区分两个极易混淆的概念：子序列（Subsequence）和子串（Substring）。

子串：原字符串中连续的一段。例如 "abc" 的子串有 "a"、"ab"、"abc"、"b"、"bc"、"c"。
子序列：原字符串中删除任意个字符（可以不删）后得到的序列，不要求连续，但相对顺序保持不变。例如 "abc" 的子序列有 ""、"a"、"b"、"c"、"ab"、"ac"、"bc"、"abc"（注意 "ac" 不是子串而是子序列）。

特性	子串（Substring）	子序列（Subsequence）
连续性	必须连续	不要求连续
求解算法	滑动窗口 / KMP / 后缀数组	动态规划
时间复杂度	O(n+m)（KMP）	O(mn)（DP）
应用场景	字符串匹配、模式查找	DNA比对、diff工具、相似度度量

LCS 定义：给定两个序列 X = [x₁, x₂, ..., xₘ] 和 Y = [y₁, y₂, ..., yₙ]，找出一个长度最长的序列 Z，使得 Z 既是 X 的子序列又是 Y 的子序列。Z 的长度称为 LCS 的长度。

2.2 二维 DP 解法——递推公式推导

设 dp[i][j] 表示 X[1..i] 和 Y[1..j] 的 LCS 长度（为方便处理边界，下标从 1 开始）。考虑 X[i] 和 Y[j] 的关系：

情况一：X[i] == Y[j]，则该元素必然属于 LCS，于是 dp[i][j] = dp[i-1][j-1] + 1。
情况二：X[i] != Y[j]，则 LCS 要么来自 X[1..i-1] 和 Y[1..j]（即忽略 X[i]），要么来自 X[1..i] 和 Y[1..j-1]（忽略 Y[j]），取二者较大者：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始条件为 dp[0][j] = dp[i][0] = 0。最终答案在 dp[m][n]。递推公式如下：

                # 递推公式（伪代码）
                if X[i] == Y[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

下面给出完整的 Python 实现：

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    # 初始化 (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 X[i - 1] == Y[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]

# 测试
X = "ABCBDAB"
Y = "BDCABA"
print(lcs_length(X, Y))  # 输出: 4 (LCS可以是"BCAB"或"BDAB")

复杂度分析：时间 O(mn) —— 双层循环填充 DP 表；空间 O(mn) —— 需要存储完整的 DP 表。当 m、n 都在 10³ 级别时，O(mn) 空间约 1MB 尚可接受，但若达到 10⁴ 级别则需考虑空间优化。

2.3 路径回溯——输出具体的 LCS 序列

求出 LCS 长度后，我们往往还需要知道具体的子序列是什么。这可以通过路径回溯（backtracking）来实现：在填充 dp 表的同时记录方向（或直接从 dp 表逆向推导）。

def lcs_with_path(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 回溯：从 dp[m][n] 逆向走到 dp[0][0]
    i, j = m, n
    seq = []
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            seq.append(X[i - 1])  # 该字符属于 LCS
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1  # 向上走
        else:
            j -= 1  # 向左走

    seq.reverse()  # 回溯是反向的，需要反转
    return ''.join(seq)

print(lcs_with_path("ABCBDAB", "BDCABA"))  # 输出: BCAB 或 BDAB

回溯过程的要点：

当 X[i-1] == Y[j-1] 时，当前字符属于 LCS，沿对角线方向回溯（i--, j--），并将该字符加入结果。
当字符不相等时，比较 dp[i-1][j] 和 dp[i][j-1] 的大小，选择较大的方向回溯。若二者相等，则说明存在多条 LCS，此处我们选择向上走（也可向左）。
回溯结束后将收集到的字符反转，即得到一条 LCS。

2.4 空间优化——从 O(mn) 到 O(min(m,n))

注意到 dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1] 三个相邻的状态——即当前行只与上一行有关。因此我们可以用滚动数组（rolling array）将空间优化到 O(n)。

def lcs_rolling(X, Y):
    if len(X) < len(Y):  # 确保 Y 是较短者，进一步节省空间
        X, Y = Y, X
    m, n = len(X), len(Y)
    dp_prev = [0] * (n + 1)
    dp_curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp_curr[j] = dp_prev[j - 1] + 1
            else:
                dp_curr[j] = max(dp_prev[j], dp_curr[j - 1])
        dp_prev, dp_curr = dp_curr, dp_prev  # 交换引用

    return dp_prev[n]

然而滚动数组只能求长度，无法回溯出具体序列。若要同时输出序列，可以使用 Hirschberg 算法——该算法采用分治策略，每次将两个序列各切一半，递归求解，在 O(mn) 时间和 O(min(m,n)) 空间内输出 LCS。其核心思想是：对于某个切割点 i，正向计算第一半的 DP 行，反向计算第二半的 DP 行，找到最佳的拼接点。

Hirschberg 算法概要：① 若 m==0 或 n==0，返回空；② 若 m==1，在 Y 中查找该字符的位置；③ 取 X 的中位下标 mid，对 X[1..mid] 和 Y 做正向 DP（只保留一行），同时对 X[mid+1..m] 和 reverse(Y) 做反向 DP（也只保留一行），找出使二者之和最大的 split 位置；④ 递归求解 X[1..mid] 和 Y[1..split] 的 LCS，以及 X[mid+1..m] 和 Y[split+1..n] 的 LCS，拼接结果。该算法在面试中很少要求实现，但作为空间优化的重要思想值得了解。

三、最长递增子序列（LIS）

3.1 基础 DP 解法——O(n²) 递推

最长递增子序列问题：给定一个无序整数序列 nums，找出其中最长的严格递增的子序列（不要求连续）。

定义 dp[i] 为以 nums[i] 结尾的 LIS 长度。对每个 i，遍历所有 j < i，如果 nums[j] < nums[i]（严格递增条件），则 dp[i] = max(dp[i], dp[j] + 1)。初始时每个元素自身构成一个长度为 1 的子序列。最终答案是 max(dp)。

def lis_dp(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_dp(nums))  # 输出: 4 (LIS可以是[2,3,7,101]或[2,5,7,101])

复杂度分析：时间 O(n²)（双重循环），空间 O(n)。对于 n ≤ 10⁴ 可接受，更大的输入需要优化。

3.2 二分优化——O(n log n) 经典解法

O(n²) 解法在 n 较大时效率不足。经典优化思路是：维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾值。tails 本身一定是严格递增的，因此可以二分查找。

算法过程：遍历 nums，对每个元素 x，在 tails 中二分查找第一个 ≥ x 的位置 pos。如果 pos == len(tails)，说明 x 比所有 tails 元素都大，可以将 LIS 延长一个单位，将 x 追加到 tails 末尾；否则用 x 替换 tails[pos]（即保持长度不变，但使末尾值更小，为后续构建更长的子序列创造机会）。

import bisect

def lis_optimized(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)  # 第一个 >= x 的位置
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_optimized(nums))  # 输出: 4

为什么 tails 维护的是"最小末尾值"？以 nums = [3, 1, 2] 为例：

遍历 3：tails = [3]（长度为 1 的 LIS 最小末尾是 3）
遍历 1：二分找到 pos=0，替换为 1，tails = [1]（长度为 1 的 LIS 最小末尾降为 1）
遍历 2：二分找到 pos=1（超出尾部），追加 2，tails = [1, 2]

最终 tails = [1, 2]，长度 2 即为 LIS 长度。注意 tails 的内容不一定是真实的 LIS 序列，它只保证长度正确（但通过额外记录前驱可以输出具体序列）。

# 同时输出 LIS 具体序列（二分优化版）
def lis_with_path(nums):
    tails = []
    pre = [-1] * len(nums)  # 前驱索引
    indices = []  # tails 中每个位置对应的 nums 中的索引

    for i, x in enumerate(nums):
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
            indices.append(i)
        else:
            tails[pos] = x
            indices[pos] = i
        if pos > 0:
            pre[i] = indices[pos - 1]

    # 回溯 LIS 序列
    if not indices:
        return []
    seq = []
    k = indices[-1]
    while k != -1:
        seq.append(nums[k])
        k = pre[k]
    seq.reverse()
    return seq

print(lis_with_path([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出 [2, 3, 7, 18]

复杂度：时间 O(n log n)（每个元素一次二分查找），空间 O(n)。这是求解 LIS 长度的最优解法，在实际工程和面试中都是标准答案。

3.3 LIS 的变体问题

变体一：最长不降子序列（Longest Non-Decreasing Subsequence）。允许相等元素连续出现。只需将二分查找条件从 bisect_left（第一个 ≥ x）改为 bisect_right（第一个 > x），使得相等的值被追加而不是替换。

# 最长不降子序列（允许相等）
def lis_non_decreasing(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_right(tails, x)  # 关键：用 bisect_right
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

# 测试: [1,2,2,3] 的 LIS 严格版返回 3，不降版返回 4
print(lis_optimized([1,2,2,3]))       # 输出 3
print(lis_non_decreasing([1,2,2,3]))  # 输出 4

变体二：最长递减子序列（Longest Decreasing Subsequence, LDS）。只需将原数组取反（取负数）或将比较条件反转即可复用 LIS 算法。

# 最长递减子序列 = 对负值求 LIS
def lds(nums):
    neg = [-x for x in nums]
    return lis_optimized(neg)

print(lds([5, 4, 3, 2, 1]))  # 输出 5
print(lds([1, 3, 2, 4]))     # 输出 2 (3,2 或 3,1 等)

变体三：二维 LIS（俄罗斯套娃信封问题）。给定若干信封（宽度 w, 高度 h），一个信封能装入另一个当且仅当 w₁ < w₂ 且 h₁ < h₂。求最多能嵌套多少个。解法：按 w 升序排序，w 相同时按 h 降序排序，然后对 h 求 LIS。这种技巧巧妙地避免了 w 相等时的错误嵌套。

# 俄罗斯套娃信封问题
def max_envelopes(envelopes):
    # 按宽度升序，宽度相同时按高度降序
    envelopes.sort(key=lambda e: (e[0], -e[1]))
    # 对高度序列求 LIS
    heights = [h for _, h in envelopes]
    return lis_optimized(heights)

# 测试
env = [[5,4],[6,4],[6,7],[2,3]]
print(max_envelopes(env))  # 输出: 3 (2,3 → 5,4 → 6,7)

四、LCS 与 LIS 的转化

一个有趣的理论结果是：给定两个序列 X 和 Y，求 LCS 可以转化为在某个特定序列上求 LIS。这个转化依赖于"映射 + 位置序列"的思想。

具体做法：假设 X 中的元素互不相同（或有办法建立唯一映射），将 X 中的每个元素映射到它在 Y 中的出现位置（如果有多个出现位置，按降序排列）。将这些位置序列拼接后求 LIS，得到的 LIS 长度就是 LCS 的长度。此技巧常用于单串 LCS 问题（一个序列长度远大于另一个）的优化。

# LCS 转 LIS 优化（适用于 X 中元素互异且 len(Y) 较大）
def lcs_via_lis(X, Y):
    # 建立 Y 中字符到索引位置的映射
    pos_map = {}
    for idx, ch in enumerate(Y):
        pos_map.setdefault(ch, []).append(idx)

    # 对 X 中每个字符，取其位置列表（降序以保证子序列意义正确）
    seq = []
    for ch in X:
        if ch in pos_map:
            seq.extend(reversed(pos_map[ch]))

    # 对 seq 求 LIS 即得 LCS 长度
    return lis_optimized(seq)

print(lcs_via_lis("ABCBDAB", "BDCABA"))  # 输出: 4

为什么降序排列？假设 X 中有重复字符，如果直接按升序排列每个该字符在 Y 中的所有位置，那么在用同一个字符的多个位置构建 LIS 时，可能选择同一字符的多个位置，导致子序列意义错误。将位置降序排列保证每个字符至多贡献一次。

转化价值：当 len(X) ≤ len(Y) 且 X 中元素互异时，LCS 的时间复杂度由 O(mn) 降为 O(m log m)（构建映射 + LIS），这在 m 较小而 n 极大时非常有用。如字符串匹配中模式串远短于文本串的场景。

问题	最优时间复杂度	空间复杂度	核心思想
LCS（基础 DP）	O(mn)	O(mn)	二维 DP 表填充
LCS（滚动数组）	O(mn)	O(min(m,n))	只保留两行
LCS（Hirschberg）	O(mn)	O(min(m,n))	分治 + 正反向 DP
LCS（转 LIS 优化）	O(m log m)	O(m)	映射 + LIS 二分优化
LIS（基础 DP）	O(n²)	O(n)	dp[i] 以 i 结尾
LIS（二分优化）	O(n log n)	O(n)	维护最小末尾值 tails

五、实际应用场景

5.1 Unix diff 工具

Unix 的 diff 命令比较两个文件的不同之处，其核心算法正是 LCS。通过找出两文件之间的 LCS（即共同的行），diff 可以确定哪些行被删除、添加或修改，从而生成最小差异的补丁（patch）。GNU diff 的实现基于 Myers 算法，它在 LCS 框架上进一步优化了编辑距离计算。

原理示意：文件 A 的每一行作为一个元素，文件 B 的每一行作为另一个序列。求 LCS 后，属于 LCS 的行是"不变的"，A 中不在 LCS 的行是"删除的"，B 中不在 LCS 的行是"新增的"。

5.2 DNA / 蛋白质序列比对

生物信息学中，DNA 序列由 A、T、C、G 四种碱基组成，蛋白质序列由 20 种氨基酸组成。比对新测序的 DNA 与已知基因库的 LCS（更常用的是 Smith-Waterman 局部比对算法，基于 DP 思想），可以判断序列的相似性和进化关系。新冠病毒的变异追踪、亲子鉴定、物种演化分析背后都有 LCS 类算法的支撑。

5.3 推荐系统和用户行为分析

LCS 可以衡量两个用户行为序列的相似度：用户 A 购买了 [A, B, C, D]，用户 B 购买了 [A, C, D, E]，他们的 LCS 是 [A, C, D]，长度为 3，说明行为模式高度相似，可以互相推荐商品。LIS 则广泛应用于时间序列分析中的趋势判断：给定股价序列，求 LIS 可以得到最长上涨周期。

5.4 文本相似度与抄袭检测

将文档分割为句子或 n-gram 序列，计算两份文档的 LCS 长度除以平均长度，得到的比值可以作为相似度指标。配合语义哈希和倒排索引，可以快速在大规模文档库中检测高度相似的文本段落。高级的 MOSS 系统（斯坦福开发的编程作业抄袭检测）也使用了类似的序列比对技术。

5.5 数据压缩与编码

LCS 有助于寻找两个数据块之间的公共部分，这在增量压缩（如 rsync 算法）和版本控制系统中至关重要。Git 比较两个版本的代码时，本质上也是在行序列上求 LCS 并输出差异。

小结：LCS 和 LIS 绝非纸上谈兵的面试题。subversion 的底层 diff 算法、CRISPR 基因编辑中的序列比对、Netflix 的推荐系统、Git 的版本差异，以及大数据平台上的相似度去重——这些工业级系统在核心模块中都用到了序列 DP 的思想。掌握好这两个问题，就是掌握了序列型动态规划的半壁江山。

六、核心要点总结

① 子序列 ≠ 子串：子序列不要求连续，子串要求连续。LCS 和 LIS 处理的是子序列问题。

② LCS 递推公式：dp[i][j] = dp[i-1][j-1] + 1（X[i]==Y[j]）或 max(dp[i-1][j], dp[i][j-1]）（不等）。

③ 路径回溯：从 dp[m][n] 逆向走到 dp[0][0]，沿途收集对角方向匹配的字符。

④ LIS 核心递推：dp[i] = max(dp[j] + 1) 对所有 j < i 且 nums[j] < nums[i]。

⑤ 二分优化 LIS：维护 tails 数组（最小末尾值），对每个 x 找第一个 ≥ x 的位置替换或追加。

⑥ 变体处理：不降子序列用 bisect_right；递减子序列取负值处理。

⑦ LCS ↔ LIS 转化：通过位置映射将 LCS 转化为 LIS，适用于一长一短的序列。

⑧ 空间优化：滚动数组降为 O(n)；Hirschberg 分治在 O(n) 空间输出完整序列。

⑨ 工程应用：diff 工具、DNA 比对、推荐系统、抄袭检测、增量压缩等。

七、进一步思考与练习

思考题

如果要求 LCS 数量（有多少种不同的最长公共子序列），如何修改 DP 状态和递推？
给定三个字符串，求它们的三维 LCS（即最长的公共子序列同时是三者的子序列），递推公式如何扩展？复杂度是多少？
LIS 的二分优化版本中，tails 数组是否一定是递增的？尝试证明其单调性。
在 LCS 的路径回溯中，当 dp[i-1][j] == dp[i][j-1] 时，选择不同的方向可能得到不同的 LCS 序列。如何输出所有可能的 LCS？
研究一下 Myers diff 算法，它与 LCS 有何关系？为什么它更适合实际使用？

LeetCode 推荐习题

题号	题目	难度	涉及知识点
1143	最长公共子序列	中等	LCS 基础 DP
1035	不相交的线	中等	LCS 变形（画线不交叉）
300	最长递增子序列	中等	LIS 基础 / 二分优化
354	俄罗斯套娃信封问题	困难	二维 LIS + 排序技巧
673	最长递增子序列的个数	中等	LIS 计数
1713	得到子序列的最少操作数	困难	LCS 转 LIS 优化
712	两个字符串的最小ASCII删除和	中等	LCS 变形（加权）
516	最长回文子序列	中等	LCS 应用（字符串反转）

建议学习方法：先独立实现基础版 LCS 和 LIS，确保能正确输出长度和具体序列。然后尝试优化空间（滚动数组）。接着实现 LIS 的二分优化并理解 tails 数组的含义。最后挑战 LCS 转 LIS 的优化技巧。每道 LeetCode 题目都建议用 2-3 种方法实现，对比时间空间差异。