四邊形不等式

如果對於任意的，有，那麼滿足四邊形不等式。

設表示動態規劃的狀態量。

有類似如下的狀態轉移方程：

m滿足四邊形不等式是適用這種優化方法的必要條件

對於一道具體的題目，我們首先要證明它滿足這個條件，一般來說用數學歸納法證明，根據題目的不同而不同。

通常的動態規劃的複雜度是，我們可以優化到

定義為函數對應的使得取得最小值的k值。

我們可以證明，

那麼改變狀態轉移方程為：

複雜度分析：不難看出，複雜度決定於s的值，以求為例，

所以總複雜度是O(n)

對的證明：

設

對於任意，有（這裡以為例,max的類似），接下來只要證明，那麼只有當時才有可能有

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

∵m滿足四邊形不等式，∴對於有

∴

∴，同理可證

證畢

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

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

1.

證明w滿足四邊形不等式，這裡w是m的附屬量，形如，此時大多要先證明w滿足條件才能進一步證明m滿足條件

2.

證明m滿足四邊形不等式

3.

證明