转移方程形式
本文讨论的四边形不等式用于优化以下常见方程：
$$ f(i, j) = \begin{cases} \min_{i \le k < j}\{f(i, k) + f(k + 1, j) + w(i, j)\} & i < j \\ 0 & i = j \\ \infty & i > j \end{cases} $$
这个转移方程状态有 $\mathcal O(n^2)$ 种，决策有 $\mathcal O(n)$ 种，因此直接转移的复杂度为 $\mathcal O(n^3)$。但是如果它有一些特殊性质，那么我们就可以优化复杂度！
条件
首先我们设 $i\le i'<j\le j'$，那么要求转移方程满足如下条件。
区间包含的单调性
$$ w(i', j) \le w(i, j') $$
四边形不等式
$$ w(i, j) + w(i', j') \le w(i', j) + w(i, j') $$
定理
四边形不等式
假如函数 $w$ 满足上述条件，那么函数 $f$ 也满足四边形不等式：
$$ f(i, j) + f(i', j')\le f(i', j) + f(i, j') $$
决策单调性
假如函数 $f$ 满足四边形不等式，那么决策点 $s(i,j)$ 单调，即有如下不等式：
$$ s(i, j) \le s(i, j + 1) \le s(i + 1, j + 1) $$
证明详见 动态规划加速原理之四边形不等式 - 赵爽 。（我才不会告诉你们我不会证明）
优化
有了如上性质和定义，我们可以对转移方程进行优化：
$$ f(i, j) = \begin{cases} \min_{s(i, j - 1) \le k \le s(i + 1, j)}\{f(i, k) + f(k + 1, j) + w(i, j)\} & i < j \\ 0 & i = j \\ \infty & i > j \end{cases} $$
简单观察可以发现，对于确定的区间长度 $j - i + 1$，总复杂度为 $\mathcal O(n)$。故总复杂度为 $\mathcal O(n^2)$。