狀態轉移方程

動態規劃中本階段的狀態往往是上一階段狀態和上一階段決策的結果。若給定了第K階段的狀態Sk以及決策uk(Sk),則第K+1階段的狀態Sk+1也就完全確定。也就是説Sk+1與Sk,uk之間存在一種明確的數量對應關係，記為Tk(Sk,uk),即有Sk+1= Tk(Sk,uk)。 這種用函數表示前後階段關係的方程，稱為狀態轉移方程。在上例中狀態轉移方程為 Sk+1= uk(Sk) 。 ^[1] 

適用條件

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

1.最優化原理（最優子結構性質） 最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。

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

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

如何設計動態轉移方程

如果滿足上述條件，一般可以按照以下步驟進行設計：

一、確定問題的決策對象

二、對決策對象劃分階段

三、對各階段確定狀態變量

四、根據狀態變量確定費用函數和目標函數

五、建立各階段的狀態變量的轉移方程，寫出狀態轉移方程

六、編程實現

假設列出了狀態轉移方程：d(i, j) = a(i, j) + max{d(i + 1, j), d(i + 1, j + 1)}。

int d(int i, int j){

return a[i][j] + (i == n ? 0 : (d(i + 1, j) > d(i + 1, j + 1) ? d(i + 1, j) : d(i + 1, j + 1)));

}

遞歸方法的缺點是：效率比較低，首先在調用函數的嵌套時，函數不斷的切換，由此降低了效率。其次是相同的子問題被重複求解，例如:d(2, 3), d(4, 2), d(4, 3)就是被重複求解了兩次。

int i, j;

for(j = 1; j <= n; ++j)

d[n][j] = a[n][j];

for(i = n-1; i >= 1; --i)

for(j = 1; j <= i; ++j)

d[i][j] = a[i][j] + (d[i + 1][j] > d[i + 1][j + 1] ? d[i + 1][j] : d[i + 1][j + 1]);

遞推要注意邊界的處理。

首先設置一個數組，目的是保存已經計算好的子問題的解，下次再計算相同子問題時，就不用重複求解了，如下設置一個st數組用來保存計算好的子問題的解，初始化st所有元素為-1。

int d(int i, int j){

if(st[i][j] > 0)

return st[i][j];

return st[i][j] = a[i][j] + (i == n ? 0 : (d(i + 1, j) > d(i + 1, j + 1) ? d(i + 1, j) : d(i + 1, j + 1)));

}

記憶化搜索用的也是遞歸的方法，目的是把子問題的解保存下來，避免重複計算的情況，這是它比純遞歸更高效的原因。

記憶化搜索跟遞推相比，它的優點是:它不必事先確定好各狀態的計算順序，但使用遞推時必須事先確定好計算順序。