斜率优化概念

在动态规划中，某些递推方程可以转化成 DP[i] = f[j] + x[i] 的形式，其中 f[j] 只保存与 j 相关的量。这类方程有两类优化方式:

单调队列优化
局限性：f[j] 必须只能和 j 有关，且其递推方程可以分解成上述形式，否则该优化方案不合适。
斜率优化
可以较好的解决单调队列的局限性。

斜率优化应用实战

题目：打印数字

给定一串数字(含有N个元素)，连续输出其中的一个子串，所花费用是“子串数字和的平方加上一个常数M”。求解：输出这一串数字的最小花费。
题目来源自HDU

题解

假设下标 i 从 1 开始；
dp[i] : 表示输出到第 i 个数字时的最少花费；
sum[i] : 表示从a[1] 到 a[i] 的数字和；
递推方程: dp[i] = dp[j] + M + (sum[i] - sum[j])²

从该递推公式可以看出，我们需要二层循环，当输入的数字串非常大时，显然非常耗时。时间复杂度O(N²)

斜率优化

步骤1：问题是否具有决策单调性

步骤2：斜率优化
假设k<j<i, i 是当前的位置, 由题意知，如果选择 j 优于选择 k，则
dp[j] + M + (sum[i] - sum[j])² < dp[k] + M + (sum[i] - sum[k])².
化简该式：{ (dp[j] + sum[j]²) - (dp[k] + sum[k]²) } / 2(sum[j] - sum[k]) < sum[i]。

记 y_j = (dp[j] + sum[j]²)
记 y_k = (dp[k] + sum[k]²)
记 x_j = 2sum[j]
记 x_k = 2sum[k]

令 g(j, k) = (y_j - y_k) / (x_j - x_k)
当g(j, k) < sum[i]成立是，说明选择 j 优于选择 k。

假设k<j<i, 如果 g(i, j) < g(j, k), 则 j 永远不可能成为最优解
证明：
当g(i, j) < sum[i]时，选择 i 优于选择 j，因此，排除 j
当g(i, j) >= sum[i]时，选择 j 优于选择 i，又 g(j, k) > g(i, j) >=sum[i], 说明选择 k 优于选择 j，因此，同样排除 j.

由于排除不必要的点，因此缩小了搜索空间。

步骤3：选择最优解
设k<j<i, 如果 g(i, j) < g(j, k), 则 j 永远不可能成为最优解。因此整个有效点集应该呈现下凸(开口向上)性质，即：kj 的斜率小于 ji 的斜率，如图1所示

图1

因此，从左到右，有效点集的斜率是单调递增的。

斜率优化总结如下：

用一个单调队列 q 来维护解集。
更新q, 同时维护解集的下凸性：
假设队列中从头到尾已经有元素k, j, i (k<j<i)。那么当d要入队的时候，我们维护队列的上凸性质，即如果g[d,i] < g[i,j]，则将 i 点删除，直到找到g[d,x]>=g[x,y]为止(x,y都是队列中的元素)，并将d点加入在该位置中。
求解：
从队头开始，如果已有元素a b c (a<b<c)，当 i 点要求解时，如果g[b,a] < sum[i]，那么说明b点比a点更优，a点可以排除，于是a出队。最后dp[i] = dp[q[head]] + M + (sum[i] - sum[q[head]])²;。

代码如下：

//TODO

复杂度分析

空间复杂度：

注：本文主要参考了文献1，但文献1中由太多的错误，且排版混乱，叙述不清晰，因此在理解的基础上，写下此文。

参考文献

[1] http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

动态规划之斜率优化