前缀信息优化 DP
当转移只依赖前缀且 i、j 的贡献可分离时,维护 y(j,f(j)) 的前缀聚合,把 O(n^2) 的转移降为 O(n)。时间 O(n),空间 O(n) · 标签 动态规划 / 前缀和 / 前缀最值 / DP 优化
问题形式
考虑 1D/1D 动态规划中,当 时,方程退化为
其中 是基础状态,窗口取为前缀。 与 的贡献已经拆开, 只依赖 的前缀。若把 换成求和,对应的聚合量就是前缀和;若换成 ,就是前缀最大值。下面的写法以最小值为例,其他聚合运算同理。
核心思想
令 表示当前前缀中 的聚合值。初始时 取该运算的单位元:最小值用 ,求和用 ,最大值用 。
从基础状态 开始,先把 并入 ;之后每算出一个 ,再把 并入。计算 前, 已经汇总了所有 的项,于是
得到 后,再把 并入 ,供后面的状态使用:
每个 只进入前缀一次,因此总时间为 。若只需要转移,额外空间为 ;若后续还要访问 ,则保留整个数组。
正确性
归纳不变式为:计算 时, 恰好等于 。
处理完基础状态 后,,不变式对 成立。由 得到正确的 ;随后把 并入, 就变成下一个状态所需的前缀聚合。归纳成立。
易错点
- 依赖 时,必须先用 的值更新聚合量,不能提前把 并入。
- 不同聚合运算的单位元不同;最小值用 ,最大值用 ,求和用 。
- 若 不是固定的 或 ,前缀聚合不再等于窗口聚合,不能直接套用。
- 前缀为空时,最小值是 ;如果 依赖这个值,需要单独处理无解或基础状态。