動态規劃——什麼是動态規劃？

先來看看《資訊學奧賽一本通第5版》是怎麼說的：

動态規劃程式設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。不像前面所述的那些搜尋或數值計算那樣，具有一個标準的數學表達式和明确清晰的解題方法。動态規劃程式設計往往是針對一種最優化問題，由于各種問題的性質不同，确定最優解的條件也互不相同，因而動态規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動态規劃算法，可以解決各類最優化問題。是以讀者在學習時，除了要對基本概念和方法正确了解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。我們也可以通過對若幹有代表性的問題的動态規劃算法進行分析、讨論，逐漸學會并掌握這一設計方法。

舉個栗子：

《資訊學奧賽一本通第5版》的例9.1:，題目是，最短路徑問題。下圖給出了一個地圖，地圖中的每個頂點代表一個城市，兩個城市間的一條連線代表道路，連線上的數值代表道路的長度。現在想從城市A到達城市E，怎樣走路程最短？最短路程的長度是多少？

圖：

，這是《資訊學奧賽一本通第5版》的解析：

【算法分析】

把A到E的全過程分成四個階段，用K表示階段變量，第1階段有一個初始狀态A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個初始狀态B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路……。用DK（XI，X+1J）表示在第K階段由初始狀态XI到下階段的初始狀态X+1J的路徑距離，FK（XI）表示從第K階段的XI到終點E的最短距離，利用倒推的方法，求解A到E的最短距離。 具體計算過程如下：

S1： K = 4 有

F4（D1）= 3，

F4（D2）= 4，

F4（D3）= 3；

S2： K = 3 有

F3（C1）= MIN{ D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2）}

= MIN{ 5+3，6+4 } = 8

F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8

F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11

F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6

S3： K = 2 有

F2（B1）= MIN{ D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2），

D2（B1，C3）+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9

F2（B2）= MIN{ D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4）}

= MIN{ 8+8，4+6 } = 10

S4： K = 1 有

F1（A）= MIN{ D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2）}

= MIN{ 5+9，3+10} = 13

是以由A點到E點的全過程最短路徑為A→B2→C4→D3→E；最短路程長度為13。

從以上過程可以看出，每個階段中，都求出本階段的各個初始狀态到終點E的最短距離，當逆序倒推到過程起點A時，便得到了全過程的最短路徑和最短距離。

在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關的，決策依賴于目前狀态，又随即引起狀态的轉移，一個決策序列就是在變化的狀态中産生出來的，故有“動态”的含義，我們稱這種解決多階段決策最優化的過程為動态規劃程式設計方法。

我的了解是，這題是一道求最優的題目，最短路徑目前已知比較普通的有：BFS，DFS，貪心，DP。BFS明顯是不行，因為每個變化的代價不一樣，DFS雖然是萬能的金鑰匙，但時間複雜度太高，不行。貪心就更不用說了，沒有局部最優導緻全局最優。是以，用DP，DP上面已經講得很詳細了。

然後是動态規劃的基本概念和基本模型構成 :

現在我們來介紹動态規劃的基本概念。

1. 階段和階段變量：

用動态規劃求解一個問題時，需要将問題的全過程恰當地分成若幹個互相聯系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示，階段的劃分一般是根據時間和空間的自然特征來劃分，同時階段的劃分要便于把問題轉化成多階段決策過程，如例題1中，可将其劃分成4個階段，即K = 1，2，3，4。

2. 狀态和狀态變量：

某一階段的出發位置稱為狀态，通常一個階段包含若幹狀态。一般地，狀态可由變量來描述，用來描述狀态的變量稱為狀态變量。如例題1中，C3是一個狀态變量。

3. 決策、決策變量和決策允許集合：

在對問題的進行中作出的每種選擇性的行動就是決策。即從該階段的每一個狀态出發，通過一次選擇性的行動轉移至下一階段的相應狀态。一個實際問題可能要有多次決策和多個決策點，在每一個階段的每一個狀态中都需要有一次決策，決策也可以用變量來描述，稱這種變量為決策變量。在實際問題中，決策變量的取值往往限制在某一個範圍之内，此範圍稱為允許決策集合。如例題1中，F3（C3）就是一個決策變量。

4．政策和最優政策：

所有階段依次排列構成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為政策。在實際問題中，從決策允許集合中找出最優效果的政策成為最優政策。

5. 狀态轉移方程

前一階段的終點就是後一階段的起點，對前一階段的狀态作出某種決策，産生後一階段的狀态，這種關系描述了由k階段到k+1階段狀态的演變規律，稱為狀态轉移方程。

我的見解是：DP（動态規劃）其實是一種進階貪心——用遞推做的貪心，遞推與DP最大的差別就在于遞推隻是單純的推，而DP是有選擇性的遞推。

然後是最優化原理與無後效性 ：

上面已經介紹了動态規劃模型的基本組成，現在需要解決的問題是：什麼樣的“多階段決策問題”才可以采用動态規劃的方法求解。

一般來說，能夠采用動态規劃方法求解的問題，必須滿足最優化原理和無後效性原則：

1、動态規劃的最優化原理。作為整個過程的最優政策具有：無論過去的狀态和決策如何，對前面的決策所形成的狀态而言，餘下的諸決策必須構成最優政策的性質。也可以通俗地了解為子問題的局部最優将導緻整個問題的全局最優，即問題具有最優子結構的性質，也就是說一個問題的最優解隻取決于其子問題的最優解，而非最優解對問題的求解沒有影響。在例題1最短路徑問題中，A到E的最優路徑上的任一點到終點E的路徑，也必然是該點到終點E的一條最優路徑，即整體優化可以分解為若幹個局部優化。

2、動态規劃的無後效性原則。所謂無後效性原則，指的是這樣一種性質：某階段的狀态一旦确定，則此後過程的演變不再受此前各狀态及決策的影響。也就是說，“未來與過去無關”，目前的狀态是此前曆史的一個完整的總結，此前的曆史隻能通過目前的狀态去影響過程未來的演變。在例題1最短路徑問題中，問題被劃分成各個階段之後，階段K中的狀态隻能由階段K+1中的狀态通過狀态轉移方程得來，與其它狀态沒有關系，特别與未發生的狀态沒有關系，例如從Ci到E的最短路徑，隻與Ci的位置有關，它是由Di中的狀态通過狀态轉移方程得來，與E狀态，特别是A到Ci的路徑選擇無關，這就是無後效性。

由此可見，對于不能劃分階段的問題，不能運用動态規劃來解；對于能劃分階段，但不符合最優化原理的，也不能用動态規劃來解；既能劃分階段，又符合最優化原理的，但不具備無後效性原則，還是不能用動态規劃來解；誤用動态規劃程式設計方法求解會導緻錯誤的結果。