前言
某些概念。
四边形不等式是 dp 式子满足决策单调性的必要但不充分条件。
决策单调性：对于某个最优化问题而言，若任意的 \(i<j\) 都满足 \(opt(i) \leq opt(j)\)，那么称该 dp 满足决策单调性。（\(opt_i\) 表示 \(dp_i\) 从 \(opt_i\) 这种情形转移过来）
以下先用最基础的问题讨论。\(f_i = \min\limits_{j=1}^{i-1}\{w(j,i)\}\)。朴素要 \(O(n^2)\)。
四边形不等式
四边形不等式为：对于任意的 \(a\leq b\leq c \leq d\)，有 \(w(a,c) + w(b,d) \leq w(a,d) + w(c,d)\)。
- 如果满足四边形不等式，那么式子满足决策单调性。
证明
假设有 \(b = opt(c), a = opt(d)\) 并且 \(a < b\leq c < d\)。根据假设，可知 \(w(a,d) \leq w(b,d)\) 且 \(w(b,c) \leq w(a,c)\)。得到式子：
\[w(a,d) - w(b,d)\leq0\leq w(a,c) - w(b,c) \]\[w(a,c) + w(b,d) \geq w(a,d) + w(c,d) \]与四边形不等式矛盾。证毕。
以下是一些性质：
- 如果 \(a(i,j)，b(i,j)\) 满足四边形不等式，对于 \(c_1,c_2 \geq 0\)，有 \(c_1a(i,j) +c_2b(i,j)\) 满足四边形不等式。
- 如果