二分栈优化 DP
当 Q_(i,j) 可依赖 f(j)、最优决策满足决策单调性中的单交叉条件时,用二分栈在线维护决策区间,以 O(n log n) 求出全部 f(i)。时间 O(n log n),空间 O(n) · 标签 动态规划 / 决策单调性 / 二分栈 / DP 优化
问题形式
考虑 1D/1D 动态规划中,当 可以依赖 ,且最优决策满足 决策单调性 中的单交叉条件时,方程
可以按 递增在线计算。下面按 、 说明;若窗口另有约束,需要先检查新决策是否仍对一段后缀的未来状态可用。
核心思想
维护一个栈,栈中每个决策 带一个起点 ;决策 在 上最优。
先计算基础状态 ,把决策 以 压入空栈;之后从 开始处理。用一个指针找到覆盖 的区间;当后一个区间的起点不大于 时,指针后移。由覆盖 的决策算出 后,把决策 插入栈:
- 若栈为空,令 并压入。
- 否则与栈顶决策 比较。若 在 处已经优于 ,弹出 ,继续与新的栈顶比较。
- 若 在 处不优于 ,在 内二分,找最后一个 不劣于 的位置 ,令 并压入。
- 若 在任何位置都不优于栈顶,则不插入。
比较时固定 和 ,只看候选状态 上的转移值。每个决策最多入栈、出栈一次,每次二分 ,总时间为 。
正确性
不变式为:栈中决策的区间按决策下标递增,并覆盖当前及未来的状态;每个区间内对应的决策最优。
由决策单调性,每个决策的最优位置是一段连续区间,区间的起点随决策下标递增。插入新决策 时,由单交叉条件, 优于任一旧决策的位置是一个后缀。从栈顶开始弹出完全被 超过的决策,再二分出分界,就能保持区间有序且不丢失候选。
因为 可以依赖 ,必须按 递增计算;但插入决策 时 已经算出,所以比较使用的是已知值。
易错点
- 本页按 、 说明;窗口端点任意时,新决策不一定对整个后缀可用,不能直接套用。
- 若二分的分界是最后一个旧决策不劣于新决策的位置 ,新决策的起点是 。
- 新决策可能处处更优,也可能处处不优;前者要弹空栈并把起点设为 ,后者不要插入。
- 必须先算出 再把决策 插入; 依赖 时不能打乱计算顺序。