[Note] 线性DP

[L4] 线性状态动态规划

线性状态 DP 指一类具有自然处理顺序的动态规划。状态通常描述某个有序过程已经处理到哪里，并从更早的状态向后递推。

“线性”修饰的是状态 DAG 的展开方式，而不是状态数组的维数，也不代表时间复杂度一定是 $O(n)$。

题目中的处理顺序可能来自：序列或时间轴上的先后关系，两个序列各自处理到的位置，网格中的坐标或步数，以及区间长度、拓扑序等人为构造的递推顺序。

常见状态形式为：

f[i]       ：处理到第 i 个位置，或以前 i 个对象为范围
f[i][j]    ：同时记录两条处理轴的进度
f[i][j][k] ：在基本进度之外，再附加会影响后续的信息

状态维数只是需要保存的信息数量。真正需要确定的是：哪些状态已经可以独立表示一个子问题，以及它们应当按照什么顺序计算。

一、单序列问题

单序列问题通常沿下标从左向右递推，但状态可以有两种不同含义：

以前 i 个元素为范围
以第 i 个元素作为结尾

两种定义对应的转移来源并不相同，不能只因为状态都写成 $f[i]$ 就混为一类。

1. 以当前位置结尾

LIS 模型

最长上升子序列要求在保持原顺序的前提下，寻找一条尽可能长的单调子序列。

朴素状态定义为：$f[i]$ 表示以 $a_i$ 结尾的最长上升子序列长度。

转移为：$\displaystyle f[i] = 1 + \max_{\substack{j<i\\a_j<a_i}} f[j]$。

这里的前驱不是唯一的上一个位置，而是此前所有能够连接到 $a_i$ 的位置。

基础原理、最小结尾优化与模板参见 LIS模型；其他变体问题参见 LIS题型整理。

限制前驱范围

问题

P1725 琪露诺
每个位置只能从此前一段固定长度的区间转移，求能够取得的最大权值。

这类问题仍然可以定义：$f[i]$ 表示到达位置 $i$ 时的最优答案。

区别在于，合法前驱被限制在某个滑动区间内，转移通常形如：

$$f[i] = a_i + \max_{j\in[i-R,i-L]}f[j]$$

朴素枚举前驱为 $O(nR)$，而转移真正需要的是一个滑动窗口内的最大值，因此可以使用 单调队列优化 DP。

它与 LIS 同属“以当前位置结尾”的线性 DP，但连接条件和优化方法不同。

2. 在基本位置上附加信息

有些问题除了当前位置，还需要保存会影响后续转移的额外性质。

例如：

• P4933 大师：状态需要记录等差子序列的公差；
• P1874 快速求和：状态需要记录当前处理到的位置以及已经形成的目标信息。

这类状态通常形如：$f[i][s]$ 其中 $i$ 表示处理进度，$s$ 表示此前决策留下的必要信息。

增加状态时需要判断：去掉这项信息后，两个历史不同的方案在后续是否仍然完全等价？

若不等价，就必须保留；若等价，就不应机械地增加维度。

二、双序列问题

当一个决策需要同时保持两个序列中的相对顺序时，只记录其中一条序列的进度通常不够。

常见状态为：$f[i][j]$ 表示处理完序列 $A$ 的前 $i$ 个元素与序列 $B$ 的前 $j$ 个元素时的答案。

考虑对齐方案的最后一步，通常有三种基本转移：

(i-1,j-1) → (i,j)：同时处理 A_i 与 B_j
(i-1,j)   → (i,j)：只处理 A_i
(i,j-1)   → (i,j)：只处理 B_j

LCS、编辑距离、带权字符串距离、相似基因以及在基础状态上进行方案计数、连续段扩展等问题，统一参见：浅谈序列对齐DP

三、网格状态

二维状态不一定来自两个序列，也可能来自网格中的两个坐标。

例如定义：$f[i][j]$ 表示走到网格位置 $(i,j)$ 时的最优答案。

若移动只能使坐标单调增加，所有状态会形成一个有向无环图，可以按照行、列或反对角线顺序递推。

反对角线性质：从左上向右下单调移动的路径，会依次经过每一条反对角线。
因此，当多个人同时移动且步数相同时，可以用反对角线编号统一它们的处理进度。

代表题：

• P1006 传纸条：两个人同时在网格上移动，需要记录同一时刻两人的位置；
• P1544 三倍经验：在基本状态之外增加层次或阶段信息。

网格 DP 是否属于“线性状态”，不取决于数组是不是二维，而取决于状态能否沿某种单向顺序递推。

四、多维状态与状态扩展

高维状态通常来自两种情况。

1. 存在多条独立的处理轴

例如同时记录：

两个位置
两个对象的进度
多个参与者的状态

2. 在基本进度上附加限制

例如记录：

已经使用的次数
当前所属阶段
上一种操作
剩余资源
匹配模式

状态可以写成：$f[i][j][k]$，但 $k$ 不应只是照抄题面中的变量，而应表示一项确实会影响后续决策的信息。

常见检查方式是：若两个方案的基本位置相同，但这项信息不同，它们后续允许的选择或贡献是否不同？若不同，则需要区分状态。

相关实战：

• ABC442F Diagonal Separation 2：后缀最值优化；
• CF2194E The Turtle Strikes Back：前后缀最值优化；
• P1052 过河：压缩路径长度，减少无意义状态；
• CF2193F Pizza Delivery：利用单调性，将二维移动关系简化为一维转移。

五、统一认识

线性状态 DP 也是一种组织子问题的方式：

找到自然的处理顺序
→ 确定状态描述前缀还是结尾
→ 枚举当前状态的合法前驱
→ 保存所有会影响后续的信息
→ 从转移结构中寻找优化

面对新的线性 DP，可以依次判断：

1. 题目中的有序事件或处理轴是什么？
2. 状态应表示“前若干对象”，还是“以当前位置结尾”？
3. 当前状态可能从哪些更早状态转移？
4. 哪些历史信息会影响后续，必须加入状态？
5. 朴素转移实际需要维护的是区间最值、前缀和，还是其他可优化操作？

几类常见结构可以整理为：

状态形式	常见含义	代表方向
$f[i]$	前 $i$ 个对象，或以 $i$ 结尾	LIS、划分、路径
$f[i][j]$	两个处理进度或网格坐标	序列对齐、网格 DP
$f[i][s]$	位置与附加状态	公差、资源、模式
$f[i][j][k]$	多条处理轴或额外限制	双人移动、分层状态

状态 DAG 是否能够按照某种明确的处理顺序，从已经完成的子问题递推到尚未完成的子问题。不能只从状态的维度来判断 DP 的类别。