動態規劃演算法三步解決

A. 關於動態規劃演算法，哪位可以講一下自己心得體會

動態規劃的特點及其應用
安徽 張辰
動態規劃 階段

動態規劃是信息學競賽中的常見演算法，本文的主要內容就是分析它的特點。
文章的第一部分首先探究了動態規劃的本質，因為動態規劃的特點是由它的本質所決定的。第二部分從動態規劃的設計和實現這兩個角度分析了動態規劃的多樣性、模式性、技巧性這三個特點。第三部分將動態規劃和遞推、搜索、網路流這三個相關演算法作了比較，從中探尋動態規劃的一些更深層次的特點。
文章在分析動態規劃的特點的同時，還根據這些特點分析了我們在解題中應該怎樣利用這些特點，怎樣運用動態規劃。這對我們的解題實踐有一定的指導意義。

動態規劃是編程解題的一種重要的手段，在如今的信息學競賽中被應用得越來越普遍。最近幾年的信息學競賽，不分大小，幾乎每次都要考察到這方面的內容。因此，如何更深入地了解動態規劃，從而更為有效地運用這個解題的有力武器，是一個值得深入研究的問題。
要掌握動態規劃的應用技巧，就要了解它的各方面的特點。首要的，是要深入洞悉動態規劃的本質。
§1動態規劃的本質
動態規劃是在本世紀50年代初，為了解決一類多階段決策問題而誕生的。那麼，什麼樣的問題被稱作多階段決策問題呢？
§1.1多階段決策問題
說到多階段決策問題，人們很容易舉出下面這個例子。
[例1] 多段圖中的最短路徑問題：在下圖中找出從A1到D1的最短路徑。
仔細觀察這個圖不難發現，它有一個特點。我們將圖中的點分為四類（圖中的A、B、C、D），那麼圖中所有的邊都處於相鄰的兩類點之間，並且都從前一類點指向後一類點。這樣，圖中的邊就被分成了三類（AàB、BàC、CàD）。我們需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，並且這條路徑是所有這樣的路徑中的最短者。
從上面的這個例子中，我們可以大概地了解到什麼是多階段決策問題。更精確的定義如下：
多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列[1]。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
從上述的定義中，我們可以明顯地看出，這類問題有兩個要素。一個是階段，一個是決策。
§1.2階段與狀態
階段：將所給問題的過程，按時間或空間特徵分解成若干相互聯系的階段，以便按次序去求每階段的解。常用字母k表示階段變數。[1]
階段是問題的屬性。多階段決策問題中通常存在著若干個階段，如上面的例子，就有A、B、C、D這四個階段。在一般情況下，階段是和時間有關的；但是在很多問題（我的感覺，特別是信息學問題）中，階段和時間是無關的。從階段的定義中，可以看出階段的兩個特點，一是「相互聯系」，二是「次序」。
階段之間是怎樣相互聯系的？就是通過狀態和狀態轉移。
狀態：各階段開始時的客觀條件叫做狀態。描述各階段狀態的變數稱為狀態變數，常用sk表示第k階段的狀態變數，狀態變數sk的取值集合稱為狀態集合，用Sk表示。[1]
狀態是階段的屬性。每個階段通常包含若干個狀態，用以描述問題發展到這個階段時所處在的一種客觀情況。在上面的例子中，行人從出發點A1走過兩個階段之後，可能出現的情況有三種，即處於C1、C2或C3點。那麼第三個階段就有三個狀態S3=。
每個階段的狀態都是由以前階段的狀態以某種方式「變化」而來，這種「變化」稱為狀態轉移（暫不定義）。上例中C3點可以從B1點過來，也可以從B2點過來，從階段2的B1或B2狀態走到階段3的C3狀態就是狀態轉移。狀態轉移是導出狀態的途徑，也是聯系各階段的途徑。
說到這里，可以提出應用動態規劃的一個重要條件。那就是將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的發展，而只能通過當前的這個狀態。換句話說，每個狀態都是「過去歷史的一個完整總結[1]」。這就是無後效性。對這個性質，下文還將會有解釋。
§1.3決策和策略
上面的階段與狀態只是多階段決策問題的一個方面的要素，下面是另一個方面的要素——決策。
決策：當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。表示決策的變數，稱為決策變數，常用uk(sk)表示第k階段當狀態為sk時的決策變數。在實際問題中，決策變數的取值往往限制在一定范圍內，我們稱此范圍為允許決策集合。常用Dk(sk)表示第k階段從狀態sk出發的允許決策集合。顯然有uk(sk) ?Dk(sk)。[1]
決策是問題的解的屬性。決策的目的就是「確定下一階段的狀態」，還是回到上例，從階段2的B1狀態出發有三條路，也就是三個決策，分別導向階段3的C1、C2、C3三個狀態，即D2(B1)=。
有了決策，我們可以定義狀態轉移：動態規劃中本階段的狀態往往是上一階段和上一階段的決策結果，由第k段的狀態sk和本階段的決策uk確定第k+1段的狀態sk+1的過程叫狀態轉移。狀態轉移規律的形式化表示sk+1=Tk(sk,uk)稱為狀態轉移方程。
這樣看來，似乎決策和狀態轉移有著某種聯系。我的理解，狀態轉移是決策的目的，決策是狀態轉移的途徑。
各段決策確定後，整個問題的決策序列就構成一個策略，用p1,n=表示。對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最有效果的策略就是最優策略。[1]
說到這里，又可以提出運用動態規劃的一個前提。即這個過程的最優策略應具有這樣的性質：無論初始狀態及初始決策如何，對於先前決策所形成的狀態而言，其以後的所有決策應構成最優策略[1]。這就是最優化原理。簡言之，就是「最優策略的子策略也是最優策略」。
§1.4最優化原理與無後效性
這里，我把最優化原理定位在「運用動態規劃的前提」。這是因為，是否符合最優化原理是一個問題的本質特徵。對於不滿足最優化原理的一個多階段決策問題，整體上的最優策略p1,n同任何一個階段k上的決策uk或任何一組階段k1…k2上的子策略pk1,k2都不存在任何關系。如果要對這樣的問題動態規劃的話，我們從一開始所作的劃分階段等努力都將是徒勞的。
而我把無後效性定位在「應用動態規劃的條件」，是因為動態規劃是按次序去求每階段的解，如果一個問題有後效性，那麼這樣的次序便是不合理的。但是，我們可以通過重新劃分階段，重新選定狀態，或者增加狀態變數的個數等手段，來是問題滿足無後效性這個條件。說到底，還是要確定一個「序」。
在信息學的多階段決策問題中，絕大部分都是能夠滿足最優化原理的，但它們往往會在後效性這一點上來設置障礙。所以在解題過程中，我們會特別關心「序」。對於有序的問題，就會考慮到動態規劃；對於無序的問題，也會想方設法來使其有序。
§1.5最優指標函數和規劃方程
最優指標函數：用於衡量所選定策略優劣的數量指標稱為指標函數，最優指標函數記為fk(sk)，它表示從第k段狀態sk採用最優策略p*k,n到過程終止時的最佳效益值[1]。
最優指標函數其實就是我們真正關心的問題的解。在上面的例子中，f2(B1)就表示從B1點到終點D1點的最短路徑長度。我們求解的最終目標就是f1(A1)。
最優指標函數的求法一般是一個從目標狀態出發的遞推公式，稱為規劃方程：

其中sk是第k段的某個狀態，uk是從sk出發的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態sk+1，g(x,uk)是定義在數值x和決策uk上的一個函數，而函數opt表示最優化，根據具體問題分別表為max或min。
，稱為邊界條件。
上例中的規劃方程就是：

邊界條件為
這里是一種從目標狀態往回推的逆序求法，適用於目標狀態確定的問題。在我們的信息學問題中，也有很多有著確定的初始狀態。當然，對於初始狀態確定的問題，我們也可以採用從初始狀態出發往前推的順序求法。事實上，這種方法對我們來說要更為直觀、更易設計一些，從而更多地出現在我們的解題過程中。
我們本節所討論的這些理論雖然不是本文的主旨，但是卻對下面要說的動態規劃的特點起著基礎性的作用。
§2動態規劃的設計與實現
上面我們討論了動態規劃的一些理論，本節我們將通過幾個例子中，動態規劃的設計與實現，來了解動態規劃的一些特點。
§2.1動態規劃的多樣性
[例2] 花店櫥窗布置問題（IOI99）試題見附錄
本題雖然是本屆IOI中較為簡單的一題，但其中大有文章可作。說它簡單，是因為它有序，因此我們一眼便可看出這題應該用動態規劃來解決。但是，如何動態規劃呢？如何劃分階段，又如何選擇狀態呢？
<方法1>以花束的數目來劃分階段。在這里，階段變數k表示的就是要布置的花束數目（前k束花），狀態變數sk表示第k束花所在的花瓶。而對於每一個狀態sk，決策就是第k-1束花應該放在哪個花瓶，用uk表示。最優指標函數fk(sk)表示前k束花，其中第k束插在第sk個花瓶中，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
（其中A(i,j)是花束i插在花瓶j中的美學值）
邊界條件 （V是花瓶總數，事實上這是一個虛擬的邊界）
<方法2>以花瓶的數目來劃分階段。在這里階段變數k表示的是要佔用的花瓶數目（前k個花瓶），狀態變數sk表示前k個花瓶中放了多少花。而對於任意一個狀態sk，決策就是第sk束花是否放在第k個花瓶中，用變數uk=1或0來表示。最優指標函數fk(sk)表示前k個花瓶中插了sk束花，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
邊界條件為
兩種劃分階段的方法，引出了兩種狀態表示法，兩種規劃方式，但是卻都成功地解決了問題。只不過因為決策的選擇有多有少，所以演算法的時間復雜度也就不同。[2]
這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規劃方法。有時各種方法所產生的效果是差不多的，但更多的時候，就像我們的例子一樣，兩種方法會在某個方面有些區別。
所以，在用動態規劃解題的時候，可以多想一想是否有其它的解法。對於不同的解法，要注意比較，好的演算法好在哪裡，差一點的演算法差在哪裡。從各種不同演算法的比較中，我們可以更深刻地領會動態規劃的構思技巧。
§2.2動態規劃的模式性
這個可能做過動態規劃的人都有體會，從我們上面對動態規劃的分析也可以看出來。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的，否則問題就無法求解。
選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
確定決策並寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。
寫出規劃方程（包括邊界條件）：在第一部分中，我們已經給出了規劃方程的通用形式化表達式。一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。
動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。大體上的框架如下：
對f1(s1)初始化（邊界條件）
for k?2 to n（這里以順序求解為例）
對每一個sk?Sk
fk(sk)?一個極值（∞或－∞）
對每一個uk(sk)?Dk(sk)
sk-1?Tk(sk,uk)
t?g(fk-1(sk-1),uk)
y t比fk(sk)更優 n
fk(sk)?t
輸出fn(sn)
這個N-S圖雖然不能代表全部，但足可以概括大多數。少數的一些特殊的動態規劃，其實現的原理也是類似，可以類比出來。我們到現在對動態規劃的分析，主要是在理論上、設計上，原因也就在此。
掌握了動態規劃的模式性，我們在用動態規劃解題時就可以把主要的精力放在理論上的設計。一旦設計成熟，問題也就基本上解決了。而且在設計演算法時也可以按部就班地來。
但是「物極必反」，太過拘泥於模式就會限制我們的思維，扼殺優良演算法思想的產生。我們在解題時，不妨發揮一下創造性，去突破動態規劃的實現模式，這樣往往會收到意想不到的效果。[3]
§2.3動態規劃的技巧性
上面我們所說的動態規劃的模式性，主要指的是實現方面。而在設計方面，雖然它較為嚴格的步驟性，但是它的設計思想卻是沒有一定的規律可循的。這就需要我們不斷地在實踐當中去掌握動態規劃的技巧，下面僅就一個例子談一點我自己的體會。
[例3] 街道問題：在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。
這是一道簡單而又典型的動態規劃題，許多介紹動態規劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：

按照圖中的虛線來劃分階段，即階段變數k表示走過的步數，而狀態變數sk表示當前處於這一階段上的哪一點（各點所對應的階段和狀態已經用ks在地圖上標明）。這時的模型實際上已經轉化成了一個特殊的多段圖。用決策變數uk=0表示向右走，uk=1表示向上走，則狀態轉移方程如下：

（這里的row是地圖豎直方向的行數）
我們看到，這個狀態轉移方程需要根據k的取值分兩種情況討論，顯得非常麻煩。相應的，把它代入規劃方程而付諸實現時，演算法也很繁。因而我們在實現時，一般是不會這么做的，而代之以下面方法：
將地圖中的點規則地編號如上，得到的規劃方程如下：

（這里Distance表示相鄰兩點間的邊長）
這樣做確實要比上面的方法簡單多了，但是它已經破壞了動態規劃的本來面目，而不存在明確的階段特徵了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那麼它的「狀態轉移」就不全是在兩個階段之間進行的了。
也許這沒什麼大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，並且要求兩條路徑的總長度最短。這時，再用這種「簡單」的方法就不太好辦了。
如果非得套用這種方法的話，則最優指標函數就需要有四維的下標，並且難以處理兩條路徑「不能重疊」的問題。
而我們回到原先「標准」的動態規劃法，就會發現這個問題很好解決，只需要加一維狀態變數就成了。即用sk=(ak,bk)分別表示兩條路徑走到階段k時所處的位置，相應的，決策變數也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態轉移時將兩條路徑分別考慮：

在寫規劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數：

從這個例子中可以總結出設計動態規劃演算法的一個技巧：狀態轉移一般是在相鄰的兩個階段之間（有時也可以在不相鄰的兩個階段間），但是盡量不要在同一個階段內進行。
動態規劃是一種很靈活的解題方法，在動態規劃演算法的設計中，類似的技巧還有很多。要掌握動態規劃的技巧，有兩條途徑：一是要深刻理解動態規劃的本質，這也是我們為什麼一開始就探討它的本質的原因；二是要多實踐，不但要多解題，還要學會從解題中探尋規律，總結技巧。
§3動態規劃與一些演算法的比較
動態規劃作為諸多解題方法中的一種，必然和其他一些演算法有著諸多聯系。從這些聯系中，我們也可以看出動態規劃的一些特點。
§3.1動態規劃與遞推
——動態規劃是最優化演算法
由於動態規劃的「名氣」如此之大，以至於很多人甚至一些資料書上都往往把一種與動態規劃十分相似的演算法，當作是動態規劃。這種演算法就是遞推。實際上，這兩種演算法還是很容易區分的。
按解題的目標來分，信息學試題主要分四類：判定性問題、構造性問題、計數問題和最優化問題。我們在競賽中碰到的大多是最優化問題，而動態規劃正是解決最優化問題的有力武器，因此動態規劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態規劃在這兩個方面的聯系。
[例4] mod 4 最優路徑問題：在下圖中找出從第1點到第4點的一條路徑，要求路徑長度mod 4的余數最小。
這個圖是一個多段圖，而且是一個特殊的多段圖。雖然這個圖的形式比一般的多段圖要簡單，但是這個最優路徑問題卻不能用動態規劃來做。因為一條從第1點到第4點的最優路徑，在它走到第2點、第3點時，路徑長度mod 4的余數不一定是最小，也就是說最優策略的子策略不一定最優——這個問題不滿足最優化原理。
但是我們可以把它轉換成判定性問題，用遞推法來解決。判斷從第1點到第k點的長度mod 4為sk的路徑是否存在，用fk(sk)來表示，則遞推公式如下：
（邊界條件）

（這里lenk,i表示從第k-1點到第k點之間的第i條邊的長度，方括弧表示「或(or)」運算）
最後的結果就是可以使f4(s4)值為真的最小的s4值。
這個遞推法的遞推公式和動態規劃的規劃方程非常相似，我們在這里借用了動態規劃的符號也就是為了更清楚地顯示這一點。其實它們的思想也是非常相像的，可以說是遞推法借用了動態規劃的思想解決了動態規劃不能解決的問題。
有的多階段決策問題（像這一題的階段特徵就很明顯），由於不能滿足最優化原理等使用動態規劃的先決條件，而無法應用動態規劃。在這時可以將最優指標函數的值當作「狀態」放到下標中去，從而變最優化問題為判定性問題，再借用動態規劃的思想，用遞推法來解決問題。
§3.2動態規劃與搜索
——動態規劃是高效率、高消費演算法
同樣是解決最優化問題，有的題目我們採用動態規劃，而有的題目我們則需要用搜索。這其中有沒有什麼規則呢？
我們知道，撇開時空效率的因素不談，在解決最優化問題的演算法中，搜索可以說是「萬能」的。所以動態規劃可以解決的問題，搜索也一定可以解決。
把一個動態規劃演算法改寫成搜索是非常方便的，狀態轉移方程、規劃方程以及邊界條件都可以直接「移植」，所不同的只是求解順序。動態規劃是自底向上的遞推求解，而搜索則是自頂向下的遞歸求解（這里指深度搜索，寬度搜索類似）。
反過來，我們也可以把搜索演算法改寫成動態規劃。狀態空間搜索實際上是對隱式圖中的點進行枚舉，這種枚舉是自頂向下的。如果把枚舉的順序反過來，變成自底向上，那麼就成了動態規劃。（當然這里有個條件，即隱式圖中的點是可排序的，詳見下一節。）
正因為動態規劃和搜索有著求解順序上的不同，這也造成了它們時間效率上的差別。在搜索中，往往會出現下面的情況：
對於上圖(a)這樣幾個狀態構成的一個隱式圖，用搜索演算法就會出現重復，如上圖(b)所示，狀態C2被搜索了兩次。在深度搜索中，這樣的重復會引起以C2為根整個的整個子搜索樹的重復搜索；在寬度搜索中，雖然這樣的重復可以立即被排除，但是其時間代價也是不小的。而動態規劃就沒有這個問題，如上圖(c)所示。
一般說來，動態規劃演算法在時間效率上的優勢是搜索無法比擬的。（當然對於某些題目，根本不會出現狀態的重復，這樣搜索和動態規劃的速度就沒有差別了。）而從理論上講，任何拓撲有序（現實中這個條件常常可以滿足）的隱式圖中的搜索演算法都可以改寫成動態規劃。但事實上，在很多情況下我們仍然不得不採用搜索演算法。那麼，動態規劃演算法在實現上還有什麼障礙嗎？
考慮上圖(a)所示的隱式圖，其中存在兩個從初始狀態無法達到的狀態。在搜索演算法中，這樣的兩個狀態就不被考慮了，如上圖(b)所示。但是動態規劃由於是自底向上求解，所以就無法估計到這一點，因而遍歷了全部的狀態，如上圖(c)所示。
一般說來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的事搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。
如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化演算法。記憶化演算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。
§3.3動態規劃與網路流
——動態規劃是易設計易實現演算法
由於圖的關系復雜而無序，一般難以呈現階段特徵（除了特殊的圖如多段圖，或特殊的分段方法如Floyd），因此動態規劃在圖論中的應用不多。但有一類圖，它的點卻是有序的，這就是有向無環圖。
在有向無環圖中，我們可以對點進行拓撲排序，使其體現出有序的特徵，從而據此劃分階段。在有向無還圖中求最短路徑的演算法[4]，已經體現出了簡單的動態規劃思想。但動態規劃在圖論中還有更有價值的應用。下面先看一個例子。
[例6] N個人的街道問題：在街道問題（參見例3）中，若有N個人要從左下角走向右上角，要求他們走過的邊的總長度最大。當然，這里每個人也只能向右或向上走。下面是一個樣例，左圖是從出發地到目的地的三條路徑，右圖是他們所走過的邊，這些邊的總長度為5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
這個題目是對街道問題的又一次擴展。仿照街道問題的解題方法，我們仍然可以用動態規劃來解決本題。不過這一次是N個人同時走，狀態變數也就需要用N維來表示，。相應的，決策變數也要變成N維，uk=(uk,1,uk,2,…,uk,N)。狀態轉移方程不需要做什麼改動：

在寫規劃方程時，需要注意在第k階段，N條路徑所走過的邊的總長度的計算，在這里我就用gk(sk,uk)來表示了：

邊界條件為
可見將原來的動態規劃演算法移植到這個問題上來，在理論上還是完全可行的。但是，現在的這個動態規劃演算法的時空復雜度已經是關於N的指數函數，只要N稍微大一點，這個演算法就不可能實現了。
下面我們換一個思路，將N條路徑看成是網路中一個流量為N的流，這樣求解的目標就是使這個流的費用最大。但是本題又不同於一般的費用流問題，在每一條邊e上的流費用並不是流量和邊權的乘積 ，而是用下式計算：

為了使經典的費用流演算法適用於本題，我們需要將模型稍微轉化一下：
如圖，將每條邊拆成兩條。拆開後一條邊上有權，但是容量限制為1；另一條邊沒有容量限制，但是流過這條邊就不能計算費用了。這樣我們就把問題轉化成了一個標準的最大費用固定流問題。
這個演算法可以套用經典的最小費用最大流演算法，在此就不細說了。（參見附錄中的源程序）
這個例題是我仿照IOI97的「障礙物探測器」一題[6]編出來的。「障礙物探測器」比這一題要復雜一些，但是基本思想是相似的。類似的題目還有99年冬令營的「迷宮改造」[7]。從這些題目中都可以看到動態規劃和網路流的聯系。
推廣到一般情況，任何有向無環圖中的費用流問題在理論上說，都可以用動態規劃來解決。對於流量為N（如果流量不固定，這個N需要事先求出來）的費用流問題，用N維的變數sk=(sk,1,sk,2,…,sk,N)來描述狀態，其中sk,i?V(1￡i￡N)。相應的，決策也用N維的變數uk=(uk,1,uk,2,…,uk,N)來表示，其中uk,i?E(sk,i)(1￡i￡N)，E(v)表示指向v的弧集。則狀態轉移方程可以這樣表示：
sk-1,i = uk,i的弧尾結點
規劃方程為
邊界條件為
但是，由於動態規劃演算法是指數級演算法，因而在實現中的局限性很大，僅可用於一些N非常小的題目。然而在競賽解題中，比如上面說到的IOI97以及99冬令營測試時，我們使用動態規劃的傾向性很明顯（「障礙物探測器」中，我們用的是貪心策略，求N=1或N=2時的局部最優解[8]）。這主要有兩個原因：
一． 雖然網路流有著經典的演算法，但是在競賽中不可能出現經典的問題。如果要運用網路流演算法，則需要經過一番模型轉化，有時這個轉化還是相當困難的。因此在演算法的設計上，靈活巧妙的動態規劃演算法反而要更為簡單一些。
二． 網路流演算法實現起來很繁，這是被人們公認的。因而在競賽的緊張環境中，實現起來有一定模式的動態規劃演算法又多了一層優勢。
正由於動態規劃演算法在設計和實現上的簡便性，所以在N不太大時，也就是在動態規劃可行的情況下，我們還是應該盡量運用動態規劃。
§4結語
本文的內容比較雜，是我幾年來對動態規劃的參悟理解、心得體會。雖然主要的篇幅講的都是理論，但是根本的目的還是指導實踐。
動態規劃，據我認為，是當今信息學競賽中最靈活、也最能體現解題者水平的一類解題方法。本文內容雖多，不能涵蓋動態規劃之萬一。「紙上得來終覺淺，絕知此事要躬行。」要想真正領悟、理解動態規劃的思想，掌握動態規劃的解題技巧，還需要在實踐中不斷地挖掘、探索。實踐得多了，也就能體會到漸入佳境之妙了。
動態規劃，
演算法之常，
運用之妙，
存乎一心。

B. 動態規劃演算法詳解

動態規劃一般也只能應用於有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解(對有些問題這個要求並不能完全滿足，故有時需要引入一定的近似)。簡單地說，問題能夠分解成子問題來解決。

將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解（這部分與分治法相似）。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到的子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。通常可以用一個表來記錄所有已解的子問題的答案。

問題的一個最優解中所包含的子問題的解也是最優的。總問題包含很多個子問題，而這些子問題的解也是最優的。

用遞歸演算法對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。

：很顯然，這道題的對應的數學表達式是

其中F(1)=1, F(2)=2。很自然的狀況是，採用遞歸函數來求解：

參考：
http://blog.csdn.net/zmazon/article/details/8247015
http://blog.csdn.net/lisonglisonglisong/article/details/41548557
http://blog.csdn.net/v_JULY_v/article/details/6110269
http://blog.csdn.net/trochiluses/article/details/37966729

C. 動態規劃的推法 謝謝

DP是把一個很大的有階段性有最佳答案問題分割成許多子問題，每個子問題有自己的最優情況（最優子結構），也就是說，每個動態規劃的問題都是有許多最有子結構接和起來的，而推法就是要分割出最有子結構
然後對這個小問題得出最優的答案，並由此推出全局的最優解

1.最優子結構性質；

設Q[i,j]表示第i顆珠子到第j顆珠子合並所產生的能量。顯然Q[1,n]表示的是合並產生的總的能量。給定一種標號方法，maxQ[1,n]就是所要求的。設最後一次合並在k處進行，則有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
證明：假設Q[1,k]不是最大，則必然存在一Q'[1,k]>Q[1,k]。那麼就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。這與Q[1,n]的最優性矛盾

能量項鏈其實就是石子合並

演算法分析
競賽中多數選手都不約而同地採用了盡可能逼近目標的貪心法來逐次合並：從最上面
的一堆開始，沿順時針方向排成一個序列。 第一次選得分最小（最大）的相鄰兩堆合並，
形成新的一堆；接下來，在N－1堆中選得分最小（最大）的相鄰兩堆合並……，依次類推，
直至所有石子經N－1次合並後形成一堆。

例如有6堆石子，每堆石子數（從最上面一堆數起，順時針數）依次為3 46 5
4 2

（圖6.2-5）
要求選擇一種合並石子的方案，使得做5次合並，得分的總和最小。
按照貪心法，合並的過程如下：
每次合並得分
第一次合並 3 4 6 5 4 2 5
第二次合並 5 4 6 5 4 9
第三次合並 9 6 5 4 9
第四次合並 9 6 9 15
第五次合並 15 9 24
24
總得分＝5＋9＋9＋15＋24＝62

但是當我們仔細琢磨後，可得出另一個合並石子的方案：
每次合並得分
第一次合並 3 4 6 5 4 2 7
第二次合並 7 6 5 4 2 13
第三次合並 13 5 4 2 6
第四次合並 13 5 6 11
第五次合並 13 11 24
24
總得分＝7＋6＋11＋13＋24＝61
顯然，後者比貪心法得出的合並方案更優。 題目中的示例故意造成一個貪心法解題的
假像，誘使讀者進入「陷阱」。為了幫助讀者從這個「陷阱」里走出來， 我們先來明確一
個問題：

1．最佳合並過程符合最佳原理
使用貪心法至所以可能出錯， 是因為每一次選擇得分最小（最大）的相鄰兩堆合並，
不一定保證餘下的合並過程能導致最優解。聰明的讀者馬上會想到一種理想的假設：如果N
－1次合並的全局最優解包含了每一次合並的子問題的最優解，那麼經這樣的N－1次合並後
的得分總和必然是最優的。
例如上例中第五次合並石子數分別為13和11的相鄰兩堆。 這兩堆石頭分別由最初
的第1，2，3堆（石頭數分別為3，4，6）和第4，5，6堆（石頭數分別為5，4，
2）經4次合並後形成的。於是問題又歸結為如何使得這兩個子序列的N－2 次合並的得分
總和最優。為了實現這一目標，我們將第1個序列又一分為二：第1、2堆構成子序列1，
第3堆為子序列2。第一次合並子序列1中的兩堆，得分7； 第二次再將之與子序列2的
一堆合並，得分13。顯然對於第1個子序列來說，這樣的合並方案是最優的。同樣，我
們將第2個子序列也一分為二；第4堆為子序列1，第5，6堆構成子序列2。第三次合
並子序列2中的2堆，得分6；第四次再將之與子序列1中的一堆合並，得分13。顯然
對於第二個子序列來說，這樣的合並方案也是最優的。 由此得出一個結論——6堆石子經
過這樣的5次合並後，得分的總和最小。
我們把每一次合並劃分為階段，當前階段中計算出的得分和作為狀態， 如何在前一次
合並的基礎上定義一個能使目前得分總和最大的合並方案作為一次決策。很顯然，某階段
的狀態給定後，則以後各階段的決策不受這階段以前各段狀態的影響。 這種無後效性的性
質符最佳原理，因此可以用動態規劃的演算法求解。

2．動態規劃的方向和初值的設定
採用動態規劃求解的關鍵是確定所有石子堆子序列的最佳合並方案。 這些石子堆子序
列包括：
｛第1堆、第2堆｝、｛第2堆、第3堆｝、……、｛第N堆、第1堆｝；
｛第1堆、第2堆、第3堆｝、｛第2堆、第3堆、第4堆｝、……、｛第N堆、第1
堆、第2堆｝；
……
｛第1堆、……、第N堆｝｛第1堆、……、第N堆、第1堆｝……｛第N堆、第1堆、
……、第N－1堆｝

為了便於運算，我們用〔i，j〕表示一個從第i堆數起，順時針數j堆時的子序列
｛第i堆、第i＋1堆、……、第（i＋j－1）mod n堆｝
它的最佳合並方案包括兩個信息：
①在該子序列的各堆石子合並成一堆的過程中，各次合並得分的總和；
②形成最佳得分和的子序列1和子序列2。由於兩個子序列是相鄰的， 因此只需記住
子序列1的堆數；
設
f〔i，j〕——將子序列〔i，j〕中的j堆石子合並成一堆的最佳得分和；
c〔i，j〕——將〔i，j〕一分為二，其中子序列1的堆數；
（1≤i≤N，1≤j≤N）
顯然，對每一堆石子來說，它的
f〔i，1〕＝0 c〔i，1〕＝0 （1≤i≤N）
對於子序列〔i，j〕來說，若求最小得分總和，f〔i，j〕的初始值為∞； 若求最大得
分總和，f〔i，j〕的初始值為0。（1≤i≤N，2≤j≤N）。
規劃的方向是順推。先考慮含二堆石子的N個子序列（各子序列分別從第1堆、第2堆、
……、第N堆數起，順時針數2堆）的合並方案
f〔1，2〕，f〔2，2〕，……，f〔N，2〕
c〔1，2〕，c〔2，2〕，……，c〔N，2〕

然後考慮含三堆石子的N個子序列（各子序列分別從第1堆、第2堆、……、第N堆
數起，順時針數3堆）的合並方案
f〔1，3〕，f〔2，3〕，……，f〔N，3〕
c〔1，3〕，c〔2，3〕，……，c〔N，3〕
……

依次類推，直至考慮了含N堆石子的N個子序列（各子序列分別從第1堆、第2堆、 …
…、第N堆數起，順時針數N堆）的合並方案
f〔1，N〕，f〔2，N〕，……，f〔N，N〕
c〔1，N〕，c〔2，N〕，……，c〔N，N〕

最後，在子序列〔1，N〕，〔2，N〕，……，〔N，N〕中，選擇得分總和（f值）最
小（或最大）的一個子序列〔i，N〕（1≤i≤N），由此出發倒推合並過程。

3．動態規劃方程和倒推合並過程
對子序列〔i，j〕最後一次合並，其得分為第i堆數起，順時針數j堆的石子總數t。被
合並的兩堆石子是由子序列〔i，k〕和〔（i＋k－1）modn＋1，j－k〕（1≤k≤j－1）
經有限次合並形成的。為了求出最佳合並方案中的k值，我們定義一個動態規劃方程：
當求最大得分總和時
f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）

當求最小得分總和時
f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝
1≤k≤j－1
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（2≤j≤n，1≤i≤n）
其中x＝（i＋k－1）modn＋1，即第i堆數起，順時針數k＋1堆的堆序號。

例如對（圖6．2－4）中的6堆石子，按動態規劃方程順推最小得分和。 依次得出含
二堆石子的6個子序列的合並方案
f〔1，2〕＝7 f〔2，2〕＝10 f〔3 ，2〕＝11
c〔1，2〕＝1 c〔2，2〕＝1 c〔3，2〕＝1
f〔4，2〕＝9 f〔5，2〕＝6 f〔6，2〕＝5
c〔4，2〕＝1 c〔5， 2〕＝1 c〔6，2〕＝1

含三堆石子的6個子序列的合並方案
f〔1，3〕＝20 f〔2，3〕＝25 f〔3，3〕＝24
c〔1，3〕＝2 c〔2，3〕＝2 c〔3，3〕＝1
f〔4，3〕＝17 f〔5，3〕＝14 f〔6，3〕＝14
c〔4，3〕＝1 c〔5，3〕＝1 c〔6，3〕＝2

含四堆石子的6個子序列的合並方案
f〔1，4〕＝36 f〔2，4〕＝38 f〔3，4〕＝34
c〔1，4〕＝2 c〔2，4〕＝2 c〔3，4〕＝1
f〔4，4〕＝28 f〔5，4〕＝26 f〔6，4〕＝29
c〔4，4〕＝1 c〔5，4〕＝2 c〔6，4〕＝3

含五堆石子的6個子序列的合並方案
f〔1，5〕＝51 f〔2，5〕＝48 f〔3，5〕＝45
c〔1，5〕＝3 c〔2，5〕＝2 c〔3，5〕＝2
f〔4，5〕＝41 f〔5，5〕＝43 f〔6，5〕＝45
c〔4，5〕＝2 c〔5，5〕＝3 c〔6，5〕＝3

含六堆石子的6個子序列的合並方案
f〔1，6〕＝61 f〔2，6〕＝62 f〔3，6〕＝61
c〔1，6〕＝3 c〔2，6〕＝2 c〔3，6〕＝2
f〔4，6〕＝61 f〔5，6〕＝61 f〔6，6〕＝62
c〔4，6〕＝3 c〔5，6〕＝4 c〔6，6〕＝3

f〔1，6〕是f〔1，6〕，f〔2，6〕，……f〔6，6〕中的最小值，表明最小
得分和是由序列〔1，6〕經5次合並得出的。我們從這個序列出發， 按下述方法倒推合
並過程：
由c〔1，6〕＝3可知，第5次合並的兩堆石子分別由子序列〔1，3〕和子序列〔
4，3〕經4次合並後得出。其中
c〔1，3〕＝2可知由子序列〔1，3〕合並成的一堆石子是由子序列〔1，2〕和
第三堆合並而來的。而c〔1，2〕＝1，以表明了子序列〔1，2〕的合並方案是第1堆
合並第2堆。
由此倒推回去，得出第1，第2次合並的方案
每次合並得分
第一次合並 3 4 6…… 7
第二次合並 7 6…… 13
13……
子序列〔1，3〕經2次合並後合並成1堆， 2次合並的得分和＝7＋13＝20。
c〔4，3〕＝1，可知由子序列〔4，3〕合並成的一堆石子是由第4堆和子序列〔5，
2〕合並而來的。而c〔5，2〕＝1，又表明了子序列〔5，2〕的合並方案是第5堆合
並第6堆。由此倒推回去，得出第3、第4次合並的方案
每次合並得分
第三次合並 ……54 2 6
第四次合並 ……5 6 11
……11
子序列〔4，3〕經2次合並後合並成1堆，2次合並的得分和＝6＋11＝17。
第五次合並是將最後兩堆合並成1堆，該次合並的得分為24。
顯然，上述5次合並的得分總和為最小
20＋17＋24＝61

上述倒推過程，可由一個print（〔子序列〕）的遞歸演算法描述
procere print （〔i，j〕）
begin
if j〈〉1 then ｛繼續倒推合並過程
begin
print（〔i，c〔i，j〕）；｛倒推子序列1的合並過程｝
print（〔i＋c〔i，j〕－1）mod n＋1，j－c〔i，j〕）
｛倒推子序列2的合並過程｝
for K：＝1 to N do｛輸出當前被合並的兩堆石子｝
if （第K堆石子未從圈內去除）
then begin
if（K＝i）or（K＝X）then置第K堆石子待合並標志
else第K堆石子未被合並；
end；｛then｝
第i堆石子數←第i堆石子數＋第X堆石子數；
將第X堆石子從圈內去除；
end；｛then｝
end；｛print｝
例如，調用print（〔1，6〕）後的結果如下：
print（〔1，6〕）⑤
│
┌——————┴——————┐
│ │
print（〔1，3〕）② print（〔4，3〕）④
│ │
print（〔1，2〕）① ┌—————┴—————┐
│ │ │
│
┌—————┴—————┐ print（〔4，1〕） print（〔5，2〕）③
│ │ │
print（〔1，1〕） print（〔2，1〕） │
┌——————┴——————┐
│ │
print（〔5，1〕） print（〔6，1〕）
（圖6.2-5）
其中回溯至
① 顯示 3 46 5 4
② 顯示 7 65 4 2
③ 顯示 13 54 2
④ 顯示 135 6
⑤ 顯示 13 11
注:調用print過程後，應顯示6堆石子的總數作為第5次合並的得分

D. 演算法題套路總結（三）——動態規劃

前兩篇我總結了鏈表和二分查找題目的一些套路，這篇文章來講講動態規劃。動態規劃從我高中開始參加NOIP起就一直是令我比較害怕的題型，除了能一眼看出來轉移方程的題目，大部分動態規劃都不太會做。加上後來ACM更為令人頭禿的動態規劃，很多題解看了之後，我根本就不相信自己能夠想出來這種解法，看著大佬們談笑間還加一些常數優化，一度懷疑自己的智商。以前一直覺得動態規劃是給大佬准備的，所以刻意地沒有去攻克它，主要也是沒有信心。但是後來慢慢的，我再做LC的時候，發現很多DP的題目我自己慢慢能夠推出轉移方程了，而且似乎也沒那麼難。我一直在思考，到底是我變強了，還是因為LC的題目相比ACM或者NOI太簡單了。其實主要還是後者，但是同時我也發現，動態規劃其實是有套路的，我以前方法不對，總結太少。
主要就是，站在出題人的角度，他幾乎不太可能完全憑空想出一個新的DP模型，因為動態規劃畢竟要滿足：

因此，能夠利用DP來解決的問題實際上是有限的，大部分題目都是針對現有的模型的一些變種，改改題目描述，或者加點限制條件。所以要想攻克DP題目，最根本的就是要充分理解幾個常見的DP模型。而要充分理解常見經典DP模型，就需要通過大量的做題和總結，而且二者不可偏廢。通過做題進行思考和量的積累，通過總結加深理解和融會貫通進而完成質的提升。

動態規劃是求解一個最優化問題，而最核心的思想就是：

解一道DP題目，先問自己幾個問題：

當然以上內容看起來比較抽象，雖然它深刻地揭露了動態規劃的本質，但是如果臨場要去想明白這些問題，還是有些難度。如果只是針對比賽和面試，就像前面說的，DP題型是有限的。只要刷的題目足夠多，總結出幾個經典模型，剩下的都是些變種+優化而已。

一般來說，動態規劃可以分成4個大類:

線性DP就是階段非常線性直觀的模型，比如：最長（上升|下降）序列，最長公共子序列(LCS)等，也有一些簡單的遞推，甚至都算不上是 經典模型 。

最長上升序列是一個非常經典的線性模型。說它是個模型，是因為它是一類題的代表，很多題目都只是換個說法，或者要求在這基礎上進一步優化而已。最長上升序列最基礎的轉移方程就是 f[i] = max{f[j]}+1 (a[i] > a[j]) , f[i] 表示一定要以 a[i] 結尾的序列，最長長度是多少。很顯然就是在前面找到一個最大的 f[j] 同時滿足 a[j]<a[i] 。因此是 N^2 的時間復雜度和N的空間復雜度。這種方法是最樸素直觀的，一定要理解。它非常簡單，因此很少有題目直接能夠這么做。大部分相關題目需要進一步優化，也就是有名的單調隊列優化，能夠把復雜度優化到nlogn。

說單調隊列優化之前必須明白一個貪心策略。因為要求的是最長上升序列，那麼很顯然長度為k的上升序列的最大值（最後一個數）越小越好，這樣後面的數才有更大的概率比它大。如果我們記錄下來不同長度的上升序列的最後一個數能達到的最小值，那麼對於後續每個數t，它要麼能放到某個長度為y的序列之後，組成長度為y+1的上升序列，要麼放到某個長度為x的序列後面，把長度為x+1的序列的最大值替換成t。同時我們可以發現，如果x<y，那麼長度為x序列的最後一個數一定比長度為y的序列最後一個數小。因此這個上升序列我們可以用一個數組來維護（所謂的單調隊列），數組下標就代表序列長度。 opt[i]=t 表示長度為i的上升序列最後一個數最小是t。那麼當我們在面對後續某個數x時，可以對單調隊列opt進行二分，把它插到對應的位置。因此總體復雜度就是NlogN。
相關題目比如：

但是你可以發現，其實這個題型其實變種很有限，吃透了也就那麼回事。所以一定要總結。

最長公共子序列也是線性DP中的一種比較常見的模型。說它是一種「模型」其實有點拔高了，其實它就是一類比較常見的題目。很多題目都是在LCS的基礎上進行簡單的擴展，或者僅僅就是換一個說法而已。
求兩個數組的最長公共子序列，最直觀地做法就是：設f[i][j]表示S[..i]和T[..j]的最長公共子序列，則有:

這個轉移方程也非常好理解，時間復雜度是 N^2 ，空間復雜度也是 N^2 。不過仔細觀察你可以發現，當我們計算第i行時只與i-1和i行有關。因此我們可以利用01滾動來優化空間復雜度為2N。
相關題目：

線性DP除了上述的兩種常見題型，還有很多別的類型，包括背包。我們要努力去嘗試理解這些題目的異同，它們的轉移方程，以及思路，可能的變化，這樣才能更好的應對未知的題目。以下是一些我總結的題型：

最終結果就是max(0, f[n][2]+f[n][4])。
不過實際上你可以發現，由於各個狀態只和前一維有關，且只能由固定的一個狀態轉移過來，因此我們可以省掉一維，只用4個變數來存儲：

剩下的，同123題類似，由於最多進行k次交易，那麼一天就有2k個狀態：第1次買/賣……第k次買/賣，結合123題的優化，我們只需要2k個變數就能存儲這些狀態。因此設f[i×2]為第i次買入的最優值，f[i×2+1]為第i次賣出的最優值：

以上都是對一些常見的線性DP的一些小結，實際上線性DP還有一個重要的題型就是背包。關於背包，有很多相關的講解，我這里就不多說了，推薦大家看看 背包九講 。下一章依然是DP專題，我講總結一些區間DP的題型。大部分區間DP都是hard級的，對於希望提高自己水平的人來說，需要投入更多精力去理解。

E. 什麼是動態規劃動態規劃的意義是什麼

動態規劃是用來求解最優化問題的一種方法。常規演算法書上強調的是無後效性和最優子結構描述，這套理論是正確的，但是適用與否與你的狀態表述有關。至於劃分階段什麼的就有些扯淡了：動態規劃不一定有所謂的階段。其實質是狀態空間的狀態轉移。下面的理解為我個人十年競賽之總結。基本上在oi和acm中我沒有因為動態規劃而失手過。所有的決策類求最優解的問題都是在狀態空間內找一個可以到達的最佳狀態。搜索的方式是去遍歷每一個點，而動態規劃則是把狀態空間變形，由此變成從初始到目標狀態的最短路問題。依照這種描述：假若你的問題的結論包含若干決策，則可以認為從初始狀態（邊界條件）到解中間的決策流程是一個決策狀態空間中的轉移路線。前提是：你的狀態描述可以完整且唯一地覆蓋所有有效的狀態空間中的點，且轉移路線包含所有可能的路徑。這個描述是包含動態規劃兩大條件的。所謂無後效性，指狀態間的轉移與如何到達某狀態無關。如果有關，意味著你的狀態描述不能完整而唯一地包括每一個狀態。如果你發現一個狀態轉移有後效性，很簡單，把會引起後效性的參數作為狀態描述的一部分放進去將其區分開來就可以了；最優子結構說明轉移路線包含了所有可能的路徑，如果不具備最優子結構，意味著有部分情況沒有在轉移中充分體現，增加轉移的描述就可以了。最終所有的搜索問題都可以描述成狀態空間內的狀態轉移方程，只是有可能狀態數量是指數階的，有可能不滿足計算要求罷了。這樣的描述下，所有的動態規劃問題都可以轉變為狀態空間內大量可行狀態點和有效轉移構成的圖的從初始狀態到最終狀態的最短路問題。於是乎，對於動態規劃，他的本質就是圖論中的最短路；階段可以去除，因為不一定有明確的階段劃分。

F. 動態規劃演算法的基本思想

動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。

拓展資料：

動態規劃的實質是分治思想和解決冗餘，因此動態規劃是一種將問題實例分析為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略
動態規劃所針對的問題有一個顯著的特徵，即它對應的子問題樹中的子問題呈現大量的重復。動態規劃的關鍵在於，對於重復的子問題，只在第一次遇到時求解，並把答案保存起來，讓以後再遇到時直接引用，不必要重新求解。

G. 設計動態規劃演算法的主要步驟是怎樣的

Step1：描述最優解的結構特徵
Step2：遞歸地定義一個最優解的值
Step3：自底向上計算一個最優解的值
Step4：從已計算的信息中構造一個最優解

H. 設計動態規劃演算法有哪些主要步驟

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規劃演算法多種多樣，但它們具有相同的填表格式。

I. 動態規劃法的原理

動態規劃法[dynamic programming method (DP)]是系統分析中一種常用的方法。在水資源規劃中,往往涉及到地表水庫調度、水資源量的合理分配、優化調度等問題,而這些問題又可概化為多階段決策過程問題。動態規劃法是解決此類問題的有效方法。動態規劃法是20世紀50年代由貝爾曼（R. Bellman）等人提出,用來解決多階段決策過程問題的一種最優化方法。所謂多階段決策過程,就是把研究問題分成若干個相互聯系的階段,由每個階段都作出決策,從而使整個過程達到最優化。許多實際問題利用動態規劃法處理,常比線性規劃法更為有效,特別是對於那些離散型問題。實際上,動態規劃法就是分多階段進行決策,其基本思路是：按時空特點將復雜問題劃分為相互聯系的若干個階段,在選定系統行進方向之後,逆著這個行進方向,從終點向始點計算,逐次對每個階段尋找某種決策,使整個過程達到最優,故又稱為逆序決策過程。
[1]動態規劃的基本思想
前文主要介紹了動態規劃的一些理論依據，我們將前文所說的具有明顯的階段劃分和狀態轉移方程的動態規劃稱為標准動態規劃，這種標准動態規劃是在研究多階段決策問題時推導出來的，適合用於理論上的分析。在實際應用中，許多問題的階段劃分並不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規模更小的子問題，並且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可以考慮用動態規劃解決。
動態規劃的實質是分治思想和解決冗餘，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略。
由此可知，動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，並通過求解子問題產生一個全局最優解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴於有待於做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子子問題），因此一旦遞歸地求出各子問題的解後，便可自下而上地將子問題的解合並成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題。
解決上述問題的辦法是利用動態規劃。該方法主要應用於最優化問題，這類問題會有多種可能的解，每個解都有一個值，而動態規劃找出其中最優（最大或最小）值的解。若存在若干個取最優值的解的話，它只取其中的一個。但是首先要保證該問題的無後效性,即無論當前取哪個解,對後面的子問題都沒有影響.在求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許這些子問題不獨立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，並將結果保存起來，避免每次碰到時都要重復計算。
因此，動態規劃法所針對的問題有一個顯著的特徵，即它所對應的子問題樹中的子問題呈現大量的重復。動態規劃法的關鍵就在於，對於重復出現的子問題，只在第一次遇到時加以求解，並把答案保存起來，讓以後再遇到時直接引用，不必重新求解。
3、動態規劃演算法的基本步驟
設計一個標準的動態規劃演算法，通常可按以下幾個步驟進行：
（1）劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無後向性），否則問題就無法用動態規劃求解。
（2）選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。