设 DP 方程为 f(i,j)=\min f(i,k)+f(k+1,j)+w(i,j) 并满足四边形不等式，状态 f(i,j) 的最优决策点为 s(i,j). 证明：s(i,j-1)\leq s(i,j)\leq s(i+1, j).

下面证明前半部分 s(i,j-1)\leq s(i,j). 令 s(i,j-1)=k. 根据 DP 方程，对于所有的 i\leq l< k ，都有 f(i,k)+f(k+1,j-1)\leq f(i,l)+f(l+1,j-1) 由四边形不等式，得 f(l+1, j-1)+f(k+1, j)\leq f(k+1,j-1)+f(l+1,j) 移项得 f(k+1, j)-f(k+1,j-1)\leq f(l+1,j)-f(l+1, j-1) 与前式相加得 f(i,k)+f(k+1,j)\leq f(i,l)+f(l+1,j) 即若对于状态 f(i,j-1) 从 k 转移比从 l(l<k) 转移优，则对于 f(i,j) 同样有 从 k 转移比从 l 转移优。因此，最优决策点后移， s(i,j-1)\leq s(i,j) 成立。 后半部分证明同理。