序列问题

序列问题概述[编辑 | 编辑源代码]

序列问题指在给定序列（如数组、字符串等线性结构）上应用动态规划求解的经典问题类型，其核心是通过子序列的最优解递推全局最优解。这类问题通常具有以下特征：

问题可分解为重叠子问题（如以某个位置结尾的子序列）
存在明确的状态转移关系（如前驱状态的选择影响当前状态）

常见问题分类[编辑 | 编辑源代码]

典型序列问题类型
类型	示例问题	状态定义关键
单序列问题	最长递增子序列	`dp[i]`表示以第i项结尾的解
双序列问题	最长公共子序列	`dp[i][j]`表示两序列前i/j项的解
区间问题	矩阵链乘法	`dp[i][j]`表示区间i到j的解

核心解题框架[编辑 | 编辑源代码]

状态设计原则[编辑 | 编辑源代码]

1. 维度选择：根据问题复杂度决定使用一维/二维DP 2. 语义明确：dp[i]或dp[i][j]需有清晰数学含义 3. 边界处理：初始状态（如空序列）需要明确定义

通用解法步骤[编辑 | 编辑源代码]

# 伪代码框架
def sequence_dp(seq):
    n = len(seq)
    # 1. 初始化DP数组（含边界条件）
    dp = [[0]*(n+1) for _ in range(m+1)] 
    
    # 2. 状态转移
    for i in range(1, n+1):
        for j in range(1, m+1):
            if condition(seq[i-1], seq[j-1]):
                dp[i][j] = dp[i-1][j-1] + 1  # 示例转移方程
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 3. 返回最终结果
    return dp[n][m]

经典问题详解[编辑 | 编辑源代码]

最长递增子序列 (LIS)[编辑 | 编辑源代码]

问题描述：给定整数序列，找到最长的严格递增子序列长度

状态转移方程： 解析失败 (语法错误): {\displaystyle dp[i] = \max_{\substack{0 \leq j < i \\ seq[j] < seq[i]}}(dp[j] + 1) }

示例实现：

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

# 输入: [10,9,2,5,3,7,101,18]
# 输出: 4 （对应子序列[2,5,7,101]）

最长公共子序列 (LCS)[编辑 | 编辑源代码]

状态转移方程： $d p [i] [j] = {\begin{cases} d p [i - 1] [j - 1] + 1 & if t e x t 1 [i - 1] = t e x t 2 [j - 1] \\ \max (d p [i - 1] [j], d p [i] [j - 1]) & otherwise \end{cases}$

可视化过程：

实际应用案例[编辑 | 编辑源代码]

基因组比对[编辑 | 编辑源代码]

在生物信息学中，LCS算法用于DNA序列比对：

输入：两条碱基序列（如"AGCAT"和"GAC"）
输出：最大匹配片段（"AC"或"GA"）

版本控制差异分析[编辑 | 编辑源代码]

Git等工具使用LCS变种（如Myers差分算法）比较文件修改：

def text_diff(old, new):
    # 基于LCS实现的行级差异比较
    lcs = find_lcs(old.splitlines(), new.splitlines())
    return generate_edit_script(lcs)

进阶技巧[编辑 | 编辑源代码]

空间优化[编辑 | 编辑源代码]

当状态转移仅依赖有限前驱状态时，可使用滚动数组：

def lcs_space_optimized(text1, text2):
    prev = [0] * (len(text2)+1)
    for i in range(1, len(text1)+1):
        curr = [0]*(len(text2)+1)
        for j in range(1, len(text2)+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
    return prev[-1]