以石子合并为例

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)

上述的m(i,j)表示区间[i,j]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。

下面看看四边形不等式的作用

前提条件：

（1）区间包含的单调性：如果对于i≤i'<j≤j'，有w(i',j)≤w(i,j')，那么说明w具有区间包含的单调性。

（2）四边形不等式：如果对于i≤i'<j≤j'，有w(i,j)+w(i',j')≤w(i',j)+w(i,j')，我们称函数w满足四边形不等式。

作用：

另 s(i,j)表示m(i,j)取最小值时k的位置，那么由上面的条件可以推出，s(i,j)单调，即s(i,j-1)≤s(i,j)≤s(i+1,j)。(证明略）

那么在实际应用中，就可以对k的枚举范围缩小,即从s(i,j-1)-------s(i+1,j)即可