動態規劃的基本知識
動態規劃是研究一類最最佳化問題的方法，在經濟、工程技術、企業管理、工農業生產及軍事等領域中都有廣泛的套用。近年來，在ACM/ICPC中，使用動態規劃(或部分套用動態規劃思維)求解的題不僅常見，而且形式也多種多樣。而在與此相近的各類信息學競賽中，套用動態規劃解題已經成為一種趨勢，這和動態規劃的優勢不無關係。
1、動態規劃的常用名詞
在學習動態規劃之前，先得對下面的名詞有所了解。本書將標準名詞作了一些簡化，便於大家更好的理解。
(1)狀態(smte)
對於一個問題，所有可能到達的情況(包括初始情況和目標情況)都稱為這個問題的一個狀態。
(2)狀態變數(sk)
對每個狀態k關聯一個狀態變數sk，它的值表示狀態k所對應的問題的當前解值。
(3)決策(decision)
決策是一種選擇，對於每一個狀態而言，你都可以選擇某一種路線或方法，從而到達下一個狀態。
(4)決策變數(dk)
在狀態k下的決策變數dk的值表示對狀態k當前所做出的決策。
(5)策略
策略是一個決策的集合，在我們解決問題的時候，我們將一系列決策記錄下來，就是一個策略，其中滿足某些最優條件的策略稱之為最優策略。
(6)狀態轉移函式(t)
從一個狀態到另一個狀態，可以依據一定的規則來前進。我們用一個函式t來描述這樣的規則，它將狀態i和決策變數di映射到另一個狀態j，記為t(i，di)=j
(7)狀態轉移方程(f)
狀態轉移方程f描述了狀態變數之間的數學關係。一般來說，與最最佳化問題相應，狀態轉移方程表示si的值最最佳化的條件，或者說是狀態i所對應問題的最優解值的計算公式，用代數式表示就是：
si=f({(sj,dj)|i=t(j,dj)，對決策變數dj所有可行的取值})
2、最最佳化原理
1951年美國數學家R．Bellman等人，根據一類多階段問題的特點，把多階段決策問題變換為一系列互相聯繫的單階段問題，然後逐個加以解決。一些靜態模型，只要人為地引進“時間”因素，分成時段，就可以轉化成多階段的動態模型，用動態規劃方法去處理。與此同時，他提出了解決這類問題的“最最佳化原理”(Principle of optimality)：
“一個過程的最優決策具有這樣的性質：即無論其初始狀態和初始決策如何，其今後諸策略對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略”。簡言之，一個最優策略的子策略，對於它的初態和終態而言也必是最優的。
這個“最最佳化原理”如果用數學化一點的語言來描述的話，就是：假設為了解決某一最佳化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優的，對於任何一個整數k，1 < k < n，不論前面k個決策是怎樣的，以後的最優決策只取決於由前面決策所確定的當前狀態，即以後的決策Dk+1，Dk+2，…，Dn也是最優的。
最最佳化原理是動態規劃的基礎。任何一個問題，如果失去了這個最最佳化原理的支持，就不可能用動態規劃方法計算。
3、什麼是動態規劃
動態規劃是運籌學的一個分支。與其說動態規劃是一種算法，不如說是一種思維方法來得更貼切。因為動態規劃沒有固定的框架，即便是套用到同一道題上，也可以建立多種形式的求解算法。許多隱式圖上的算法，例如求單源最短路徑的Dijkstra算法、廣度優先搜尋算法，都滲透著動態規劃的思想。還有許多數學問題，表面上看起來與動態規劃風馬牛不相及，但是其求解思想與動態規劃是完全一致的。
因此，動態規劃不像深度或廣度優先那樣可以提供一套模式，需要的時候，取來就可以使用；它必須對具體問題進行具體分析處理，需要豐富的想像力去建立模型，需要創造性的思想去求解。
4、動態規劃適於解決什麼樣的問題
準確地說，動態規劃不是萬能的，它只適於解決一定條件的最優策略問題。
或許，大家聽到這個結論會很失望：其實，這個結論並沒有削減動態規劃的光輝，因為屬於上面範圍內的問題極多，還有許多看似不是這個範圍中的問題都可以轉化成這類問題。
上面所說的“滿足一定條件”主要指下面兩點：
(1)狀態必須滿足最最佳化原理；
(2)狀態必須滿足無後效性。
所謂的無後效性是指：“過去的決策只能通過當前狀態影響未來的發展，當前的狀態是對以往決策的總結”。
這條特徵說明什麼呢?它說明動態規劃適於解決當前決策和過去狀態無關的問題。狀態，出現在策略的任何一個位置，它的地位都是相同的，都可以實施同樣的決策。這就是無後效性的內涵。
5、用動態規劃解題的好處
說了這么多的動態規劃，它到底給我們解題能帶來什麼好處呢?
其實動態規劃的最大優勢在於它具有極高的效率，而且動態規劃還有其他的優勢，例如：動態規劃可以得出一系列解，算法清晰簡便，程式易編、易調，等等。
動態規劃的逆向思維法
動態規劃是一種思維方法，沒有統一的、具體的模式。動態規劃可以從多方面去考察，不同的方面對動態規劃有不同的表述。我們不打算強加一種統一的表述，而是從多個角度對動態規劃的思維方法進行討論，希望大家在思維具體問題時，也能夠從多個角度展開，這樣收穫會更大。
逆向思維法是指從問題目標狀態出發倒推回初始狀態或邊界狀態的思維方法。如果原問題可以分解成幾個本質相同、規模較小的問題，很自然就會聯想到從逆向思維的角度尋求問題的解決。
你也許會想，這種將大問題分解成小問題的思維不就是分治法嗎?動態規劃是不是分而治之呢?其實，雖然我們在運用動態規劃的逆向思維法和分治法分析問題時，都使用了這種將問題實例歸納為更小的、相似的子問題，並通過求解子問題產生一個全局最優值的思路，但動態規劃不是分治法：關鍵在於分解出來的各個子問題的性質不同。
分治法要求各個子問題是獨立的(即不包含公共的子問題)，因此一旦遞歸地求出各個子問題的解後，便可自下而上地將子問題的解合併成原問題的解。如果各子問題是不獨立的，那么分治法就要做許多不必要的工作，重複地解公共的子問題。
動態規劃與分治法的不同之處在於動態規劃允許這些子問題不獨立(即各子問題可包含公共的子問題)，它對每個子問題只解一次，並將結果保存起來，避免每次碰到時都要重複計算。這就是動態規劃高效的一個原因。
動態規劃的逆向思維法的要點可歸納為以下三個步驟：
(1)分析最優值的結構，刻畫其結構特徵；
(2)遞歸地定義最優值；
(3)按自底向上或自頂向下記憶化的方式計算最優值。
【例題5】背包問題描述：
有一個負重能力為m的背包和n種物品，第i種物品的價值為v，重量為w。在不超過背包負重能力的前提下選擇若干個物品裝入背包，使這些的物品的價值之和最大。每種物品可以不選，也可以選擇多個。假設每種物品都有足夠的數量。
分析：
從算法的角度看，解決背包問題一種最簡單的方法是枚舉所有可能的物品的組合方案並計算這個組合方案的價值之和，從中找出價值之和最大的方案。顯然，這種靠窮舉所有可能方案的方法不是一種有效的算法。
但是這個問題可以使用動態規劃加以解決。下面我們用動態規劃的逆向思維法來分析這個問題。
(1)背包問題最優值的結構
動態規劃的逆向思維法的第一步是刻畫一個最優值的結構，如果我們能分析出一個問題的最優值包含其子問題的最優值，問題的這種性質稱為最優子結構。一個問題的最優子結構性質是該問題可以使用動態規劃的顯著特徵。
對一個負重能力為m的背包，如果我們選擇裝入一個第 i 種物品，那么原背包問題就轉化為負重能力為 m-w 的子背包問題。原背包問題的最優值包含這個子背包問題的最優值。若我們用背包的負重能力來劃分狀態，令狀態變數s[k]表示負重能力為k的背包，那么s [m]的值只取決於s[k](k≤m)的值。因此背包問題具有最優子結構。
(2)遞歸地定義最優值
動態規劃的逆向思維法的第二步是根據各個子問題的最優值來遞歸地定義原問題的最優值。對背包問題而言，有狀態轉移方程：
／max{s[k-w]+v}(其中1≤i≤n，且k-w≥0)
s[k]= 若k>0且存在1≤i≤n使k-w≥0，
＼ 0 否則。
有了計算各個子問題的最優值的遞歸式，我們就可以直接編寫對應的程式。下述的函式knapsack是輸入背包的負重能力k，返回對應的子背包問題的最優值s[k]：
function knapsack(k:integer):integer；
begin
knapsack:=0；
for i:=1 to n do
if k-w>=0 then
begin
t:=knapsack(k-w)+v；
if knapsack < t then knapsack:=t；
end;
end；
上述遞歸算法在求解過程中反覆出現了一個子問題，且對每次重複出現的子問題都要重新解一次，這需要多花費不少時間。下面先考慮一個具體的背包問題。例如，當
m=3，n=2，v[1]=1，w[1]=1，v[2]=2，w[2]=2，
圖1示出了由調用knapsack(3)所產生的遞歸樹，每一個結點上標有參數k的值，請注意某些數出現了多次。
3
／＼
2 1
／＼ ＼
1 0 0
／
0
圖1
例如，knapsack(1)被引用了兩次：在計算knapsack(3)和knapsack(2)中分別被引用；而knapsack(0)更是被引用了三次。如果knapsack(1)和knapsack(0)每次都要被重新計算，則增加的運行時間相當可觀。
下面，我們來看看動態規劃是如何解決這個問題的。
(3)按自頂向下記憶化或自底向上的方式求最優解
一般地，如果一個解最最佳化問題的遞歸算法經常反覆地解重複的子問題，而不是總在產生新的子問題時，我們說該最最佳化問題包含重迭子問題。這類問題不宜用分治法求解，因為分治法遞歸的每一步要求產生相異的子問題。在這種情況下，採用動態規劃是很合適的，因為該方法對每一個子問題只解一次，然後把解存放在一個表中，以便在解同樣的子問題時查閱，充分利用了重迭子問題。一般來說，解決重迭子問題的方式有兩種。
①自頂向下的記憶化方式
該方式的程式流程基本按照原問題的遞歸定義，不同的是，它專門設定了一張表，以記憶在求解過程中得出的所有子問題的解。一個記憶的遞歸算法為每個子問題的解在表中記錄一個表項。初始時每個表項都包含一個特殊值，以示該表項的解有待填入。例如背包問題中：
s=-1；(0≤i≤m)
當在遞歸算法的執行中第一次遇到一個子問題時(即s=-1)，計算其解並填入表中，以後每遇到該子問題，只要查看錶中先前填入的值即可。
下面，我們按照自上而下的記憶化方式，寫出求背包問題的遞歸算法。
函式memorized_knapsack輸入背包的負重能力k，返回背包問題的解s[k]。s表應設為全局變數，使得函式執行後，傳出所有子問題的解s(0≤i≤m)。
function memorized_knapsack(k:integer):integer；
begin
if s[k]=-1 then
begin
s[k]:=0；
for i:=1 to n do
if k-w>=0 then
begin
t:=memorized_knapsack(k-W)+V；
if s[k] < t then s[k]:=t；
end；
end；
memorized_knapsack:=s[k]；
end；
我們在主程式通過調用memorized_knapsack(m)即可獲得背包問題的解。
顯然這種自頂向下記憶化的算法效率比重複解重迭子問題的knapsack算法要強一些。此外，在程式中加入判別哪些子問題需要求解的語句，只解那些肯定要解的子問題，從而節省了時間。
②自底向上的方式
假設我們要解決在分析函式knapsack當中提出的那個具體的背包問題。觀察一下在調用memorized_knapsack(4)的過程中， s[k]被計算出來的順序。我們發現，首先是s[0]被計算出來，然後是s[1]，s[2]，最後s[3]被計算出來，這與調用的次序正好相反。
動態規劃的執行方式是自底向上，所有的子問題計算一次，充分利用重迭子問題。因此，我們很自然就想到與這種自底向上的執行方式相應的採用自底向上的方式遞推所有子問題的最優值。
我們知道，計算負重能力為k的背包問題的解僅依賴於計算負重能力小於k的背包問題的解，因此填s表的方式與解決負重能力遞增的背包問題相對應：
最初設定負重能力為0的背包問題的解s[0]=0。然後依次考慮負重能力為1，2，…，m的背包問題的解。每填入一個s[k](0≤k≤m)時，充分利用所有重迭子問題的解：s[k-w](0≤i≤n，k-w≥0)
下面是按照自底向上方式計算背包問題的算法流程。過程knapsack_order輸入背包的負重能力k，s表設為全局變數。過程執行後所有子問題的解通過s表傳給主程式。
procedure knapsack_order(k:integer);
begin
for i:=1 to k do s:=0;
for j:=1 to k do
for i:=1 to n do
if j-w>=0 then
begin
t:=s[j-w]+v;
if s[j] < t then s[j]:=t;
end;
end;
我們在主程式調用knapsack_order(m)，過程執行後s[m]即為背包問題的解。
最後，我們分析一下背包問題的動態規劃解法的複雜度。所需的存儲開銷主要在s表上，其空間複雜度是O(m)。而整個s表用兩重循環求出，循環內語句的執行只需常數時間，因此，時間複雜度是O(m,n)。
自頂向下的記憶化是動態規劃的一種變形。動態規劃的執行方式是自底向上，因此自底向上的計算方式是與動態規劃的執行方式相一致的。它無需遞歸代價，且維護記憶表的開銷也要小些，因此其效率通常好於自頂向下的記憶法。
但是，在動態規劃的執行過程中，並不是所有的子問題都要用到它。對某個具體問題而言，可能有大部分子問題的最優值是不必計算的。自底向上的計算方式無法判斷那些子問題是需要求解的，所以它將一視同仁地處理所有的子問題，這就可能會把大量的時間都花在計算不必解決的子問題上；而自頂向下的記憶法可以判斷那些子問題是需要求解的，只解那些肯定要解的子問題，在這個意義上，自頂向下的算法效率又好於自底向上。所以到底那種方式效率更高，我們要具體問題具體分析。
最後，給出求解背包問題的程式如下：
{//背包問題程式}
program knapsack;
const
maxn=100;
maxm=1000;
var
m,n:integer;
S:array[0..maxm] of integer;
v,w:array[1..maxn] of integer;
{//輸入數據}
procedure read_data;
var i:integer;
begin
read(m,n);
for i:=1 to n do read(v,w);
end;
{//採用自底向上的方式求解背包問題}
procedure knapsack_order;
var i,j,t:integer;
begin
for i:=1 to m do s:=0;
for j:=1 to m do
for i:=1 to n do
if j-w>=0 then
begin
t:=s[j-w]+v;
if s[j] < t then s[j]:=t;
end;
end;
{//主程式}
begin
read_data;
knapsack_order;
writeln(s[m]);
end.
動態規劃的正向思維法
正向思維法是指從初始狀態或邊界狀態出發，利用某種規則不斷到達新的狀態，直到問題目標狀態的方法。動態規劃的正向思維法，正是從已知最優值的初始狀態或邊界狀態開始，按照一定的次序遍歷整個狀態空間，遞推出每個狀態所對應問題的最優值。
提出動態規劃的正向思維法的根本原因，是為了擺脫逆向思維法當中那種將大問題轉化為子問題的思維框框，提供一種新的思維方式。在正向思維法中，我們不再區分原問題和子問題，將動態規劃的過程看成是從狀態到狀態的轉移。我們將所有的狀態構造出一個狀態空間，並在狀態空間中構想一個狀態網路，若對兩個狀態i,j，存在決策變數di使t(i，di)=j，則向狀態網路添加有向邊。給定己知最優值的初始狀態或邊界狀態，我們可以沿著有向邊推廣到未知最優值的新狀態，利用狀態轉移方程得到新狀態的狀態變數的最優值。我們可以用這種方式遍歷整個狀態空間，得到每個狀態的狀態變數的最優值。
因為正向思維法中不再區分原問題、子問題、子子問題，所以我們不再按照問題被遞歸調用求解的相反次序的方法確定狀態最優值的計算次序。從上面我們知道可以按照狀態的拓撲序列來計算每個狀態的最優值，於是我們用一個新的名詞“階段”來描述在狀態空間遍歷的過程中，各個狀態最優值的計算次序。我們將每個狀態和一個階段掛鈎，前一個階段的狀態先計算，後一個階段的狀態後計算。有的時候我們甚至將一組狀態和一個階段掛鈎，前一個階段的那組狀態先計算，後一個階段的那組狀態後計算，而在同一個階段內，那些狀態的計算次序可以是任意的。
動態規劃的正向思維法的要點可歸納為以下三個步驟：
(1)構造狀態網路；
(2)根據狀態轉移關係和狀態轉移方程建立最優值的遞推計算式：
(3)按階段的先後次序計算每個狀態的最優值。
在下一節“最短路問題”當中，我們將結合最短路問題來示範動態規劃的正向思維法。
動態規劃的正向思維法帶給我們什麼啟示呢?動態規劃需要按階段遍歷整個狀態空間，因此動態規劃的效率取決於狀態空間的大小和計算每個狀態最優值的開銷：如果狀態空間的大小是多項式的，那么套用動態規劃的算法就是多項式時間的；如果狀態空間的大小是指數的，那么套用動態規劃的算法也是指數時間的。因此，找一個好的狀態劃分對動態規劃的效率是至關重要的。
將這個結論套用到逆向思維上，我們得出如下結果：一個問題的最優子結構常常暗示了動態規劃的狀態空間。典型的情況是，某一個特定問題可有幾類“自然”的子問題，不同的子問題往往意味著不同的最優子結構，從而我們得到不同的狀態劃分方案。但是由這些不同的狀態得到的算法的效率可能差異極大。例如，某個問題的輸入是一個有序序列，有兩類“自然”的子問題，一類子問題的輸入是原問題輸入序列的所有子序列，另一類子問題的輸入是原問題輸入序列的任意元素構成的新序列。顯然若我們採用後者的最優子結構來建立狀態，它的狀態空間必然遠遠大於基於前者的狀態空間。那末基於後者的狀態空間的動態規劃則要解許多不必要的問題，使得算法的效率驟然下降。
從動態規劃的正向思維法的分析可以看出，我們從已知最優值的初始狀態和邊界狀態出發，利用最最佳化原理，一步一步向未知的目標狀態推進，直到目標狀態的最優值解決。這種“從己知推廣到未知”的思維，正是動態規劃正向思維法的精髓。大家在運用動態規劃的正向思維法時如果能掌握這一點，那么就能達到套用自如的境界。
在套用動態規劃求解的問題的過程中，希望讀者能夠注意從題目的分析中領會：套用動態規劃解題是富於技巧和創造性的，沒有固定的模式可套；題目出現的形式多種多樣，而且大部分表面上與動態規劃看不出直接的聯繫。只有在充分把握其思想精髓的前提下大膽聯想，才能達到得心應手，靈活運用的境界。
動態規劃設計方法的一般模式
動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
┌───┐ ┌───┐ ┌───┐
初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態
└───┘ └───┘ └───┘
圖1 動態規劃決策過程示意圖
(1)劃分階段：，按照問題的時間或空間特徵，把問題分為若干個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態和狀態變數：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
(3)確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯繫，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態之間的關係來確定決策。
(4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
(5)程式設計實現：動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。 下面，給出一個利用動態規劃方法求解的典型例子。
【例題6】數字三角形問題。圖3示出了一個數字三角形寶塔。數字三角形中的數字為不超過100的整數。現規定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。
任務一：假設三角形行數≤10，鍵盤輸入一個確定的整數值M，編程確定是否存在一條路徑，使得沿著該路徑所經過的數字的總和恰為M，若存在則給出所有路徑，若不存在，則輸出“NO Answer!”字樣。
任務二：假設三角形行數≤100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經過的數字的總和最大，輸出最大值。
輸入數據：由檔案輸入數據，任務一中檔案第一行是三角形的行數N和整數值 M。以後的N行分別是從最頂層到最底層的每一層中的數字。任務二中檔案數據格式同任務一，只是第一行中沒有整數值M。在例子中任務二的檔案數據表示如下：
輸入：5
7 輸出：
3 8 7 輸出路徑和最大值
8 1 0 3 8 或“No Answer!”字樣。
2 7 7 4 8 1 0
4 5 2 6 5 2 7 4 4
圖3 數字三角形 4 5 2 6 5
【分析】對於這一問題，很容易想到用枚舉的方法去解決，即列舉出所有路徑並記錄每一條路徑所經過的數字總和。然後判斷數字總和是否等於給定的整數值M或尋找出最大的數字總和，這一想法很直觀，而且對於任務一，由於數字三角形的行數不大(<＝10)，因此其枚舉量不是很大，應該能夠實現。但對於任務二，如果用枚舉的方法，當三角形的行數等於100時，其枚舉量之大是可想而知的，顯然，枚舉法對於任務二的求解並不適用。其實，只要對對任務二稍加分析，就可以得出一個結論：
如果得到一條由頂至底的某處的一條最佳路徑，那么對於該路徑上的每一個中間點來說，由頂至該中間點的路徑所經過的數字和也為最大。因此該問題是一個典型的多階段決策最最佳化的問題。算法設計與分析如下：
對於任務一，合理地確認枚舉的方法，可以最佳化問題的解法。由於從塔頂到底層每次都只有兩種走法，即左或右。設“0”表示左， “1”表示右，對於層數為N的數字塔，從頂到底的一種走法可用一個N-1位的二進制數表示。如例中二進制數字串1011，其對應的路徑應該是：8—1—4—6。這樣就可以用一個N—l位的二進制數來模擬走法和確定解的範圍。窮舉出從0到2n-1個十進制數所對應的N-1位二進制串對應的路徑中的數字總和，判定其是否等於M而求得問題的解。
對於任務二，採用動態規劃中的順推解法。按三角形的行劃分階段，若行數為 n，則可把問題看做一個n-1個階段的決策問題。從始點出發，依順向求出第一階段、第二階段……第n—1階段中各決策點至始點的最佳路徑，最終求出始點到終點的最佳路徑。
設：fk(Uk)為從第k階段中的點Uk至三角形頂點有一條最佳路徑，該路徑所經過的數字的總和最大，fk(Uk)表示為這個數字和；
由於每一次決策有兩個選擇，或沿左斜線向下，或沿右斜線向下，因此設：
Uk1為k-1階段中某點Uk沿左斜線向下的點；
Uk2為k-1階段中某點Uk沿右斜線向下的點；
dk(Uk1)為k階段中Uk1的數字；dk(Uk2)為k階段中Uk2的數字。
因而可寫出順推關係式(狀態轉移方程)為：
fk(Uk)=max{fk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)}(k=1，2，3，…，n)
f0(U0)＝0
經過一次順推，便可分別求出由頂至底N個數的N條路徑，在這N條路徑所經過的N個數字和中，最大值即為正確答案。
