二分栈优化 DP

当 Q_(i,j) 可依赖 f(j)、最优决策满足决策单调性中的单交叉条件时,用二分栈在线维护决策区间,以 O(n log n) 求出全部 f(i)。

时间 O(n log n),空间 O(n) · 标签 动态规划 / 决策单调性 / 二分栈 / DP 优化

问题形式

考虑 1D/1D 动态规划中,当 𝑄𝑖,𝑗 可以依赖 𝑓(𝑗),且最优决策满足 决策单调性 中的单交叉条件时,方程

𝑓(𝑖)=min1≤𝑗<𝑖𝑄𝑖,𝑗(𝑓(𝑗))

可以按 𝑖 递增在线计算。下面按 𝐿(𝑖)=1、𝑅(𝑖)=𝑖−1 说明;若窗口另有约束,需要先检查新决策是否仍对一段后缀的未来状态可用。

核心思想

维护一个栈,栈中每个决策 𝑗 带一个起点 𝑠𝑗;决策 𝑗 在 [𝑠𝑗,𝑠𝑗+1−1] 上最优。

先计算基础状态 𝑓(1),把决策 1 以 𝑠1=2 压入空栈;之后从 𝑖=2 开始处理。用一个指针找到覆盖 𝑖 的区间;当后一个区间的起点不大于 𝑖 时,指针后移。由覆盖 𝑖 的决策算出 𝑓(𝑖) 后,把决策 𝑖 插入栈:

  • 若栈为空,令 𝑠𝑖=1 并压入。
  • 否则与栈顶决策 𝑗 比较。若 𝑖 在 𝑠𝑗 处已经优于 𝑗,弹出 𝑗,继续与新的栈顶比较。
  • 若 𝑖 在 𝑠𝑗 处不优于 𝑗,在 [𝑠𝑗,𝑛] 内二分,找最后一个 𝑗 不劣于 𝑖 的位置 𝑘,令 𝑠𝑖=𝑘+1 并压入。
  • 若 𝑖 在任何位置都不优于栈顶,则不插入。

比较时固定 𝑓(𝑗) 和 𝑓(𝑖),只看候选状态 𝑘 上的转移值。每个决策最多入栈、出栈一次,每次二分 𝑂(log𝑛),总时间为 𝑂(𝑛log𝑛)。

正确性

不变式为:栈中决策的区间按决策下标递增,并覆盖当前及未来的状态;每个区间内对应的决策最优。

由决策单调性,每个决策的最优位置是一段连续区间,区间的起点随决策下标递增。插入新决策 𝑖 时,由单交叉条件,𝑖 优于任一旧决策的位置是一个后缀。从栈顶开始弹出完全被 𝑖 超过的决策,再二分出分界,就能保持区间有序且不丢失候选。

因为 𝑄𝑖,𝑗 可以依赖 𝑓(𝑗),必须按 𝑖 递增计算;但插入决策 𝑖 时 𝑓(𝑖) 已经算出,所以比较使用的是已知值。

易错点

  • 本页按 𝐿(𝑖)=1、𝑅(𝑖)=𝑖−1 说明;窗口端点任意时,新决策不一定对整个后缀可用,不能直接套用。
  • 若二分的分界是最后一个旧决策不劣于新决策的位置 𝑘,新决策的起点是 𝑘+1。
  • 新决策可能处处更优,也可能处处不优;前者要弹空栈并把起点设为 1,后者不要插入。
  • 必须先算出 𝑓(𝑖) 再把决策 𝑖 插入;𝑄𝑖,𝑗 依赖 𝑓(𝑗) 时不能打乱计算顺序。
源码位置