动态规划：子序列模型完全指南-171主机测评

第一部分：基础概念与辨析

1.1 什么是子序列？

定义：子序列（Subsequence）是指从原序列中删除若干元素（也可以不删）后，剩下的元素保持原有的相对顺序形成的序列。

与子数组（Subarray）的区别：子数组必须是连续的；子序列可以不连续。

1.2 动态规划的核心思想

解决子序列问题，DP 状态通常定义为：

以 i 结尾：dp[i] 表示以第 i 个元素结尾的某种子序列的性质（如长度、个数、最大和）。这是处理“线性结构”最常用的技巧，它保证了状态的“无后效性”，因为最后一个元素固定了。
前 i 个元素：dp[i] 表示考虑前 i 个元素的情况，常用于二维 DP（如 LCS）。

第二部分：基石模型

模型一：最长递增子序列 (LIS)

这是最经典的 1D/1D 动态规划问题。

2.1 朴素解法 (O(n^2))

状态定义：dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。
状态转移：dp[i] = max(dp[j]) + 1，其中 0 <= j < i 且 nums[j] < nums[i]。
初始化：dp[i] = 1（每个元素自身构成一个长度为 1 的子序列）。
最终答案：max(dp[0..n-1])。

2.2 贪心 + 二分优化 (O(n log n))

核心思想：维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。
贪心策略：我们希望在相同长度下，末尾元素越小，后面接上新元素的可能性越大。
算法流程：
遍历 num。
在 tails 中二分查找第一个大于等于 num 的位置（lower_bound）。
如果找到，替换该位置为 num；如果没找到（即 num 大于 tails 所有元素），则将 num 追加到末尾。
最终 tails 的长度即为 LIS 的长度。
注意：tails 数组存储的并不是真正的 LIS 序列，但长度是正确的。

2.3 严格递增 vs 非严格递增

严格递增 (nums[j] < nums[i])：二分查找 lower_bound（第一个 >= x）。
非严格递增 (nums[j] <= nums[i])：二分查找 upper_bound（第一个 > x）。

2.4 输出具体的 LIS 路径

虽然贪心+二分可以得到长度，但若要输出序列，通常需要结合 DP 数组 + 贪心倒推。

使用 O(n log n) 方法记录每个元素作为末尾时，当前 LIS 的长度 len[i]。

从后向前遍历，找到第一个长度等于 maxLen 的元素，然后找长度减 1 且值小于当前元素的元素，以此类推。

模型二：最长公共子序列 (LCS)

给定两个序列 text1 和 text2，求最长的公共子序列。

3.1 经典二维 DP (O(n*m))

状态定义：dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度。
状态转移：

如果 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[i] 只依赖 dp[i-1] 和当前行，可以优化为一维数组（滚动数组），注意内层循环需要逆序或保存左上角值。

3.2 转化为 LIS 的特殊情况

当其中一个序列的元素互不相同时，可以将 LCS 转化为 LIS 问题（O(n log n)）。

方法：将序列 A 中的元素映射为其下标（位置），然后遍历序列 B，将 B 中元素在 A 中的位置取出形成新数组，求该数组的 LIS。
原理：LCS 要求顺序一致，映射到下标后，B 中的下标序列的递增子序列对应了 A 中顺序一致的子序列。

第三部分：经典变体与进阶

4.1 最长公共上升子序列 (LCIS)

结合了 LIS 和 LCS 的特点。给定两个序列，求既是公共子序列又是上升子序列的最长序列。

解法一：O(n^3)
dp[i][j] 表示以 A 的第 i 个元素结尾，且与 B 的前 j 个元素形成的 LCIS 长度。转移需要枚举 k。

解法二：O(n^2) 优化（经典优化技巧）

状态定义：dp[i][j] 表示 A 的前 i 个元素与 B 的前 j 个元素形成的，且以 B[j] 结尾的 LCIS 长度。
转移：
- 若 A[i] != B[j]：dp[i][j] = dp[i-1][j]
- 若 A[i] == B[j]：dp[i][j] = max(1, max(dp[i-1][k] + 1))，其中 k < j 且 B[k] < A[i]。
优化点：在遍历 i 固定时，维护一个 maxVal 变量，记录当前遇到的小于 A[i] 的最大 dp[i-1][k] 值，实现 O(1) 转移。

4.2 子序列的最大和

问题：求最大和递增子序列（不一定最长，要求和最大）。
解法：dp[i] = nums[i] + max(dp[j])，其中 j < i 且 nums[j] < nums[i]。如果没有符合条件的 j，则 dp[i] = nums[i]。
复杂度：O(n^2)。（通常不需要二分优化，因为和与长度无关，贪心失效）

4.3 最长回文子序列 (LPS)

给定一个字符串，求最长回文子序列的长度。

解法一：转化为 LCS
将原字符串反转，求原串与反串的 LCS。
解法二：区间 DP
dp[i][j] 表示子串 s[i..j] 的最长回文子序列长度。
- 转移：
  - i == j：dp[i][j] = 1
  - s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2
  - s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- 遍历顺序：按长度递增，或从下往上，从左往右。

4.4 编辑距离

虽然不是直接的子序列问题，但它是 LCS 的广义形式，定义了替换、插入、删除的代价。

dp[i][j] 表示 word1 前 i 个转成 word2 前 j 个的最小操作数。

第四部分：数据结构优化与高阶技巧

当状态转移需要从所有满足条件的 j < i 且 nums[j] < nums[i] 中取最值时，朴素 O(n^2) 会超时。此时需要利用值域进行优化。

5.1 树状数组 / 线段树优化 (基于值域的 DP)

适用于 LIS 及其变种，当元素值范围较小时（或可以离散化）。

核心：将 dp[i] 存储在数据结构中，键为 nums[i]，值为 dp[i]。
查询：当处理 nums[i] 时，查询所有 < nums[i] 的最大 dp 值。
更新：将 dp[i] 更新到树状数组的 nums[i] 位置上。
优势：时间复杂度 O(n log M)，M 是值域大小。不仅可以处理 LIS，还可以处理带权重的 LIS 或特定限制（如 nums[i] – nums[j] >= k 等）。

5.2 多维偏序问题

将子序列问题升维。例如：“俄罗斯套娃信封问题”（LeetCode 354）。

问题：给定信封 (w, h)，求最多能嵌套多少层（必须 w1 < w2 且 h1 < h2）。
解法：
按宽度升序，宽度相同时按高度降序排序。
对高度序列求 LIS。
为什么宽度相同要降序？因为严格递增要求宽度不能相等。如果宽度相同按升序，LIS 会把相同宽度的信封也算进去（因为高度是递增的），这是错误的。降序保证了相同宽度的信封不会出现在递增子序列中。

5.3 带限制条件的子序列

差值限制：如 nums[i] – nums[j] >= k。利用线段树查询区间 [minVal, nums[i]-k] 的最大值。
倍数/约数限制：如 nums[i] % nums[j] == 0。利用预处理约数，枚举 nums[i] 的因子进行转移。

第五部分：计数问题

不仅求最值，还要统计个数。

6.1 LIS 的个数

求最长递增子序列的个数（LeetCode 673）。

方法：维护 length[i] 和 count[i]。
- 遍历 j < i，若 nums[j] < nums[i]：
  - 如果 length[j] + 1 > length[i]：更新长度，并更新计数为 count[j]。
  - 如果 length[j] + 1 == length[i]：累加计数 count[i] += count[j]。
注意：需要处理重复值，且需要 O(n^2) 或结合线段树维护区间最大值及对应计数。

6.2 不同的子序列

给定字符串 s 和 t，求 t 作为 s 的子序列出现的次数（LeetCode 115）。

状态：dp[i][j] 表示 s 的前 i 个字符中，t 的前 j 个字符作为子序列出现的次数。
转移：
- dp[i][j] = dp[i-1][j] （不使用 s[i]）
- 如果 s[i-1] == t[j-1]：dp[i][j] += dp[i-1][j-1]（使用 s[i]）
空间优化：可优化为一维，但内层 j 需要逆序。

第六部分：实战演练与思维进阶

7.1 序列自动机

用于快速判断一个字符串是否是另一个字符串的子序列，或者快速寻找子序列匹配位置。

定义：next[i][c] 表示在位置 i 之后（不包括 i），字符 c 第一次出现的位置。
构建：从后向前扫描。
应用：可以解决多模式串匹配、子序列自动机 DP（求本质不同的子序列个数）。

7.2 子序列的字典序问题

最小字典序的 LIS：在求 LIS 时，维护 tails 数组时，如果遇到相等的情况（tails[pos] == num），贪心选择保留原有的还是替换？为了字典序最小，通常选择保留靠左的，或者使用特定的“替换”策略。
所有子序列的字典序排序：涉及后缀自动机或后缀数组。

7.3 环形数组的 LIS

方法：破环成链（将数组复制一份拼接），限制长度不超过 n。

7.4 DP 套 DP

有些复杂问题，如“最长公共子序列的个数”或者“在 LIS 长度为 k 的条件下求方案数”，可能需要将 DP 本身作为状态（DP 内部再跑 DP）。

第七部分：总结与常见误区

8.1 时间复杂度分析

模型时间复杂度空间复杂度适用场景

LIS (朴素)	O(n^2)	O(n)	n <= 5000
LIS (二分)	O(n log n)	O(n)	n <= 1e5，仅求长度
LIS (BIT)	O(n log M)	O(M)	带权、多维、或需输出计数
LCS (朴素)	O(n*m)	O(n*m)	n*m <= 1e7
LCS (转LIS)	O(n log n)	O(n)	其中一个序列元素不重复
LCIS	O(n*m)	O(n*m)	n,m <= 3000
区间 DP (LPS)	O(n^2)	O(n^2)	n <= 5000

8.2 易错点

初始化：LIS 初始化为 1，而非 0。

边界条件：LCS 中 dp[0][j] 和 dp[i][0] 均为 0。

非严格 vs 严格：二分查找时 lower_bound 和 upper_bound 的选择决定了是否允许相等元素。

维度顺序：在滚动数组优化时，要特别注意依赖方向，防止值被提前覆盖。

值域离散化：使用 BIT 优化时，如果原数组值较大且不需要关心相对大小外的信息，务必离散化。

附录：LeetCode / 竞赛经典例题索引

基础 LIS：LeetCode 300. Longest Increasing Subsequence
信封嵌套：LeetCode 354. Russian Doll Envelopes
LIS 个数：LeetCode 673. Number of Longest Increasing Subsequence
最长公共子序列：LeetCode 1143. Longest Common Subsequence
最长回文子序列：LeetCode 516. Longest Palindromic Subsequence
编辑距离：LeetCode 72. Edit Distance
不同的子序列：LeetCode 115. Distinct Subsequences
最大和递增子序列：LeetCode (面试题 17.08. Circus Tower LCCI 或经典变种)
序列自动机：Codeforces / LeetCode 792. Number of Matching Subsequences