前缀信息优化 DP

当转移只依赖前缀且 i、j 的贡献可分离时,维护 y(j,f(j)) 的前缀聚合,把 O(n^2) 的转移降为 O(n)。

时间 O(n),空间 O(n) · 标签 动态规划 / 前缀和 / 前缀最值 / DP 优化

问题形式

考虑 1D/1D 动态规划中,当 𝑄𝑖,𝑗(𝑓(𝑗))=𝑥(𝑖)+𝑦(𝑗,𝑓(𝑗)) 时,方程退化为

𝑓(𝑖)=𝑥(𝑖)+min0≤𝑗<𝑖𝑦(𝑗,𝑓(𝑗)),

其中 𝑓(0) 是基础状态,窗口取为前缀。𝑖 与 𝑗 的贡献已经拆开,𝑓(𝑖) 只依赖 𝑗<𝑖 的前缀。若把 min 换成求和,对应的聚合量就是前缀和;若换成 max,就是前缀最大值。下面的写法以最小值为例,其他聚合运算同理。

核心思想

令 𝑀 表示当前前缀中 𝑦(𝑗,𝑓(𝑗)) 的聚合值。初始时 𝑀 取该运算的单位元:最小值用 +∞,求和用 0,最大值用 −∞。

从基础状态 𝑓(0) 开始,先把 𝑦(0,𝑓(0)) 并入 𝑀;之后每算出一个 𝑓(𝑖),再把 𝑦(𝑖,𝑓(𝑖)) 并入。计算 𝑓(𝑖) 前,𝑀 已经汇总了所有 0≤𝑗<𝑖 的项,于是

𝑓(𝑖)=𝑥(𝑖)+𝑀.

得到 𝑓(𝑖) 后,再把 𝑦(𝑖,𝑓(𝑖)) 并入 𝑀,供后面的状态使用:

𝑀←min(𝑀,𝑦(𝑖,𝑓(𝑖))).

每个 𝑗 只进入前缀一次,因此总时间为 𝑂(𝑛)。若只需要转移,额外空间为 𝑂(1);若后续还要访问 𝑓(𝑗),则保留整个数组。

正确性

归纳不变式为:计算 𝑓(𝑖) 时,𝑀 恰好等于 min0≤𝑗<𝑖𝑦(𝑗,𝑓(𝑗))。

处理完基础状态 𝑓(0) 后,𝑀=𝑦(0,𝑓(0)),不变式对 𝑖=1 成立。由 𝑓(𝑖)=𝑥(𝑖)+𝑀 得到正确的 𝑓(𝑖);随后把 𝑦(𝑖,𝑓(𝑖)) 并入,𝑀 就变成下一个状态所需的前缀聚合。归纳成立。

易错点

  • 𝑦(𝑗,𝑓(𝑗)) 依赖 𝑓(𝑗) 时,必须先用 𝑓(𝑗) 的值更新聚合量,不能提前把 𝑗 并入。
  • 不同聚合运算的单位元不同;最小值用 +∞,最大值用 −∞,求和用 0。
  • 若 𝐿(𝑖) 不是固定的 0 或 1,前缀聚合不再等于窗口聚合,不能直接套用。
  • 前缀为空时,最小值是 +∞;如果 𝑓(𝑖) 依赖这个值,需要单独处理无解或基础状态。
源码位置