单调队列DP优化 | Yuhang's Blog

考虑状态转移方程： $f (i) = min_{L (i) \leq j \leq R (i)} {g (j)} + h (i)$ 其中 $i \leq N$ ， $j \leq M$ 。显然暴力的转移复杂度是 $O (M N)$ 。但当 $L (i)$ 和 $R (i)$ 均单调递增，可以将转移的复杂度转移到 $O (N)$ 。维护一个存储 $j$ 的可能取值的单调队列 $Q$ ，并当 $i$ 从小到大变化时，保证：

删除（因为 $L (i)$ 的增加） $Q$ 中小于 $L (i)$ 的元素。
在（因为 $R (i)$ 的增加）添加元素之前，删去 $Q$ 中比添加的元素更劣的元素。设当前添加的元素为 $j_{0}$ ，则 $Q$ 中一个更劣的元素 $j_{1}$ 需满足 $g (j_{0}) \leq g (j_{1})$ 。
- 原因在于由于 $j_{1}$ 更早被添加，必然满足 $j_{1} < j_{0}$ ，那么随着 $L (i)$ 的增加， $j_{1}$ 需要比 $j_{0}$ 更早地被删除，因而在 $j_{1}$ 能存在在 $Q$ 中的剩余时间里，它永远不能成为被选择的元素。
（因为 $R (i)$ 的增加）添加元素。

在需要进行状态转移时，取出队列中存在的最早的添加的元素。考虑队列 $Q$ 的代码实现。设出数组q[M]以及上下界变量l和r。则：

l <= r表示队列中有存在元素。
初值设为l=1，r=0，表示队列中不存在元素。
对q[++r]赋值是在队尾添加元素。
在队列中存在元素的情况下，q[l]是取出队首元素，q[r]是取出队尾元素。
在队列中存在元素的情况下，l++表示删除队首元素；r--表示删除队尾元素。

（存疑）更一般地，状态转移方程可以推广为： $f (i) = min_{j \in S (i)} {g (j)} + h (i)$ 若满足 $\forall i_{1} < i_{2}, (\exists i_{0} < i_{1}, j \in S (i_{0})) \land j \notin S (i_{1}) ⟹ j \notin S (i_{2})$ （这表明当 $i$ 增大时，对符合条件的 $j$ 的集合的每个删除操作都是不需复原的。）且先添加进队列的元素先被删除，则可以使用单调队列。