四邊形不等式用于 DP 優(yōu)化。
狀態(tài)轉(zhuǎn)移方程
d[ i, j ] = min{ d[ i, k - 1 ] + d[ k + 1 ][ j ] } + w[ i , j ] i <= k <= j
時間復(fù)雜度為 O( n * n * n )。
如果函數(shù) w 滿足： w[ a, c ] + w[ b, d ] <= w[ b, c ] + w[ a, d ] a < b < c < d
則說 w 滿足凸四邊形不等式（簡稱 w 為凸）。
如果函數(shù) w 滿足：w[ i, j ] <= w[ i", j" ] [ i, j ] 包含于 [ i", j" ]
則說 w 關(guān)于區(qū)間包含關(guān)系單調(diào)。
定理一：
如果 w 同時滿足四邊形不等式和區(qū)間單調(diào)關(guān)系，則 d 也滿足四邊形不等式；
定理二：
定理一的條件滿足時讓 d[ i, j ] 取最小值的 k 為 K[ i, j ]，則 K[ i, j - 1 ] <= K[ i, j ] <= K[ i + 1, j ]；
定理三：
w 為凸當(dāng)且僅當(dāng) w[ i, j ] + w[ i + 1, j + 1 ] <= w[ i + 1, j ] + w[ i, j + 1 ]。
這樣每次決策范圍變成 K[ i + 1, j ] 到 K[ i, j - 1 ]。
按 j - i 遞減的順序遞推各個狀態(tài)值，則對于每個確定的 j - i 來說，決策總量為 O( n )，故總的時間復(fù)雜度為 O( n*n )。
————lrj 黑書
題目：
POJ 1160 Post Office
HDOJ 3480 Division
等等。。。