四边形不等式

不妨设 a < c a<c a<c，有：
w a , c + w a + 1 , c + 1 ≤ w a + 1 , c + w a , c + 1 ( 1 ) w_{a,c}+w_{a+1,c+1}\leq w_{a+1,c}+w_{a,c+1} (1) wa,c​+wa+1,c+1​≤wa+1,c​+wa,c+1​(1)

w a + 1 , c + w a + 2 , c + 1 ≤ w a + 1 , c + 1 + w a + 2 , c ( 2 ) w_{a+1,c}+w_{a+2,c+1}\leq w_{a+1,c+1}+w_{a+2,c}(2) wa+1,c​+wa+2,c+1​≤wa+1,c+1​+wa+2,c​(2)

( 1 ) + ( 2 ) (1)+(2) (1)+(2)得到：
w a , c + w a + 2 , c + 1 ≤ w a + 2 , c + w a , c + 1 ( 3 ) w_{a,c}+w_{a+2,c+1}\leq w_{a+2,c}+w_{a,c+1}(3) wa,c​+wa+2,c+1​≤wa+2,c​+wa,c+1​(3)
以此类推，将(1)(3)式对比研究，令 a + 2 = b a+2=b a+2=b，有：
w a , c + w b , c + 1 ≤ w b , c + w a , c + 1 ( 4 ) w_{a,c}+w_{b,c+1}\leq w_{b,c}+w_{a,c+1}(4) wa,c​+wb,c+1​≤wb,c​+wa,c+1​(4)
同理，可以对 c + 1 c+1 c+1 进行放缩令 d = c + 1 d=c+1 d=c+1 ，有：
w a , c + w b , d ≤ w b , c + w a , d w_{a,c}+w_{b,d}\leq w_{b,c}+w_{a,d} wa,c​+wb,d​≤wb,c​+wa,d​
总结一下，我们将 a + 1 a+1 a+1 ， c + 1 c+1 c+1 分别进行放缩，成为 b b b ， d d d ，即第二、四项。

由此得到一维决策单调性： s i ≤ s i + 1 s_i\leq s_{i+1} si​≤si+1​

如果加上 w w w 函数的单调性： w i , j ≤ w i − 1 , j + 1 w_{i,j}\leq w_{i-1,j+1} wi,j​≤wi−1,j+1​

就可以得到二维决策单调性： s i , j − 1 ≤ k ≤ s i + 1 , j s_{i,j-1}\leq k\leq s_{i+1,j} si,j−1​≤k≤si+1,j​

前面讨论的都是 m i n min min ，如果是 m a x max max ，也可以进行四边形不等式优化。此时四边形不等式是“反”的，决策单调性的结论不变。

一维决策单调性优化

形如 f j = m i n 0 ≤ i < j ( f i + v a l i , j ) f_j=min_{0\leq i<j}(f_i+val_{i,j}) fj​=min0≤i<j​(fi​+vali,j​) ，若 v a l val val 函数满足四边形不等式或增长率越来越慢存在分界点，则 f f f 具有决策单调性或决策间存在最优分界点，可以用单调栈或分治解决。

二维决策单调性优化

形如 d p i , j = m i n ( d p i , k + d p k + 1 , j + w i , j ) dp_{i,j}=min(dp_{i,k}+dp_{k+1,j}+w_{i,j}) dpi,j​=min(dpi,k​+dpk+1,j​+wi,j​) 的 区间DP 问题，如果 w w w 满足四边形不等式和单调性，则可以 O ( n 2 ) O(n^2) O(n2) 解决 。