四边形不等式优化
定义
四边形不等式
定义
设 $w(x, y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a\leq b\leq c\leq d$，都有 $w(a, d)+w(b, c)\geq w(a, c)+w(b, d)$ 成立，则称函数 $w$ 满足四边形不等式。
简单描述为：交叉小于包含。
定理
四边形不等式还可以表述为：
设 $w(x, y)$ 是定义在整数集合上的二元函数。若对于定义域上的任意整数 $a
这算是另一种定义，可以证明与定义等价。
区间包含单调性
定义
如果对于任意的 $l\leq l’\leq r’\leq r$，都有 $w(l’, r’)\leq w(l, r)$ 成立，那么称函数 $w$ 具有区间包含单调性。
用途
一般用于区间 DP 问题，转移方程一般形如：
dp[i, j]=\left\{
\begin{array}{lr}
\min_{i\leq k<j}{\{dp[i, k]+dp[k+1, j]+w[i, j]\}}, &i<j\\
0, &i=j\\
\infty, &i>j
\end{array}
\right.
$$
转移方程的含义：
- $dp[i, j]$ 表示从 $i$ 到 $j$ 的最小花费，题目一般需要求出 $dp[1, n]$.
- $dp[i, k]+dp[k+1][j]$ 体现递推关系，$k$ 在 $i, j$ 之间滑动，$k$ 存在一个最优值，使得 $dp[i, j]$ 最大/最小。
- $w[i, j]$ 的性质非常重要。$w[i, j]$ 是与题目有关的费用，如果它满足四边形不等式和区间包含单调性，那么在 DP 的时候，就能进行四边形不等式优化。
这类中的经典问题就是石子合并。
用法
只需要简单的优化操作，就能把上面的 $\mathcal{O}(n^3)$ 变成 $\mathcal{O}(n^2)$.
把循环 $i\leq k\leq j$ 改为 $s[i, j-1]\leq k\leq s[i+1, j]$，其中 $s[i, j]$ 记录从 $i$ 到 $j$ 的最优分割点。
在计算 $dp[i, j]$ 的最值时，可以得到区间 $i, j$ 的最优分割点 $k$，记录到 $s[i, j]$ 中即可。
也就是说优化后的状态转移方程为：
dp[i, j]=\left\{
\begin{array}{lr}
\min_{s[i, j-1]\leq k\leq s_[i+1, j]}{\{dp[i, k]+dp[k+1, j]+w[i, j]\}}, &i<j\\
0, &i=j\\
\infty, &i>j
\end{array}
\right.
$$
for(int i = 1; i <= n; i++) {
dp[i][i] = 0;
s[i][i] = i; // s[][] 的初始化
}
for(int len = 2; len <= n; len++) {
for(int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
for(int k = s[i][j - 1]; k <= s[i + 1][j]; k++) { //四边形不等式优化
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + w[i][j]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j];
s[i][j] = k;
}
}
}
}
考场上，对于能否使用四边形不等式优化的判断，一般情况下随机数据+$\mathcal{O}(n^3)$ DP之后，编程判断是否满足单调性就可以了，可以不用数学方法证明。
原理
引理1
描述
对于上面那种形式的状态转移方程，如果 $w[i, j]$ 满足四边形不等式和区间包含单调性，那么 $dp[i, j]$ 也满足四边形不等式。
证明
即证，对于 $a\leq b\leq c\leq d$，有 $dp[a, c]+dp[b, d]\leq dp[a, d]+dp[b, c]$.
不妨设 $dp[a, c]$ 的最优值在 $x$ 取到，$dp[b， d]$ 的最优值在 $y$ 取到，且 $x < y$，
于是可以得到：
\begin{aligned}
dp[a, c]+dp[b, d] &= dp[a, x]+dp[x + 1, c] + w[a, c]+dp[b, y]+dp[y+1, d]+w[b, d]\\
\\
&\leq dp[a, x]+dp[x + 1, c]+w[a, d]+dp[b, y]+dp[y + 1, d]+w[b, c]\\
\\
&\leq dp[a, x]+dp[x + 1 , d]+w[a, d]+dp[b, y]+dp[y+1, c]+w[b, c]\\
\\
&=dp[a, d]+dp[b, c]
\end{aligned}
$$
其中第三行用到了结论 $dp[x + 1, c]+dp[y + 1, d]\leq dp[x + 1, d]+dp[y + 1, c]$，可以同理递归证明。
同理若 $y < x$ 命题也成立。
引理2
描述
记 $s[i, j]=k$ 是 $dp[i, j]$ 取得最优值时的 $k$，如果 dp 满足四边形不等式，那么有 $s[i, j-1]\leq s[i, j]\leq s[i+1, j]$，即 $s[i, j-1]\leq k\leq s[i+1, j]$.
证明
记 $f[k, i, j]=dp[i, k]+dp[k + 1, j] + w[i, j]$，
只需证所有不在 $[s[i, j-1], s[i+1, j]]$ 区间内的决策点肯定不是最优的。
那么决策点位置有两种：在区间左右两侧，不妨设在左侧。
也就是说，记 $x=s[i, j-1]$，决策点 $y\in(i, x)$.
此时若证明证 $f[x, i, j]\leq f[y, i, j]$，就能说明 $y\in(i, x)$ 不是最优的。
根据 $s$ 的定义，显然有 $f[x, i, j-1]\leq f[y, i, j-1]$，
故证明 $f[y, i, j-1]-f[x, i, j-1]\leq f[y, i, j]-f[x, i, j]$ 即可，
移项得到只需证 $f[y, i, j-1]+f[x, i, j]\leq f[y, i, j]+f[x, i, j-1]$，
根据 $f$ 的定义，这就等价于证明：
\begin{aligned}
dp[i, y]+dp[y+1, j-1]+w[i, j-1]+dp[i, x]+dp[x+1, y]+w[i, j]\\
\leq dp[i, y]+dp[y + 1, j]+w[i, j]+dp[i, x]+dp[x + 1, j-1]+w[i, j-1]
\end{aligned}
$$
消去相同项，只需证：
dp[y+1, j-1]+dp[x + 1, y]\leq dp[y+1, j] +dp[x + 1, j-1]
$$
又因为 $dp$ 满足四边形不等式，故上式成立。
对于决策点在区间右侧的情况同理可证。
定理——Knuth-Yao DP Speedup Theorem
描述
如果 $w(i, j)$ 满足四边形不等式和区间包含单调性，则用 DP 计算 $dp$ 数组的时间复杂度是 $O(n^2)$ 的。
证明
\begin{aligned}
dp[i, j]=\left\{
\begin{array}{lr}
\min_{s[i, j-1]\leq k\leq s_[i+1, j]}{\{dp[i, k]+dp[k+1, j]+w[i, j]\}}, &i<j\\
0, &i=j\\
\infty, &i>j
\end{array}
\right.
\end{aligned}
$$
在求 $dp[i, j]$ 的时候，$s[i, j-1]$ 和 $s[i+1, j]$ 一定已经算出，这样缩小决策变量范围进行优化。
\begin{align}
&\sum_{len=2}^n\sum_{i=1}^{n-len+1}(1+s[i+1, i+len-1]-s[i, i+len-2])\\
&=\sum_{len=2}^{n}
\left[
\sum_{i=1}^{n-len+1}(1) + \sum_{i=1}^{n-len+1}(s[i+1, i+len-1]) – \sum_{i=1}^{n-len+1}(s[i, i+len-2])
\right]\\
&=\sum_{len=2}^{n}
\left\{
(n-len+1)+s[n-len+2, n]-s[1, len-1]
\right\}\\
&\leq \sum_{len=2}^{n}(2n-len+1)
\end{align}
$$
所以复杂度为 $\mathcal{O}(n^2)$.