记录单调队列优化dp的原理、常见模型以及编码需要注意的细节。

单调队列优化dp

概述

单调队列本质上只能解决一类问题：滑动窗口的最值问题。滑动窗口不要求大小固定，只要求端点单调往一个方向移动，所以其可以优化的dp一般存在明显的求滑动窗口最值的步骤。

dp的优化是在想清楚朴素dp之后才要考虑的，要把dp的功能设计以及dp的优化分开来考虑，先保证正确性，再提高性能。

原理

抽象地说，我们在dp问题中想求形如下式的结果：

$dp[i] = \min_{L(i)\leq j\leq R(i)}\{dp[j] + val(i, j)\}$

其中，$\min$也可以换成$\max$，$L(i)$ 和 $R(i)$ 代表我们关心的 $j$ 的上下界，且 $L(i)$ 和 $R(i)$ 关于 $i$ 向同一个方向单调变化，$val(i, j)$是关于 $i, j$ 的二元函数，且$val(i, j)$在化简之后每一项仅与 $i, j$ 中的一个有关系，即 $val(i, j) = f(i) + g(j)$ ，则上式可以转化为：

$dp[i] = \min_{L(i)\leq j\leq R(i)}\{dp[j] + g(j)\} + f(i)$

对于$\min$里面的部分，由于其仅与 $j$ 有关，所以可以使用单调队列来维护。这样下来，枚举所有的 $i$ ，$\min$ 内部的总时间复杂度仅为 $O(n)$ ，相比于朴素做法，省去了枚举$[L(i), R(i)]$的过程。