算法刷题系列（四十九）：序列 DP——描述序列之间的选择关系

算法刷题系列（四十九）：序列 DP——描述序列之间的选择关系

序列动态规划关注的是：扫描序列时，当前元素能否接在之前某个选择之后。最长递增子序列（LIS）是一个典型例子。子序列可以跳过元素，但保留相对次序，因此问题的关键不是相邻位置，而是“最后一个被选择的元素”与此前选择的关系。

一、状态：以谁结尾

给定整数序列 a，定义：

dp[i] = 以 a[i] 作为最后一个元素的严格递增子序列的最大长度

以 a[i] 单独开始总是可行，所以初值 dp[i] = 1。若 j < i 且 a[j] < a[i]，可以把 a[i] 接在以 a[j] 结尾的序列后面：

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

最终答案是所有 dp[i] 的最大值。这里必须把“以 i 结尾”写进状态定义；若状态只说“前 i 个位置的答案”，转移含义容易混淆。

二、例子：从局部连接到全局答案

对 a = [3, 1, 2, 5, 4]：

i	a[i]	可接上的较小前项	dp[i]
0	3	无	1
1	1	无	1
2	2	1	2
3	5	3、1、2	3
4	4	3、1、2	3

一种最长递增子序列是 [1, 2, 5]，长度为 3。注意 [1, 2, 4] 也是长度 3；只求长度时不需要保存具体路径。

三、正确性直觉

考虑任意以 a[i] 结尾的递增子序列。若它只有一个元素，长度是初值 1。若长度大于 1，倒数第二个元素必定是某个 a[j]，且 j < i、a[j] < a[i]；去掉最后的 a[i] 后，得到以 a[j] 结尾的递增子序列。因此检查所有满足条件的 j 并取 dp[j] + 1，覆盖了所有可能的最后一步。反过来，每个满足条件的前序子序列都能合法追加 a[i]，所以该最大值既不会漏解也不会包含非法解。

四、Java 实现：平方时间

import java.util.Arrays;

public class SequenceDp {
    public static int lisLength(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("values must not be null");
        }
        int n = values.length;
        if (n == 0) {
            return 0;
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int answer = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (values[j] < values[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        if (lisLength(new int[]{3, 1, 2, 5, 4}) != 3
                || lisLength(new int[]{2, 2, 2}) != 1
                || lisLength(new int[]{}) != 0) {
            throw new AssertionError("LIS test failed");
        }
    }
}

五、Python 实现

def lis_length(values):
    if values is None:
        raise ValueError("values must not be None")
    if not values:
        return 0

    dp = [1] * len(values)
    answer = 1
    for i in range(len(values)):
        for j in range(i):
            if values[j] < values[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        answer = max(answer, dp[i])
    return answer

assert lis_length([3, 1, 2, 5, 4]) == 3
assert lis_length([2, 2, 2]) == 1
assert lis_length([]) == 0

六、复杂度与边界

两层循环枚举所有前后位置对，时间为 O(n²)；dp 使用 O(n) 空间。空序列的答案为 0，单元素序列为 1。严格递增使用 <；若题意改为非递减，条件应改为 <=。重复值因此是很有用的边界测试。

七、常见误区与扩展

1. 把子序列当成子数组：子序列允许跳过中间元素，索引只需递增。
2. 遗漏单元素起点：每个元素自身都是长度为 1 的递增子序列。
3. 用 <= 解严格递增：相等元素不能接续。
4. 把 dp[n - 1] 当答案：最优序列未必以最后一个数组元素结尾，应取全局最大值。
5. 混淆长度与方案数：本状态只记录最大长度；若要求计数，需要额外维护每个状态达到最大长度的方案数量。

当 n 很大时，可以用“最小结尾值”数组配合二分查找将 LIS 长度计算降到 O(n log n)。那个数组不是每个位置的 dp，而是按长度记录可达到的最小尾值；它适合求长度，路径重建则要额外保存前驱。

小结

序列 DP 的核心是选好状态视角。本例以某个位置结尾，枚举此前能够连接的状态，再把局部最优汇总成全局答案。先明确“最后一步是什么”，通常就能写出可靠的转移。