数据结构与算法 / 系统课时
序列动态规划
序列动态规划
序列动态规划的关键不是背公式,而是判断状态表示“以当前位置结尾”还是“两个前缀的最优解”。本课用最长递增子序列和最长公共子序列建立统一分析方法,并给出可运行实现。
学习目标
- 根据位置或前缀范围定义动态规划状态
- 推导 LIS 与 LCS 的转移、初始化和答案位置
- 分析一维、二维状态的时间与空间复杂度
两类序列状态
最长递增子序列(LIS)只处理一个序列。定义 dp[i] 为“以 numbers[i] 结尾的最长严格递增子序列长度”。每个元素至少可以单独成序列,因此初始值都是 1。
当 j < i 且 numbers[j] < numbers[i] 时,位置 i 可以接在位置 j 后面:
dp[i] = max(dp[i], dp[j] + 1)LIS 不一定以最后一个元素结尾,所以答案是所有 dp[i] 的最大值,而不是固定取 dp[n - 1]。
最长公共子序列(LCS)同时处理两个序列。定义 dp[i][j] 为第一个字符串前 i 个字符与第二个字符串前 j 个字符的最长公共子序列长度。若末尾字符相等,就从左上角扩展;否则在“舍弃第一个末尾字符”和“舍弃第二个末尾字符”之间取较大值。
字符相等:dp[i][j] = dp[i - 1][j - 1] + 1
字符不同:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
初始化与遍历顺序
LIS 的状态只依赖更小下标,因此外层 i 从左向右,内层枚举所有 j < i。LCS 的第 0 行和第 0 列表示至少一个前缀为空,默认值为 0;其余单元格按从左上到右下的顺序填写,确保左、上、左上状态已经计算。
子序列允许跳过元素,但不能改变相对顺序。它与要求连续的子串或连续子数组不同,这也是 LIS 必须枚举所有合法前驱、LCS 可以舍弃任一末尾字符的原因。
完整示例
下面的 Java 17 程序同时计算 LIS 和 LCS。示例只返回长度,不恢复具体序列。
import java.util.Arrays;
public class SequenceDynamicProgrammingDemo {
public static void main(String[] args) {
int[] numbers = {10, 9, 2, 5, 3, 7, 101, 18};
String first = "ABCBDAB";
String second = "BDCABA";
System.out.println("LIS 长度: " + lis(numbers));
System.out.println("LCS 长度: " + lcs(first, second));
}
private static int lis(int[] numbers) {
if (numbers.length == 0) {
return 0;
}
int[] dp = new int[numbers.length];
Arrays.fill(dp, 1);
int answer = 1;
// i 表示当前结尾位置,j 枚举所有可能前驱
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < i; j++) {
if (numbers[j] < numbers[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
answer = Math.max(answer, dp[i]);
}
return answer;
}
private static int lcs(String first, String second) {
int[][] dp = new int[first.length() + 1][second.length() + 1];
// 状态下标表示前缀长度,访问字符时需要减一
for (int i = 1; i <= first.length(); i++) {
for (int j = 1; j <= second.length(); j++) {
if (first.charAt(i - 1) == second.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[first.length()][second.length()];
}
}预期输出:
LIS 长度: 4
LCS 长度: 4复杂度与边界
基础 LIS 有 n 个状态,每个状态枚举前驱,时间复杂度为 O(n^2),空间复杂度为 O(n)。LCS 有 (m + 1) × (n + 1) 个状态,时间和空间复杂度均为 O(mn);只求长度时可把空间压缩到 O(min(m, n))。
严格递增使用 <,允许相等元素时改为 <=。空数组的 LIS 长度是 0,任一字符串为空时 LCS 长度也是 0。若需要恢复具体序列,必须额外记录转移来源,或保留完整状态表后反向追踪。
常见错误
把 LIS 返回值写成 dp[n - 1] 会漏掉提前结束的最优序列;只比较相邻元素得到的是最长连续递增片段。LCS 中,状态下标表示前缀长度,字符下标必须使用 i - 1 和 j - 1;字符不等时不能直接取左上角状态。