四边形不等式优化DP

对于状态转移方程$m(i,j)=min(m(i,k-1),m(k,j))+w(i,j)(i\le k\le j)$,我们常常使用四边形不等式将时间复杂度从$O(n^3)$优化至$O(n^2)$

区间包含的单调性:如果小区间包含于大区间中,那么小区间的w值不超过大区间的w值

四边形不等式:两个交错区间的w的和不超过小区间与大区间的w的和

如果上述的w函数同时满足区间包含单调性和四边形不等式性质,那么函数m也满足四边形不等式性质

定义$s(i,j)$表示$m(i,j)$取得最优值时对应的下标(即$i\le k\le j$时,$k$处的$w$值最大,则$s(i,j)=k$)
则$s(i,j)\le s(i,j+1)\le s(i+1,j+1)$

所以转移方程可以改写为下式:
$m(i,j)=min(m(i,k-1),m(k,j))+w(i,j)(s(i,j-1)\le k\le s(i+1,j))$

Contents