四邊形不等式

如果對於任意的a1≤a2＜b1≤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)

設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])

∵m滿足四邊形不等式，∴對於i＜i+1≤k＜d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]

∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0

∴s[i,j]≤s[i+1,j]，同理可證s[i,j-1]≤s[i,j]

證畢

以上所給出的狀態轉移方程只是一種比較一般的，其實，很多狀態轉移方程都滿足四邊形不等式優化的條件。

解決這類問題的大概步驟是：