四边形不等式是一种比较生草常见的优化动态规划的方法
定义
一般的，如果对于任意的 (a1 leq a2 < b1 leq b2)，
有 (m[a1,b1] + m[a2,b2] ≤ m[a1,b2] + m[a2,b1])，
那么 (m[i,j]) 满足四边形不等式
优化
设 (m[i,j]) 表示动态规划的状态量
(m[i,j]) 有类似如下的状态转移方程:
(m[i,j] = min {{ m[i,k] + m[k,j] | i≤k≤j }})
(m) 满足四边形不等式是适用这种优化方法的必要条件
对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用数学归纳法证明，根据题目的不同而不同。
通常的动态规划的复杂度是 (O( n^3 ))，我们可以优化到 (O( n^2 ))
定义 (s(i,j)) 为函数 (m(i,j)) 对应的使得 (m(i,j)) 取得最小值的k值。
我们可以证明，(s[i,j-1] ≤ s[i,j] ≤ s[i+1,j])
那么改变状态转移方程为:
(m[i,j] = min {{ m[i,k] + m[k,j] }|s[i,j-1] ≤ k ≤ s[i+1,j]})
复杂度分析:不难看出，复杂度决定于s的值，以求 m[i,i+L] 为例，
(( s[2,L+1] - s[1,L] ) + ( s[3,L+2] - s[2,L+1] )+ …+ ( s[n-L+1,n] - s[n-L,n-1] ) = s[n-L+1,n] - s[1,L] ≤ n)
所以总复杂度是 (O( n ))
证明
对 (s[i,j-1] ≤ s[i,j] ≤ s[i+1,j]) 的证明:
设 (mk[i,j] = m[i,k] + m[k,j]) , $ s[i,j] = d$
对于任意 (k < d)，有 (mk[i,j] ≥ md[i,j]) ( 这里以 (m[i,j] = min {{ m[i,k] + m[k,j] }}) 为例 , max 的类似) ，
接下来只要证明 (mk[i+1,j] ≥ md[i+1,j]) ，
那么只有当 (s[i+1,j] ≥ s[i,j]) 时才有可能有 (mk[i+1,j] ≥ md[i+1,j])
证明过程：
(( mk[i+1,j] - md[i+1,j] ) - ( mk[i,j] - md[i,j] ))
(= ( mk[i+1,j] + md[i,j] ) - ( md[i+1,j] + mk[i,j] ))
(= ( m[i+1,k] + m[k,j] + m[i,d] + m[d,j] ) - ( m[i+1,d] + m[d,j] + m[i,k] + m[k,j] ))
(=( m[i+1,k] + m[i,d] ) - ( m[i+1,d] + m[i,k] ))
(ecause) (m) 满足四边形不等式
( herefore) 对于 (i < i+1 ≤ k < d)
$ $
有 (m[i+1,k] + m[i,d] ≥ m[i+1,d] + m[i,k])
( herefore) (( mk[i+1,j] - md[i+1,j] ) ≥ ( mk[i,j] - md[i,j] ) ≥ 0)
( herefore) (s[i,j] ≤ s[i+1,j]) ，同理可证 (s[i,j-1] ≤ s[i,j])
证毕
扩展
以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。
解决这类问题的大概步骤是:
- 证明 (w) 满足四边形不等式，这里 (w) 是 (m) 的附属量，形如 (m[i,j] = opt {{ m[i,k] + m[k,j] + w[i,j] }})，此时大多要先证明 (w) 满足条件才能进一步证明 (m) 满足条件
- 证明 (m) 满足四边形不等式
- 证明 (s[i,j-1] ≤ s[i,j] ≤ s[i+1,j])