動態規劃詳解 第一章首先讓我們看一個例子：
例1：如下圖有一個數字三角陣，請編一個程序計算從頂點至底的某處的一條路徑，使該路徑所經過的數字的和最大。每一步可沿左斜線向下或右斜線向下走。
7
5 3
4 2 1
2 1 3 7
這個問題的實質實際上是一個有向圖中最長路經問題，可以用經典的圖論算法或者搜索來解決。
考慮如何用搜索法來解這道題，從第一個點開始擴展，每次擴展2個可行節點，直到達到數字三角形的底部，從所有的可行路徑中找出最優值，這樣做的復雜度是o(2^n)，當n很大的時候，普通的搜索法將不可行。
觀察發現，搜索的效率低下很大程度上是因為做了大量的重復運算，因為對于任何一個節點，從他開始向下拓展的最優值是確定的，這啟發了我們應當充分利用之前的運算結果。
下面我們來進行深入的分析，假如已經走第I行第J列，此時最大累加和S[I，J]應選S[I-1，J]，S[I-1，J+1]中較大者再加上（I，J）處的值A[I，J]，即下式
S[I，J]=A[I，J]+MAX（S[I-1，J]，S[I-1，J+1]）
所以我們可以從第一行開始，向下逐行推出每一處位置的最大累加和S，最后從底行的N個S中選出最大的一個即為所求，這種算法的復雜度為o(n^2)，比較搜索法，已經大大的降低了，這種充分利用已經計算出結果的方法，就叫做動態規劃。
通過上面的例子，我們對“動態規劃”有了一個初步認識，它所處理的問題是一個“多階段決策問題”。我們現在對一些概念進行具體定義：
狀態（State）：它表示事物的性質，是描述“動態規劃”中的“單元”的量。如例1中的每個節點（指節點處的最大值）都為單個的狀態。
階段（Stage）：階段是一些性質相近，可以同時處理的狀態集合。通常，一個問題可以由處理的先后次序劃分為幾個階段。如例1中的問題，每一行若干節點組成一個階段。一個階段既可以包含多個狀態，也可以只包含一個狀態。描述各階段狀態的變量稱為狀態變量，例1中可用S[4 , j]來表示第四階段（即第四行）走到第j列的最大值，即第四階段狀態變量。
狀態轉移方程：是前一個階段的狀態轉移到后一個的狀態的演變規律，是關于兩個相鄰階段狀態的方程，是“動態規劃”的中心。
如例1中： S[I，J]=A[I，J]+MAX（S[I-1，J]，S[I-1，J+1]）
決策（Decision）：每個階段做出的某種選擇性的行動。它是我們程序所需要完成的選擇。如例1中MAX（S[I-1，J]，S[I-1，J+1]）
動態規劃所處理的問題是一個“多階段決策問題”，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線（通常是求最優的活動路線）
從上面的講解我們可以發現：動態規劃并不像一種算法，而更像一種思考方式。
下面，我們來討論動態規劃的應用范圍，要確定一個問題是否能用動態規劃，需要考慮兩個方面：
一：最優子結構
即一個問題的最優解只取決于其子問題的最優解，也就是說，非最優解對問題的求解沒有影響。我們再來看一個問題：
例二：有4個點，分別是A、B、C、D，相鄰兩點用兩條連線，表示兩條通行的道路，給出每條道路的長度。我們定義從A到D的所有路徑中，長度除以4所得余數最小的路徑為最優路徑。求一條最優路徑。
很多初學者往往會認為這道題也可以采用動態規劃的方法，但實際并不如此，考慮這種情況
假如A-B的兩條道路分別為2，3,B-C的兩條道路分別為1，4。如果采用動態規劃，節點B的最優值為2，節點C的最優值2，但際上到達C的最優值應該是0，即3-1這條線路。
也就是說，C的最優取值不是由B的最優取值決定的，其不具有最優子結構。
由此可見，并不是所有的“決策問題”都可以用“動態規劃”來解決。所以，只有當一個問題呈現出最優子結構時，“動態規劃”才可能是一個合適的侯選方法。
二：無后效性
即一個問題被劃分階段后，階段I中的狀態只能由階段I-1中的狀態通過狀態轉移方程得來，與其他狀態沒有關系，特別是與未發生的狀態沒有關系，這就是無后效性。
<<<<<<<<<<<<<<<<<<<END>>>>>>>>>>>>>>>>>>
