编辑“︁序列问题”︁

{{Note|本条目是[[动态规划]]章节的子专题，建议先掌握基础概念后再学习序列问题。}}

== 序列问题概述 ==
'''序列问题'''指在给定序列（如数组、字符串等线性结构）上应用动态规划求解的经典问题类型，其核心是通过子序列的最优解递推全局最优解。这类问题通常具有以下特征：
* 问题可分解为'''重叠子问题'''（如以某个位置结尾的子序列）
* 存在明确的'''状态转移关系'''（如前驱状态的选择影响当前状态）

=== 常见问题分类 ===
{| class="wikitable"
|+ 典型序列问题类型
! 类型 !! 示例问题 !! 状态定义关键
|-
| '''单序列问题''' || [[最长递增子序列]] || <code>dp[i]</code>表示以第i项结尾的解
|-
| '''双序列问题''' || [[最长公共子序列]] || <code>dp[i][j]</code>表示两序列前i/j项的解
|-
| '''区间问题''' || [[矩阵链乘法]] || <code>dp[i][j]</code>表示区间i到j的解
|}

== 核心解题框架 ==
=== 状态设计原则 ===
1. '''维度选择'''：根据问题复杂度决定使用一维/二维DP
2. '''语义明确'''：<code>dp[i]</code>或<code>dp[i][j]</code>需有清晰数学含义
3. '''边界处理'''：初始状态（如空序列）需要明确定义

=== 通用解法步骤 ===
<syntaxhighlight lang="python">
# 伪代码框架
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]
</syntaxhighlight>

== 经典问题详解 ==
=== 最长递增子序列 (LIS) ===
'''问题描述'''：给定整数序列，找到最长的严格递增子序列长度

'''状态转移方程'''：
<math>
dp[i] = \max_{\substack{0 \leq j < i \\ seq[j] < seq[i]}}(dp[j] + 1)
</math>

'''示例实现'''：
<syntaxhighlight lang="python">
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]）
</syntaxhighlight>

=== 最长公共子序列 (LCS) ===
'''状态转移方程'''：
<math>
dp[i][j] = \begin{cases} 
dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\
\max(dp[i-1][j], dp[i][j-1]) & \text{otherwise}
\end{cases}
</math>

'''可视化过程'''：
<mermaid>
graph LR
    A["dp[i-1][j-1]"] -->|字符匹配| B["dp[i][j]=dp[i-1][j-1]+1"]
    C["dp[i-1][j]"] -->|字符不匹配| D["dp[i][j]=max(←,↑)"]
    E["dp[i][j-1]"] -->|字符不匹配| D
</mermaid>

== 实际应用案例 ==
=== 基因组比对 ===
在生物信息学中，LCS算法用于DNA序列比对：
* 输入：两条碱基序列（如"AGCAT"和"GAC"）
* 输出：最大匹配片段（"AC"或"GA"）

=== 版本控制差异分析 ===
Git等工具使用LCS变种（如Myers差分算法）比较文件修改：
<syntaxhighlight lang="python">
def text_diff(old, new):
    # 基于LCS实现的行级差异比较
    lcs = find_lcs(old.splitlines(), new.splitlines())
    return generate_edit_script(lcs)
</syntaxhighlight>

== 进阶技巧 ==
=== 空间优化 ===
当状态转移仅依赖有限前驱状态时，可使用滚动数组：
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

=== 问题变形 ===
* '''带权LCS'''：每个字符匹配有权重值
* '''多序列LCS'''：扩展至三个及以上序列比较
* '''受限LIS'''：增加上升幅度限制条件

{{Warning|注意区分子序列（可不连续）与子串（必须连续）的不同定义！}}

== 习题推荐 ==
* 基础：[[最长连续递增序列]]（子串问题）
* 进阶：[[编辑距离]]（带操作权重的序列比对）
* 挑战：[[俄罗斯套娃信封问题]]（二维LIS变形）

== 参见 ==
* [[动态规划的时间复杂度优化]]
* [[记忆化搜索与DP的转换]]
* [[字符串匹配算法]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]