定义1：当决策代价函数w满足w[a, c]+w[b, d]<=w[a, d]+w[b, c](a<=b<=c<=d)时，称w满足四边形不等式。
定义2：当函数w满足w[b, c]<=w[a, d](a<=b<=c<=d)时，称w关于区间包含关系单调。
如果状态转移方程dp[i, j] = min{dp[i, k-1]+dp[k, j]}+w[i, j](i<k<=j)，且w满足四边形不等式，则有
定理1：上式dp满足四边形不等式。
定理2：令让dp[i, j]取最小值的k为K[i, j]，则有K[i, j-1]<=K[i, j]<=K[i+1, j]。
定理1证明：设k=K[b, c]，则 dp[a, c] + dp[b, d] <= dp[a, k-1] + dp[k, c] + w[a, c] + dp[b, k-1] + dp[k, d] + w[b, d]
<= dp[a, k-1] + dp[k, d] + w[a, d] + dp[b, k-1] + dp[k, c] + w[b, c]
= dp[a, d] + dp[b, c]
定理2证明：设k=K[i, j-1]，令i<k‘<k<j-1<j，根据定理1，则有
dp[k‘, j-1] + dp[k, j] <= dp[k‘, j] + dp[k, j-1]
记S[k, i, j]=w[i, j] + dp[i, k-1] + dp[k, j]，不等式两侧同时加上w[i, j-1] + w[i, j] + dp[i, k-1] + dp[i, k‘-1]，可得
S[k‘, i, j-1] + S[k, i, j] <= S[k‘, i, j] + S[k, i, j-1]
根据k的定义，显然有S[k, i, j-1]<=S[k‘, i, j]，故有S[k, i, j]<=S[k‘, i, j]，所以k‘不可能是K[i,j]，因此K[i, j]>=K[i, j-1]。
同理可得K[i, j]<=K[i+1, j]。
由于推出了最优决策K的单调性，从而可以减少每个状态转移的状态数，将复杂度从O(N^3)优化到O(N^2)。做法是：按照j-i划分阶段来求K[i, j]。显然根据j-i的长度有N个阶段，不妨设每个阶段枚举的长度（j-i）为d。求K[i, j]的复杂度是O(K[i+1, j]-K[i, j-1]+1)，则第d个阶段（即计算K[1, 1+d] 到K[n-d, n]）复杂度O(K[n-d+1, n] - K[1,d] +n-d)<=O(N)。故总时间复杂度为O（N^2）。
最终方程变为dp[i, j] = min{dp[i, k-1]+dp[k, j]}+w[i, j](K[i, j-1]<k<=K[i+1, j])。
伪代码：
for (int i=1;i<=n;i++) {
K[i][i] = i;
dp[i][i] = p[i];
sum[i] = sum[i-1] + p[i];
}
for (int l=2;l<=l;l++) //枚举长度
for (int i=1;i<=n-l+1;i++) { //枚举首指针
int j = i+l-1; //尾指针
dp[i][j] = maxw;
for (int k=K[i][j-1];k<=K[i+1][j];k++)
if (dp[i][j] > dp[i][k-1]+dp[k][j]) {
dp[i][j] = dp[i][k-1]+dp[k][j];
K[i][j] = k;
}
dp[i][j] += sum[j]-sum[i-1];
}