【动态规划】线性 DP 学习笔记

最长上升子序列（LIS）

问题描述

给定一个长度为 $n$ 的序列 $a[1 \dots n]$，求其中最长的严格上升子序列的长度。

一个子序列是从原序列中删除若干元素（可以不连续）后剩余的元素保持原有顺序组成的序列。称该子序列是"上升"的，当且仅当对于序列中任意两个位置 $i < j$，都有 $a[i] < a[j]$。

示例

$$
a = [1, 5, 2, 3, 4]
$$

其中最长上升子序列为 $[1, 2, 3, 4]$，长度为 $4$。

朴素 DP（时间复杂度 $O(n^2)$）

推导过程

下面以 LIS 为例，对照动态规划的一般步骤：

找子问题，把问题划分为各个阶段。
子问题：以 $a[i]$ 结尾的最长上升子序列。将原问题按元素位置划分为 $n$ 个阶段。
根据阶段划分确定动态规划的状态。
定义 $f[i]$ 表示以 $a[i]$ 结尾的最长上升子序列的长度。
找到初始状态。
对于任意位置 $i$，仅包含 $a[i]$ 的子序列长度为 $1$，即初始值 $f[i] = 1$。
通过阶段之间的决策找出状态转移方程。
若已知以 $a[j]$ 结尾的 LIS 长度为 $f[j]$ 且 $a[j] < a[i]$，则将 $a[i]$ 接在后面，得到长度为 $f[j] + 1$ 的上升子序列。对所有满足条件的 $j$ 取最大值：

$$
f[i] = \max_{j < i,, a[j] < a[i]} { f[j] } + 1
$$

通过状态转移方程，通过递推或者记忆化搜索写出代码、优化，求出问题的解。
全局最优解为 $\max f[i]$。按 $i = 1$ 到 $n$ 的顺序递推，时间复杂度 $O(n^2)$。

int lis(const vector<int>& a) {
    int n = a.size();
    vector<int> f(n, 1);          // 初始状态：每个元素自身构成一个 LIS
    int ans = 1;
    for (int i = 0; i < n; i++) { // 按顺序递推
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1); // 状态转移
            }
        }
        ans = max(ans, f[i]);       // 记录全局最优解
    }
    return ans;
}

LIS 问题满足动态规划的两个关键性质：

最优子结构

全局最优解可以通过子问题的最优解递推得到。各个以 $a[j]$ 结尾的最优子序列组合起来，便得到了原问题的最优解。

无后效性

一旦 $f[i]$ 被确定，其值便固定下来，不会再被后续的计算改变。在计算 $f[k]$（$k > i$）时，只需用到 $f[i]$ 的最终值，而不关心 $f[i]$ 是通过怎样的顺序、怎样的路径计算出来的。即"未来和过去无关"——后续状态只依赖于之前状态的值，与这些状态的历史无关。

例题：[NOIP 2004 提高组] 合唱队形

给定 $n$ 位同学的身高序列 $t_1, t_2, \dots, t_n$，从中选取一个子序列（保持原顺序）形成"合唱队形"：存在某个峰值位置 $i$，使得身高严格递增至 $t_i$，再严格递减至末尾，即：

$$
t_{j_1} < t_{j_2} < \cdots < t_i > t_{k_1} > t_{k_2} > \cdots > t_{k_m}
$$

求最少需要出列的人数。数据范围：$2 \le n \le 100$，$130 \le t_i \le 230$。

问题等价于 $n$ 减去最长「先增后减」子序列的长度。即若以每个位置 $i$ 为峰值，定义 $L_i$ 为以 $i$ 结尾的最长上升子序列（LIS）长度、$R_i$ 为以 $i$ 开头的最长下降子序列（LDS）长度，则答案为：

$$
n - \max_{1 \le i \le n} \left( L_i + R_i - 1 \right)
$$

求解 LDS 的方法和 LIS 类似，相信理解了前文推导过程读者可以自行思考出解法。同理还有各种常见变形，比如不下降/不上升等等。

二分+贪心（Patience Sorting，$O(n \log n)$）

$\text{tails}$ 数组的单调性是整个算法的核心。下面从纸牌游戏类比出发，逐步介绍其定义，并推导其单调性与更新逻辑。

直观理解

想象你在玩一个接龙游戏纸牌游戏（Patience Solitaire）：

桌面上有若干牌堆。
规则：对于新来的一张牌 $x$，你从左到右找到第一张牌顶 $\ge x$ 的牌堆，把 $x$ 放在该牌堆的最上面（覆盖旧的牌顶）。
如果所有牌堆的牌顶都 $< x$，那么就在最右边新建一个牌堆，$x$ 就是新牌堆的牌顶。

在代码中，$\text{tails}$ 数组按从左到右的顺序，存储的就是每个牌堆当前的牌顶值。

接龙游戏举例

核心性质

$\text{tails}$ 数组始终保持严格递增，即：

$$
\text{tails}[0] < \text{tails}[1] < \text{tails}[2] < \dots
$$

这是 Patience Sorting 最重要的不变式（Invariant），下面用数学归纳法严格证明。

初始状态：空数组或单元素数组，显然严格递增。

归纳假设：在处理当前元素 $x$ 之前，$\text{tails}$ 数组严格递增。

执行操作：用 lower_bound 找到第一个满足 $\text{tails}[pos] \ge x$ 的位置 $pos$，将 $\text{tails}[pos]$ 替换为 $x$（若 $pos$ 越界则追加）。需证明替换后严格递增性不变：

左侧（$pos > 0$）：lower_bound 保证了 $\text{tails}[pos-1] < x$（否则 $pos-1$ 才是第一个 $\ge x$ 的位置）。替换后 $\text{tails}[pos-1] < \text{tails}'[pos]$ 成立。
右侧（$pos < \text{len}-1$）：由归纳假设，替换前有 $\text{tails}[pos] < \text{tails}[pos+1]$。又因 $pos$ 是第一个 $\ge x$ 的位置，故 $x \le tails[pos]$，从而：

$$
x \le \text{tails}[pos] < \text{tails}[pos+1]
$$

即 $x < \text{tails}[pos+1]$，替换后 $\text{tails}‘[pos] < \text{tails}’[pos+1]$ 成立。

其他位置：未涉及 $pos$ 的相邻关系保持不变。

综上，无论追加还是原地替换，$\text{tails}$ 的严格递增性始终维持。

数学定义

$\text{tails}[i]$ 实际上代表：在所有长度为 $i+1$ 的严格递增子序列中，最小的末尾元素值是多少？

因为 $\text{tails}$ 严格递增，所以这个定义是自洽的：

长度为 1 的最小末尾 = $\text{tails}[0]$（全局最小值）。
长度为 2 的最小末尾 = $\text{tails}[1]$（比如 $[1, 3]$ 的末尾 3，一定大于长度为 1 的某个末尾）。
因为末尾值越小，越容易接上更大的数，所以算法总是贪心地用更小的值去替换掉相同长度下的旧末尾。

这就是耐心排序法与 LIS 问题的关联。

单调性与二分查找

由于 $\text{tails}$ 严格递增，当新元素 $x$ 到来时：

我们要先找到位置 $pos$，是第一个满足 $\text{tails}[pos] \ge x$ 的下标值（使用 lower_bound）。
位置 $pos$ 的意义：
- 如果 pos == tails.size()（即 $x$ 比所有牌顶都大），说明 $x$ 可以接在当前最长的子序列后面，形成更长的 LIS，所以新建堆（push_back）。
- 如果 pos < tails.size()，说明 $x$ 可以接在长度为 $pos$ 的子序列后面（因为 $x$ 小于等于原来的 $\text{tails}[pos]$，但大于 $\text{tails}[pos-1]$）。我们将 $\text{tails}[pos]$ 替换为 $x$，使得长度为 $pos+1$ 的子序列末尾变得更小了，这对未来更有利。

画个图理解更新过程：

单调性与二分查找

假设当前 $\text{tails} = [2, 6, 8]$，新来 $x = 5$。

lower_bound 找到第一个 $\ge 5$ 的位置是 $index = 1$（值为 6）。
我们把 6 替换成 5，得到 $\text{tails} = [2, 5, 8]$。
含义：原本长度为 2 的最优结尾是 6（例如 $[1, 6]$），现在变成了 5（例如 $[2, 5]$ 或 $[1, 5]$）。结尾变小了，未来如果来个 7，就能形成 $[2,5,7]$ 长度为 3；如果还是 6，就无法形成长度为 3 的新序列。

重要误区：$\text{tails}$ 并不是最终的 LIS 序列

这是一个极易踩的坑：$\text{tails}$ 数组里存的元素并不一定构成一个真实存在的递增子序列。

例如：对于序列 $[3, 1, 2]$。

过程：
- 3 来：$\text{tails} = [3]$
- 1 来：替换掉 3，$\text{tails} = [1]$（此时末尾变成了 1，但 LIS 不是 $[1]$，而是未来的 $[1, 2]$）
- 2 来：追加，$\text{tails} = [1, 2]$

$\text{tails} = [1, 2]$ 恰好是真实序列，但再看一个反例：序列 $[2, 3, 1]$。

过程：
- 2 来：$[2]$
- 3 来：$[2, 3]$
- 1 来：替换掉 2，$[1, 3]$

此时 $\text{tails}$ 是 $[1, 3]$，但原序列中 并不存在 $[1, 3]$（因为 1 在 3 的后面，不能接上 3）。$[1, 3]$ 只是表示：

长度为 1 的最小末尾是 1。
长度为 2 的最小末尾是 3（来自真实的 $[2, 3]$）。

我们只关心这个数组的长度（即牌堆的数量），它恰好等于 LIS 的长度。

总结

单调递增 使得我们可以用 $O(\log N)$ 的二分查找快速定位更新位置。
每次更新都是用当前元素去尽可能降低某个牌堆的顶部值，为后面的元素创造更多”接上去”的机会。
这是一种在线算法，扫描一遍数据即可，空间仅需维护 $\text{tails}$ 数组。

如果读者此前接触过树状数组做法（基于值域 DP），那里维护的是”以某个值结尾的最佳长度”，是另一种完全不同的视角（动态规划）。而 Patience Sorting 是从”维护最优末尾集合”的角度出发的贪心，这也是它代码极其精妙的原因。

代码实现

int lis(const vector<int>& a) {
    vector<int> tails; // tails[k] 表示长度为 k+1 的 LIS 的最小末尾值
    for (int val : a) {
        auto it = lower_bound(tails.begin(), tails.end(), val);
        if (it == tails.end())
            tails.push_back(val);
        else
            *it = val;
    }
    return tails.size();
}

时间复杂度 $O(n \log n)$。

树状数组优化 DP（离散化后 $O(n \log n)$）

未完待续…