動態規劃DP的使用條件

任何思想方法都有一定的侷限性，超出了特定條件，它就失去了作用。同樣，動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最優化原理和無後效性。

1.最優化原理（最優子結構性質）

最優化原理可這樣闡述：乙個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，乙個最優化策略的子策略總是最優的。

乙個問題滿足最優化原理又稱其具有最優子結構性質。

圖2例如圖2中，若路線i和j是a到c的最優路徑，則根據最優化原理，路線j必是從b到c的最優路線。這可用反證法證明：假設有另一路徑j'是b到c的最優路徑，則a到c的路線取i和j'比i和j更優，矛盾。

從而證明j'必是b到c的最優路徑。

最優化原理是動態規劃的基礎，任何問題，如果失去了最優化原理的支援，就不可能用動態規劃方法計算。動態規劃的最優化理在其指標函式的可分離性和單調性中得到體現。根據最優化原理匯出的動態規劃基本方程是解決一切動態規劃問題的基本方法。

可以看出，例1是滿足最優化原理的。

2.無後向性

將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的乙個完整總結。這就是無後向性，又稱為無後效性。

如果用前面的記號來描述無後向性，就是：對於確定的xk，無論p1,k-1如何，最優子策略pkn*是唯一確定的，這種性質稱為無後向性。

[例3]bitonic旅行路線問題

歐幾里德貨郎擔問題是對平面給定的n個點確定一條鏈結各點的、閉合的最短遊歷路線問題。圖3(a)給出了七個點問題的解。bitonic旅行路線問題是歐幾里德貨郎擔問題的簡化，這種旅行路線先從最左邊開始，嚴格地由左至右到最右邊的點，然後再嚴格地由右至左到出發點，求路程最短的路徑長度。

圖3（b）給出了七個點問題的解。

圖3這兩個問題看起來很相似。但實質上是不同的。為了方便討論，我將每個頂點標記了號碼。

由於必然經過最右邊的頂點7，所以一條路(p1-p2)可以看成兩條路（p1-7）與(p2-7)的結合。所以，這個問題的狀態可以用兩條道路結合的形式表示。我們可以把這些狀態中，兩條路中起始頂點相同的狀態歸於乙個階段，設為階段[p1,p2]。

那麼，對於bitonic旅行路線問題來說，階段[p1,p2]如果可以由階段[q1,q2]推出，則必須滿足的條件就是:p1有些問題乍一看好像有後向性，但如果按照某種合理的方式重新劃分階段，就可以發現其本質上是無後向性的，所以關鍵是階段的合理劃分，這一點將在動態規劃的技巧中詳細闡述。

3.子問題的重疊性

在例1中我們看到，動態規劃將原來具有指數級複雜度的搜尋演算法改進成了具有多項式時間的演算法。其中的關鍵在於解決冗餘，這是動態規劃演算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不儲存產生過程中的各種狀態，所以它的空間複雜度要大於其它的演算法。

以bitonic旅行路線問題為例，這個問題也可以用搜尋演算法來解決。動態規劃的時間複雜度為o(n2)，搜尋演算法的時間複雜度為o(n!) ，但從空間複雜度來看，動態規劃演算法為o(n2)，而搜尋演算法為o(n)，搜尋演算法反而優於動態規劃演算法。

選擇動態規劃演算法是因為動態規劃演算法在空間上可以承受，而搜尋演算法在時間上卻無法承受，所以我們舍空間而取時間。

設原問題的規模為n，容易看出，當子問題樹中的子問題總數是n的超多項式函式，而不同的子問題數只是n的多項式函式時，動態規劃法顯得特別有意義，此時動態規劃法具有線性時間複雜性。所以，能夠用動態規劃解決的問題還有乙個顯著特徵：子問題的重疊性。

這個性質並不是動態規劃適用的必要條件，但是如果該性質無法滿足，動態規劃演算法同其他演算法相比就不具備優勢。