30 秒速览

  • 子序列：不连续的子串
  • 子串：连续的子串
  • 核心模型：LIS（最长递增子序列）、LCS（最长公共子序列）
  • 状态定义：通常以位置 i/j 结尾

一、直觉建立

子序列 vs 子串

原串：abcde

子序列（不连续）：
- ace ✓
- bd ✓
- aec ✗（顺序不对）

子串（连续）：
- abc ✓
- cde ✓
- ace ✗（不连续）

子序列 DP 的本质

考虑每个位置的状态，通过比较当前元素与之前元素的关系来转移。

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

问题定义

给定数组，找到最长严格递增子序列的长度。

示例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4（[2,3,7,101] 或 [2,3,7,18]）

方法一：O(n²) DP

状态定义：

  • dp[i] = 以 nums[i] 结尾的最长递增子序列长度

转移方程：

dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n  # 每个元素自己就是一个长度为 1 的子序列

    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) if dp else 0

复杂度：时间 O(n²)，空间 O(n)

方法二：O(n log n) 贪心 + 二分

维护一个数组 tails，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []

    for num in nums:
        # 找到第一个 >= num 的位置
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            tails.append(num)  # 可以扩展
        else:
            tails[pos] = num    # 替换，保持更小的末尾

    return len(tails)

为什么这样是对的？

  • 我们想要更长的递增子序列
  • 末尾越小，后面越容易扩展
  • tails 不一定是实际的 LIS，但长度是对的

复杂度：时间 O(n log n)，空间 O(n)

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

问题定义

给定两个字符串，找到最长公共子序列的长度。

示例：

输入：text1 = "abcde", text2 = "ace"
输出：3（"ace"）

二维 DP

状态定义：

  • dp[i][j] = text1[0:i] 和 text2[0:j] 的 LCS 长度

转移方程：

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

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]

复杂度：时间 O(mn)，空间 O(mn)

空间优化

由于只依赖上一行，可以压缩到一维。

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)

    for i in range(1, m + 1):
        prev = 0  # dp[i-1][j-1]
        for j in range(1, n + 1):
            temp = dp[j]  # 保存旧的 dp[j] 作为下一次的 prev
            if text1[i-1] == text2[j-1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j-1])
            prev = temp

    return dp[n]

四、典型例题

例题 1：LC 300. 最长递增子序列

已在上面讲解。

例题 2：LC 1143. 最长公共子序列

已在上面讲解。

例题 3：LC 72. 编辑距离

题目：给定两个单词，计算将 word1 转换成 word2 使用的最少操作数（插入、删除、替换）。

示例：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse → rorse (替换 h → r)
rorse → rose (删除 r)
rose → ros (删除 e)

思路

状态定义：

  • dp[i][j] = 将 word1[0:i] 转换为 word2[0:j] 的最少操作数

转移方程：

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]  # 不需要操作
else:
    dp[i][j] = min(
        dp[i-1][j] + 1,     # 删除 word1[i-1]
        dp[i][j-1] + 1,     # 插入（相当于删除 word2[j-1]）
        dp[i-1][j-1] + 1    # 替换
    )

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化
    for i in range(m + 1):
        dp[i][0] = i  # 删除 i 个字符
    for j in range(n + 1):
        dp[0][j] = j  # 插入 j 个字符

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,     # 删除
                    dp[i][j-1] + 1,     # 插入
                    dp[i-1][j-1] + 1    # 替换
                )

    return dp[m][n]

复杂度：时间 O(mn)，空间 O(mn)

例题 4：LC 392. 判断子序列

题目：判断 s 是否是 t 的子序列。

方法一：双指针

def isSubsequence(s: str, t: str) -> bool:
    i, j = 0, 0

    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1

    return i == len(s)

复杂度：时间 O(n)，空间 O(1)

方法二：DP（预处理 t）

如果有大量 s 需要判断，可以预处理 t。

def isSubsequence(s: str, t: str) -> bool:
    # dp[i][c] = t[i:] 中字符 c 第一次出现的位置
    n = len(t)
    dp = [[-1] * 26 for _ in range(n + 1)]

    for i in range(n - 1, -1, -1):
        for c in range(26):
            dp[i][c] = dp[i + 1][c]
        dp[i][ord(t[i]) - ord('a')] = i

    pos = 0
    for c in s:
        if dp[pos][ord(c) - ord('a')] == -1:
            return False
        pos = dp[pos][ord(c) - ord('a')] + 1

    return True

例题 5：LC 115. 不同的子序列

题目：计算 s 中有多少个子序列等于 t。

示例：

输入：s = "rabbbit", t = "rabbit"
输出：3

思路

状态定义：

  • dp[i][j] = s[0:i] 中有多少个子序列等于 t[0:j]

转移方程：

if s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    #           用 s[i-1] 匹配      不用 s[i-1] 匹配
else:
    dp[i][j] = dp[i-1][j]

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 空字符串 t 可以由任何 s 匹配（选择不选任何字符）
    for i in range(m + 1):
        dp[i][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j]
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j-1]

    return dp[m][n]

复杂度：时间 O(mn)，空间 O(mn)

例题 6：LC 583. 两个字符串的删除操作

题目：给定两个字符串，找到使两个字符串相等所需的最小删除次数。

思路

等价于：找最长公共子序列，然后删除多余字符。

最小删除次数 = len(word1) + len(word2) - 2 * LCS

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

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

    lcs = dp[m][n]
    return m + n - 2 * lcs

例题 7：LC 674. 最长连续递增序列

题目：找最长连续递增子序列。

思路

因为是连续的，只需要比较相邻元素。

def findLengthOfLCIS(nums: list[int]) -> int:
    if not nums:
        return 0

    max_len = 1
    cur_len = 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            cur_len += 1
            max_len = max(max_len, cur_len)
        else:
            cur_len = 1

    return max_len

复杂度：时间 O(n)，空间 O(1)

五、子序列问题模板

LIS 模板

# O(n²) DP
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)

# O(n log n) 贪心 + 二分
tails = []
for num in nums:
    pos = bisect.bisect_left(tails, num)
    if pos == len(tails):
        tails.append(num)
    else:
        tails[pos] = num

LCS 模板

dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s1[i-1] == s2[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 = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
    dp[i][0] = i
for j in range(n + 1):
    dp[0][j] = j

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

六、常见错误与陷阱

错误 1：LIS 的 dp 含义

# 错误理解：dp[i] = 前 i 个元素的 LIS
# 正确理解：dp[i] = 以 nums[i] 结尾的 LIS

# dp[i] 不一定是全局最优，需要取 max
return max(dp)

错误 2：LCS 下标处理

# dp[i][j] 对应 s1[i-1] 和 s2[j-1]
# 因为 dp[0][*] 和 dp[*][0] 表示空串
if s1[i-1] == s2[j-1]:  # 不是 s1[i]
    ...

错误 3：编辑距离初始化

# 忘记初始化边界
# word1 -> "" 需要删除所有字符
# "" -> word2 需要插入所有字符
for i in range(m + 1):
    dp[i][0] = i
for j in range(n + 1):
    dp[0][j] = j

七、复盘清单

触发信号

  • “子序列"关键词
  • 两个字符串比较
  • 递增/递减序列
  • 编辑/删除/插入操作

类型判断

  • 单数组递增 → LIS
  • 两字符串公共 → LCS
  • 两字符串变换 → 编辑距离
  • 子序列计数 → DP + 组合计数

实现检查

  • 状态定义正确
  • 下标处理正确（-1 问题）
  • 初始化正确
  • 返回值正确

八、题目清单

LIS 系列

题号题目难度考点
300最长递增子序列MediumLIS 模板
674最长连续递增序列Easy连续版
646最长数对链MediumLIS 变体
354俄罗斯套娃信封Hard2D LIS

LCS 系列

题号题目难度考点
1143最长公共子序列MediumLCS 模板
392判断子序列Easy双指针/DP
115不同的子序列Hard计数
583两个字符串删除操作MediumLCS 应用
718最长重复子数组Medium连续版

编辑距离

题号题目难度考点
72编辑距离Hard经典模板