[蒟蒻修炼计划][学习笔记]四边形不等式优化DP

形如f[i][j]=min{f[i][k]+f[k+1][j]}+w[i][j]的方程中，

w[][]如果同时满足：

①四边形不等式：w[a][c]+w[b][d]<=w[a][d]+w[b][c](a<=b<c<=d)

②区间包含关系单调：w[i+1][j]<=w[i][j]<=w[i][j+1]

则f[][]也满足四边形不等式。

记使f[i][j]最小的k为g[i][j]，则g[i][j-1]<=g[i][j]<=g[i+1][j]

每次枚举k只需枚举[g[i][j-1],g[i+1][j]]。

DP的时间复杂度就从O(n³)压到了O(n²)。

[蒟蒻修炼计划][学习笔记]四边形不等式优化DP

原文：http://www.cnblogs.com/AireenYe/p/5802693.html