数据结构与算法 / 系统课时

序列动态规划

序列动态规划

序列动态规划的关键不是背公式,而是判断状态表示“以当前位置结尾”还是“两个前缀的最优解”。本课用最长递增子序列和最长公共子序列建立统一分析方法,并给出可运行实现。

学习目标

  • 根据位置或前缀范围定义动态规划状态
  • 推导 LIS 与 LCS 的转移、初始化和答案位置
  • 分析一维、二维状态的时间与空间复杂度

两类序列状态

最长递增子序列(LIS)只处理一个序列。定义 dp[i] 为“以 numbers[i] 结尾的最长严格递增子序列长度”。每个元素至少可以单独成序列,因此初始值都是 1。

当 j < i 且 numbers[j] < numbers[i] 时,位置 i 可以接在位置 j 后面:

text
dp[i] = max(dp[i], dp[j] + 1)

LIS 不一定以最后一个元素结尾,所以答案是所有 dp[i] 的最大值,而不是固定取 dp[n - 1]。

最长公共子序列(LCS)同时处理两个序列。定义 dp[i][j] 为第一个字符串前 i 个字符与第二个字符串前 j 个字符的最长公共子序列长度。若末尾字符相等,就从左上角扩展;否则在“舍弃第一个末尾字符”和“舍弃第二个末尾字符”之间取较大值。

text
字符相等:dp[i][j] = dp[i - 1][j - 1] + 1
字符不同:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

LIS 与 LCS 状态依赖

初始化与遍历顺序

LIS 的状态只依赖更小下标,因此外层 i 从左向右,内层枚举所有 j < i。LCS 的第 0 行和第 0 列表示至少一个前缀为空,默认值为 0;其余单元格按从左上到右下的顺序填写,确保左、上、左上状态已经计算。

子序列允许跳过元素,但不能改变相对顺序。它与要求连续的子串或连续子数组不同,这也是 LIS 必须枚举所有合法前驱、LCS 可以舍弃任一末尾字符的原因。

完整示例

下面的 Java 17 程序同时计算 LIS 和 LCS。示例只返回长度,不恢复具体序列。

java
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()];
    }
}

预期输出:

text
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;字符不等时不能直接取左上角状态。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

序列动态规划

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通