外观
23 - 序列动态规划:最长递增子序列与最长公共子序列
前置阅读:21 - 动态规划的状态与转移、06 - 二分查找与答案搜索。
字符串比较前要明确比较单位:Java 的 UTF-16
char是一个 16 位编码单元;Unicode Code Point(码点)表示 Unicode 编码空间中的一个值,有些码点需要两个char表示;用户感知字符还可能由多个码点组成。本文代码按char比较,这三种语义不能混用。
摘要
给定一组数,怎样选出尽可能长的递增序列?给定两份文本,怎样找出顺序一致的公共部分?这两类问题都允许跳过元素,但不允许改变原有顺序,适合用序列动态规划(DP)保存较小问题的答案,再逐步扩展。
先区分两个概念:子数组和子串必须连续,子序列可以跳过元素。例如 [3, 5, 2, 4] 中的 [3, 4] 是子序列,却不是子数组。本文先推导最长递增子序列(LIS)和最长公共子序列(LCS)的基础状态,再解释 LIS 的二分优化,以及从长度恢复实际序列所需的信息。
1. LIS:最长递增子序列
LIS 是 Longest Increasing Subsequence 的缩写。本文的“递增”指严格递增,即后一个值必须大于前一个值,相等的值不能接续。
如果只知道前面元素能组成的最大长度,却不知道序列结尾,就无法判断当前值能否接上。因此定义 dp[i] 为必须以 values[i] 结尾的最长递增子序列长度。
计算这个状态时,当前元素单独就能构成长度为 1 的子序列,所以初值为 1。然后枚举它前面的下标 j:只有 j < i 且 values[j] < values[i],才能把当前元素接到以 j 结尾的序列后面,得到长度 dp[j] + 1。在所有合法前驱中取最大值即可;这里的前驱指所选子序列中的上一个元素,不必与当前元素相邻。
按下标从小到大计算,读取的 dp[j] 都已确定。整体最优解可能在任意位置结束,因此答案是所有 dp[i] 的最大值,而不是最后一个状态。下面是 Java 方法片段,需放入类中使用:
java
static int lis(int[] values) {
int[] dp = new int[values.length];
java.util.Arrays.fill(dp, 1);
int best = 0;
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < i; j++) {
if (values[j] < values[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]);
}
return best;
}设数组长度为 n。每个位置最多检查此前的所有元素,总比较次数为 n(n-1)/2,因此时间为 O(n²),额外空间为 O(n)。空数组没有状态需要更新,代码返回初始的 best = 0。
2. LIS 的二分优化
基础算法为每个结尾保存长度。若只求最长长度,可以换一个角度:为每种长度保存最有利于继续扩展的结尾。维护 tails[k],表示已处理元素中,长度为 k+1 的严格递增子序列能取得的最小结尾值;size 表示当前最长长度,只有 tails[0..size) 有效。
同样长度的候选中,结尾越小,后续越容易接上更大的值。因此不必保留该长度下的所有结尾。有效的 tails 严格递增,可以用 Lower Bound(下界搜索,即查找第一个大于等于当前值 v 的位置)更新:
- 找到位置
k < size:用v替换tails[k],保留该长度下更小或相同的结尾,不增加长度; - 没有找到,即
k == size:v大于所有有效结尾,可以接到最长候选之后,令size增加 1。
每个元素只做一次二分搜索,时间降为 O(n log n)。第 4 节给出实现,第 4.2 节进一步解释它保持的性质。
tails 的各项可能来自不同候选,不一定能按原数组顺序连成一条 LIS。需要恢复实际序列时,还要保存每种长度的结尾下标,并在处理当前元素时记录其前驱下标,最后沿前驱链回溯。
3. LCS:最长公共子序列
LCS 是 Longest Common Subsequence 的缩写,要求选出的序列同时出现在两个输入中,并在各自输入中保持原有顺序,不要求连续。例如 "ABC" 与 "AC" 的 LCS 是 "AC"。
定义 dp[i][j] 为字符串 a 的前 i 个比较单位与字符串 b 的前 j 个比较单位的 LCS 长度。这样的开头片段称为前缀。本文 Java 代码的比较单位是 char,因此两个前缀的末尾下标分别是 i-1、j-1。
转移只需考虑这两个末尾:
- 相等时,可以将共同末尾接到两个更短前缀的 LCS 后面,长度增加 1;反过来,删去这个末尾后,剩余部分不能超过更短前缀的最优长度,所以这个候选就是最优值。
- 不等时,公共子序列不可能同时使用这两个末尾,至少要舍弃一个。因此分别考虑去掉
a的末尾和去掉b的末尾,取较大的答案。
状态公式如下,仅在 i > 0 且 j > 0 时使用:
text
相等:dp[i][j] = dp[i-1][j-1] + 1
不等:dp[i][j] = max(dp[i-1][j], dp[i][j-1])任一前缀为空时,公共子序列长度为 0,所以第 0 行和第 0 列初始化为 0。按行从左到右计算时,上方、左方和左上方的状态都已就绪。下面的方法片段只返回长度:
java
static int lcs(String a, String b) {
int[][] dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[a.length()][b.length()];
}4. 完整可运行示例:LIS 两种解法与 LCS 恢复
以下类只依赖 Java 标准库,可保存为 SequenceDpDemo.java,由本地 JDK 编译运行;输入数组和字符串须非 null;空数组、空字符串是合法输入。
前两种方法返回 LIS 长度。这里的 lcs 与第 3 节片段不同,返回一条实际公共子序列:先填表,再从右下角回溯。末尾相等就收集该 char 并向左上方移动;不等就沿长度不减少的方向移动。因为收集顺序从后向前,最后需要反转。多个最优解存在时,代码在平局时优先向上移动,只恢复其中一条。
java
import java.util.*;
/**
* 可运行示例:序列动态规划:最长递增子序列与最长公共子序列。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class SequenceDpDemo {
static int lisQuadratic(int[] a) {
// dp[i] 表示“必须以 a[i] 结尾”的严格递增子序列最大长度。
int[] dp = new int[a.length];
// 每个元素单独都能构成长度为 1 的子序列。
Arrays.fill(dp, 1);
int best = 0;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < i; j++) {
// 只有前一个值更小,a[i] 才能接在该子序列后面。
if (a[j] < a[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 全局 LIS 不一定以最后一个元素结尾,因此逐个维护最大值。
best = Math.max(best, dp[i]);
}
return best;
}
static int lisBinary(int[] a) {
// tails[k] 是长度 k+1 的递增子序列能取得的最小结尾值。
int[] tails = new int[a.length];
int size = 0;
for (int v : a) {
int l = 0;
int r = size;
// lower_bound:寻找第一个大于等于 v 的结尾位置。
while (l < r) {
int m = (l + r) >>> 1;
if (tails[m] < v) {
l = m + 1;
} else {
r = m;
}
}
// 用更小的结尾替换同长度候选,为后续扩展留下空间。
tails[l] = v;
// v 比所有结尾都大时,成功把最长长度扩展 1。
if (l == size) size++;
}
return size;
}
static String lcs(String a, String b) {
// 多出的第 0 行和第 0 列代表空前缀,天然初始化为 0。
int[][] dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
// 末尾字符相同,把它接到两个更短前缀的 LCS 后面。
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 末尾字符不同,至少舍弃其中一个末尾字符。
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
StringBuilder out = new StringBuilder();
int i = a.length();
int j = b.length();
while (i > 0 && j > 0) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
// 相同字符一定可以属于当前最优解,逆序收集后同时左上移动。
out.append(a.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
// 沿不降低最优长度的方向回退;相等时任取一个即可。
i--;
} else {
j--;
}
}
return out.reverse().toString();
}
// 运行入口:演示两种 LIS 长度计算和一条 LCS 的恢复。
public static void main(String[] args) {
int[] a = { 10, 9, 2, 5, 3, 7, 101, 18 };
System.out.println(lisQuadratic(a));
System.out.println(lisBinary(a));
System.out.println(lcs("ABCBDAB", "BDCABA"));
}
}对入口中的数组,两种 LIS 方法的预期长度都是 4;两份字符串的 LCS 长度预期也是 4。这些是按代码推导的预期结果,不是实测输出。入口未覆盖空输入等边界,测试建议见第 7 节。字符串恢复仍按 char 处理,不能将其直接当作按码点或用户感知字符恢复的实现。
4.1 手工推演 LIS
对 [3, 5, 2, 4],二次 DP 得到:
| i | 当前值 | 可接续的前驱 | dp[i] |
|---|---|---|---|
| 0 | 3 | 无 | 1 |
| 1 | 5 | 3 | 2 |
| 2 | 2 | 无 | 1 |
| 3 | 4 | 3、2 | 2 |
答案是 2,但合法 LIS 不唯一,例如 [3,4] 与 [2,4]。DP 求的是长度;要稳定恢复某一条序列,必须额外记录前驱下标及最终结束位置。
4.2 为什么最小结尾能保留答案
不变量是算法在指定阶段始终保持的性质。这里每处理完一个元素,tails[k] 都表示该长度的最小结尾,且有效部分严格递增。
为什么较小结尾足够?两个同长度候选都由已处理元素组成,未来元素在它们之后;任何能接到较大结尾之后的值,也能接到较小结尾之后。因此替换结尾不会丢失未来取得更长序列的机会。
严格递增的性质也说明了为什么能二分:取一条结尾为 tails[k+1]、长度为 k+2 的候选,去掉最后一个元素后,其结尾严格小于 tails[k+1]。长度为 k+1 的最小结尾只会更小,所以 tails[k] < tails[k+1]。下界搜索找到的 k 满足左侧结尾都小于 v,而当前位置及右侧不小于 v,替换后仍保持严格递增。
以 [3, 5, 2, 4] 为例,有效 tails 依次为 [3]、[3, 5]、[2, 5]、[2, 4]。其中 [2, 5] 不是原数组的子序列,因为 2 出现在 5 后面;但它正确记录了长度 1 和长度 2 的最小结尾。这正是长度候选表与实际答案序列的区别。
4.3 复杂度与选择
- 二次 LIS:时间
O(n²)、空间O(n),状态直观且容易恢复方案。 - 二分 LIS:时间
O(n log n)、空间O(n),只求长度时优先;恢复方案需增加下标数组。 - LCS:设两份输入长度为
m、n,非空输入通常记时间与空间均为O(mn)。本例分配(m+1)(n+1)个状态,计入空输入时,时间和空间上界写作O((m+1)(n+1))更准确;恢复还需至多O(m+n)次回溯。 - LCS 只求长度时,当前行只依赖上一行和当前行左侧,可用滚动数组压缩到
O(min(m,n))空间;压缩后没有完整回溯路径,恢复序列需保留完整表或采用分治等方法,见第 6 节。
5. 子串、子数组与子序列
定义的差别会改变状态转移。第 1 节的 LIS 允许从任意合法的 j < i 接续,第 3 节的 LCS 允许舍弃不相等的末尾;这两种转移都在允许跳过元素。
如果业务要找的是连续公共片段,就不能用 LCS 的“不等时取上方或左方最大值”来延长当前片段。以“在这两个位置结尾的公共子串长度”为状态时,末尾不相等意味着连续匹配中断,该状态应为 0;末尾相等才从左上方加 1,并在所有结尾中取最大值。
因此建模前先问清:允许删除中间元素,还是必须保留完整的连续片段?文本包含查询中的连续单模式匹配,可继续阅读文末链接的 KMP 文章。
6. 大序列与文本差异的工程选型
两个长度均为十万的序列会产生约 10¹⁰ 个 LCS 状态。即使每格只占 4 字节,也需要约 400 亿字节,仅状态值就远超常规内存预算,还未计入 Java 二维数组的结构开销。这是按状态数计算的内存估算,不是测量记录;仅压缩空间也不会消除 O(mn) 的转移次数。实际文本差异比较还要按输出目标选择:
- 只求长度时使用滚动数组;
- 需要恢复序列且内存受限时评估 Hirschberg 分治:通过划分子问题减少恢复过程的内存需求;
- 需要编辑脚本时评估 Myers diff;diff 指差异比较,编辑脚本指把一份序列变成另一份所需的一组操作,具体允许哪些操作要由模型确定;
- 行级、词级还是字符级比较会改变输入规模与业务结果;
- 超大输入可先分块或利用业务锚点缩小比较范围,但独立比较各块可能漏掉跨块匹配;需要全局最优结果时,必须另外证明分块不会排除最优解。
这些算法目标并不完全相同,不能仅凭“都能做 diff”互换。
7. 验证与排障
以下是建议的检查方式:
- 二次 LIS 与二分 LIS 在随机小数组上做差分测试,即对同一输入比较两种实现的结果;必要时用小数组枚举全部子序列作独立基线,避免两种实现共享同一错误;
- 覆盖空序列、全相等、严格递减、重复值和多个最优解。严格递增在基础算法中使用
<,二分算法使用 Lower Bound;非递减允许相等值接续,需使用<=和 Upper Bound(第一个严格大于当前值的位置); - LCS 恢复结果必须同时是两个输入的合法子序列;
- 多个最优解时验证长度和合法性,不固定要求同一字符串;
- 包含 Unicode 代理对(共同表示一个码点的两个 UTF-16 编码单元)的字符串,应检查是否选取或恢复了孤立编码单元,并确认结果符合业务定义的字符语义;
- 内存异常时先估算
m × n状态数,再考虑空间压缩或算法切换。
8. 容易踩的坑
- 严格递增使用
<,非递减使用<=,不能混淆。 tails被误当成最终答案序列。- LCS 下标偏移错误。
- 忘记空输入的边界:LIS 应返回 0,LCS 长度为 0、恢复结果为空字符串;这与
null输入不同。 - 把按
char计算的长度、下标或恢复结果当成按码点或用户感知字符得到的结果。
9. 总结
序列 DP 的关键是明确“状态以哪里结尾”以及元素是否必须连续。
- LIS 的基础状态是“以 i 结尾”,二分优化维护最小结尾候选。
- LCS 根据末尾字符是否相等决定转移方向。
- 只求长度与恢复实际序列需要不同的信息量。
状态集合较小时可继续阅读位运算与状态压缩。单模式连续匹配见字符串匹配与 KMP。