单调队列优化 DP

当可分离转移的决策窗口左右端点都单调时,用单调队列维护窗口内 y(j,f(j)) 的最小值,把每层转移降为均摊 O(1)。

时间 O(n),空间 O(n) · 标签 动态规划 / 单调队列 / 滑动窗口 / DP 优化

问题形式

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

𝑓(𝑖)=𝑥(𝑖)+min𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑦(𝑗,𝑓(𝑗)),

其中

𝐿(𝑖)≤𝐿(𝑖+1),𝑅(𝑖)≤𝑅(𝑖+1),

并且 𝐿(𝑖)≤𝑅(𝑖)<𝑖,窗口左右端点单调。

窗口的左右端点都只会向右移动:新的候选从右侧加入,旧的候选从左侧过期。此时可以用一个单调队列维护窗口内 𝑦(𝑗,𝑓(𝑗)) 的最小值。

单调队列

队列中只存下标 𝑗,并按 𝑗 递增排列。同时要求对应的 𝑦(𝑗,𝑓(𝑗)) 也递增;这样队首就是当前窗口的最小值。

计算 𝑓(𝑖) 时:

  • 把所有满足 𝑗≤𝑅(𝑖) 且尚未加入的 𝑗 依次加入队尾。
  • 若新加入的 𝑗 对应的值不大于队尾的值,就不断弹出队尾。新下标更大,过期更晚,值又不更差,被弹出的下标不可能再成为最优。
  • 弹出所有 𝑗<𝐿(𝑖) 的队首元素。
  • 取队首作为最优决策,计算 𝑓(𝑖)=𝑥(𝑖)+𝑦(𝑗,𝑓(𝑗))。

每个下标最多入队、出队一次,因此所有转移的总时间是 𝑂(𝑛)。

正确性

不变式为:队列中恰好保存当前窗口 [𝐿(𝑖),𝑅(𝑖)] 内所有未被支配的候选,且它们的值随下标递增。

左端点单调增加,所以被弹出的旧下标以后不会再进入窗口。右端点加入新下标时,若队尾的值不小于新值,队尾下标比新下标更早过期且值更差,未来不可能优于新下标,可以删除。剩下的队首就是窗口最小值。

初始窗口为空,按上述规则加入和删除后,𝑓(𝑖) 取到的正是区间最小值。

易错点

  • 必须同时要求 𝐿(𝑖) 和 𝑅(𝑖) 单调;只要求 𝑅(𝑖) 单调不足以支持从队首删除。
  • 队列中存下标而不是只存值,否则无法判断是否已经小于 𝐿(𝑖)。
  • 新候选要按 𝑗 递增加入;不能把尚未算出的 𝑓(𝑗) 提前放入队列。
  • 取最小值时,队尾值等于新值时也可以弹出队尾,保留下标更大的候选;取最大值时方向相反。
  • 若窗口为空,队首不存在,需要单独处理无解或基础状态。
源码位置