四边形不等式用于 DP 优化。
状态转移方程
d[ i, j ] = min{ d[ i, k - 1 ] + d[ k + 1 ][ j ] } + w[ i , j ] i <= k <= j
时间复杂度为 O( n * n * n )。
如果函数 w 满足： w[ a, c ] + w[ b, d ] <= w[ b, c ] + w[ a, d ] a < b < c < d
则说 w 满足凸四边形不等式（简称 w 为凸）。
如果函数 w 满足：w[ i, j ] <= w[ i", j" ] [ i, j ] 包含于 [ i", j" ]
则说 w 关于区间包含关系单调。
定理一：
如果 w 同时满足四边形不等式和区间单调关系，则 d 也满足四边形不等式；
定理二：
定理一的条件满足时让 d[ i, j ] 取最小值的 k 为 K[ i, j ]，则 K[ i, j - 1 ] <= K[ i, j ] <= K[ i + 1, j ]；
定理三：
w 为凸当且仅当 w[ i, j ] + w[ i + 1, j + 1 ] <= w[ i + 1, j ] + w[ i, j + 1 ]。
这样每次决策范围变成 K[ i + 1, j ] 到 K[ i, j - 1 ]。
按 j - i 递减的顺序递推各个状态值，则对于每个确定的 j - i 来说，决策总量为 O( n )，故总的时间复杂度为 O( n*n )。
————lrj 黑书
题目：
POJ 1160 Post Office
HDOJ 3480 Division
等等。。。