动态规划的简单优化 斜率优化
__ryp__
·
·
个人记录
动态规划的思路就是保存先前的计算结果，以减少后续问题的计算量。这在另一个维度上看，就是保存子问题的解，并以此构造原问题的解。
动态规划能将高复杂度的搜索等算法，转换为多项式复杂度的较优算法，非常强大，但它也有优化的空间。
在本篇文章中我们将介绍一些简单的动态规划问题的优化，以此介绍较难一些动态规划问题的优化思路。
斜率优化
这样的状态转移方程可以考虑斜率优化：
\begin{aligned}
f(i) = \min\limits_{j \le R_i} \{f(j) + A_i\times B_j\}
,\space \text{s.t.} \space R_t \le R_{t + 1},A_t \le A_{t+1}, B_t \le B_{t+1}
\end{aligned}
（\min 也可为 \max）
这样的方程一般来说是 O(n^2) 的，在优化后可以达到 O(n)。下面是推导过程。
我们先将 i 及关于 i 的所有函数看作常量，同时去掉最值限制，做一点变形得到
g(j) = A_i\times j - f(i)
（请思考：若 B 并不递增，匆忙抽象出 g 会导致什么问题？）
那么，在 [0, R_i] 里，我们有一系列直线，记作 g_1, \cdots, g_t，它们的斜率均为 A_i，即它们互相平行。
我们回到问题：我们要求的是 f(j) + A_i\times B_j 最小，实际上在将 i 看为静止后，问题变成了求 g_1, \cdots, g_t 中截距最小的直线所对应的自变量。
我们将每一个 j \le R_i 入队进行处理。我们有如下性质：
斜率优化原理
设 k_{ij} 表示 g(i) 与 g(j) 连线的斜率。我们有：对当前入队的点 t，若有 x \lt t 使得 k_{x+1,t} \lt k_{x, x+1}，那么我们有 b_{x+1} 至少大于 b_t 与 b_{x} 中的一个。也即，x + 1 一定不是这三点中的最小值。
这个性质可以帮助我们排除队中的非最优点。以下对 x = t - 1 时的证明：
\begin{aligned}
k_{t-2, t-1} - k_{t-1, t} &= \frac{A_i\times ((t-1) - (t-2)) + b_{t-1} - b_{t-2}}{(t-1)-(t-2)} - \frac{A_i\times (t - (t-1)) + b_t - b_{t-1}}{t - (t-1)} \\
&= b_{t-1}-b_{t-2}-b_t + b_{t-1} \\
&= 2b_{t-1} - b_{t-2} - b_{t} \ge 0 \\
\text{i.e.} \space 2b_{t-1} \gt b_{t} + b_{t-2}
\end{aligned}
反证，容易得到 b_{t-1} 至少大于 b_t 与 b_{t-2} 中的一个，即 g(t-1) \ne \min \{g(t), g(t-1), g(t-2)\}
（请自己证明一般情况）
我们继续考虑求每个 f(i) 的问题。我们容易发现：f(i) 是 [0, R_i] 上的最小值。由于 R 是增序列，那么 [0, R_{i + 1}] 一定包含了 [0, R_i]。由此，f(i + 1) 一定小于等于 f(i)。我们由 A 的单增性可知，处理 f(i) 所得到的所有 j 上的直线，其斜率一定小于 f(i + 1) 上的同类。由此，我们不需要对每一个 i 都维护一个队列，只需要在一个固定的队列上操作即可。
以上是斜率优化。