区间dp中，我们可以见到以下式子：
$dp(i,j)=min_{i\leq k< j}(dp(i,k)+dp(k+1,j)+~~~w(i,j)~~~)$
那么，对于这个 $w$ ，如果满足单调性：
$$(l\leq l’\leq r’\leq r)~~~w(l’,r’)\leq w(l,r)$$
满足四边形不等式：
$$(l\leq l’\leq r’\leq r)~~~w(l,r’)+w(l’,r)\leq w(l,r)+w(l’,r’)$$
那么有，对于上面的dp而言，满足四边形不等式。
证明：
对于$l=l’$或者$r=r’$，有：
$dp(l,r’)+dp(l’,r), ~~~ dp(l,r)+dp(l’,r’)$，我觉得你观察下就能整出来。。
那么，数学归纳法整个：对$len=r-l+1$归纳：
$l\leq l’=r’\leq r$，此时$len=0$.
对于$dp(l,r’)+dp(l’,r)$有：
$原式=dp(l,r’)+dp(r’,r) \leq dp(l,r)+dp(l’,r’)=dp(l,r)$
即证明该式成立。
则对$dp(l,r)$:
设$k=max{ x|dp(l,r)=dp(l,x-1)+dp(x,r)+w(l,r)}$
由对称性：不妨设$k\leq r’$.
有：
$$
\begin{aligned}
dp(l,r’)+dp(l’,r) &\leq w(l,r’)+dp(l,k-1)+dp(k,r’)+dp(l’,r)\\
& \leq w(l,r)+dp(l,k-1)+dp(k,r’)+dp(l’,r)\\
& \leq w(l,r)+dp(l,k-1)+dp(k,r)=dp(l,r)
\end{aligned}$$
2. $l<l’< r’< r$
对$dp(l,r’)+dp(l’,r)$而言：设
$y=max{x|dp(l,r’)=dp(l,x-1)+dp(x,r’)+w(l,r’) }$
$z=max{x|dp(l’,r)=dp(l’,x-1)+dp(x,r)+w(l’,r)}$
则：
不妨设：$y\leq z$,则有$l<z\leq y \leq r$.
原式
$$\begin{aligned}
\leq dp(l,y-1)+dp(y,r’)+w(l,r’)+w(l’,r)+dp(l’,z-1)+dp(z,r)\\
\leq w(l,r)+w(l’,r’)+dp(l,y-1)+dp(l’,z-1)+dp(y,r’)+dp(z,r)\\
\leq w(l,r)+w(l’,r’)+dp(l,y-1)+dp(l’,z-1)+dp(y,r)+dp(z,r’)\\
= dp(l,r)+dp(l’,r’)
\end{aligned}
$$
这性质和区间$dp$有啥关系呢？
该性质能够证明单调性：对于满足四边形不等式的dp状态，定义$s(i,j)$为$dp(i,j)$决策过程的最大值。
因此有:$s(i,j)$单调，$s(i,j)\leq s(i,j+1)\leq s(i+1,j+1)$.
因此在dp过程中：
$$dp(i,j)=\begin{cases}
min_{s(i,j-1)\leq k \leq s(i+1,j)}{dp(i,k-1)+dp(k,j)+w(i,j)} & i<j \\
0 &i=j \\
+\infty &i>j
\end{cases}$$
