以前在學(xué)習(xí)非數(shù)值算法的時候，曾經(jīng)了解過動態(tài)規(guī)劃算法（Dynamic programming），以下是對Wikipedia上動態(tài)規(guī)劃的翻譯，圖也是Wikipedia上的，倉促行文，不到之處，請方家指正。
這篇文章的術(shù)語實在是太多了，所以我在文中加入了少量注釋，一律以粗斜體注明。
本文的不足之處將隨時修正，MIT的《Introduction to Algorithms》第15章是專門講動態(tài)規(guī)劃的。
_____________________________________________________________
動態(tài)規(guī)劃
在數(shù)學(xué)與計算機科學(xué)領(lǐng)域，動態(tài)規(guī)劃用于解決那些可分解為重復(fù)子問題（overlapping subproblems，想想遞歸求階乘吧）并具有最優(yōu)子結(jié)構(gòu)（optimal substructure，想想最短路徑算法）（如下所述）的問題，動態(tài)規(guī)劃比通常算法花費更少時間。
上世紀(jì)40年代，Richard Bellman最早使用動態(tài)規(guī)劃這一概念表述通過遍歷尋找最優(yōu)決策解問題的求解過程。1953年，Richard Bellman將動態(tài)規(guī)劃賦予現(xiàn)代意義，該領(lǐng)域被IEEE納入系統(tǒng)分析和工程中。為紀(jì)念Bellman的貢獻，動態(tài)規(guī)劃的核心方程被命名為貝爾曼方程，該方程以遞歸形式重申了一個優(yōu)化問題。
在“動態(tài)規(guī)劃”（dynamic programming）一詞中，programming與“計算機編程”（computer programming）中的programming并無關(guān)聯(lián)，而是來自“數(shù)學(xué)規(guī)劃”（mathematical programming），也稱優(yōu)化。因此，規(guī)劃是指對生成活動的優(yōu)化策略。舉個例子，編制一場展覽的日程可稱為規(guī)劃。 在此意義上，規(guī)劃意味著找到一個可行的活動計劃。
圖1 使用最優(yōu)子結(jié)構(gòu)尋找最短路徑：直線表示邊，波狀線表示兩頂點間的最短路徑（路徑中其他節(jié)點未顯示）；粗線表示從起點到終點的最短路徑。
不難看出，start到goal的最短路徑由start的相鄰節(jié)點到goal的最短路徑及start到其相鄰節(jié)點的成本決定。
最優(yōu)子結(jié)構(gòu)即可用來尋找整個問題最優(yōu)解的子問題的最優(yōu)解。舉例來說，尋找圖上某頂點到終點的最短路徑，可先計算該頂點所有相鄰頂點至終點的最短路徑，然后以此來選擇最佳整體路徑，如圖1所示。
一般而言，最優(yōu)子結(jié)構(gòu)通過如下三個步驟解決問題：
a) 將問題分解成較小的子問題；
b) 通過遞歸使用這三個步驟求出子問題的最優(yōu)解；
c) 使用這些最優(yōu)解構(gòu)造初始問題的最優(yōu)解。
子問題的求解是通過不斷劃分為更小的子問題實現(xiàn)的，直至我們可以在常數(shù)時間內(nèi)求解。
圖2 Fibonacci序列的子問題示意圖：使用有向無環(huán)圖（DAG, directed acyclic graph）而非樹表示重復(fù)子問題的分解。
為什么是DAG而不是樹呢？答案就是，如果是樹的話，會有很多重復(fù)計算，下面有相關(guān)的解釋。
一個問題可劃分為重復(fù)子問題是指通過相同的子問題可以解決不同的較大問題。例如，在Fibonacci序列中，F(xiàn)3 = F1 + F2和F4 = F2 + F3都包含計算F2。由于計算F5需要計算F3和F4，一個比較笨的計算F5的方法可能會重復(fù)計算F2兩次甚至兩次以上。這一點對所有重復(fù)子問題都適用：愚蠢的做法可能會為重復(fù)計算已經(jīng)解決的最優(yōu)子問題的解而浪費時間。
為避免重復(fù)計算，可將已經(jīng)得到的子問題的解保存起來，當(dāng)我們要解決相同的子問題時，重用即可。該方法即所謂的緩存（memoization，而不是存儲memorization，雖然這個詞亦適合，姑且這么叫吧，這個單詞太難翻譯了，簡直就是可意會不可言傳，其意義是沒計算過則計算，計算過則保存）。當(dāng)我們確信將不會再需要某一解時，可以將其拋棄，以節(jié)省空間。在某些情況下，我們甚至可以提前計算出那些將來會用到的子問題的解。
總括而言，動態(tài)規(guī)劃利用：
1) 重復(fù)子問題
2) 最優(yōu)子結(jié)構(gòu)
3) 緩存
動態(tài)規(guī)劃通常采用以下兩種方式中的一種兩個辦法：
自頂向下：將問題劃分為若干子問題，求解這些子問題并保存結(jié)果以免重復(fù)計算。該方法將遞歸和緩存結(jié)合在一起。
自下而上：先行求解所有可能用到的子問題，然后用其構(gòu)造更大問題的解。該方法在節(jié)省堆棧空間和減少函數(shù)調(diào)用數(shù)量上略有優(yōu)勢，但有時想找出給定問題的所有子問題并不那么直觀。
為了提高按名傳遞（call-by-name，這一機制與按需傳遞call-by-need相關(guān)，復(fù)習(xí)一下參數(shù)傳遞的各種規(guī)則吧，簡單說一下，按名傳遞允許改變實參值）的效率，一些編程語言將函數(shù)的返回值“自動”緩存在函數(shù)的特定參數(shù)集合中。一些語言將這一特性盡可能簡化（如Scheme、Common Lisp和Perl），也有一些語言需要進行特殊擴展（如C++，C++中使用的是按值傳遞和按引用傳遞，因此C++中本無自動緩存機制，需自行實現(xiàn)，具體實現(xiàn)的一個例子是Automated Memoization in C++）。無論如何，只有指稱透明（referentially transparent，指稱透明是指在程序中使用表達式、函數(shù)本身或以其值替換對程序結(jié)果沒有任何影響）函數(shù)才具有這一特性。
1. Fibonacci序列
尋找Fibonacci序列中第n個數(shù)，基于其數(shù)學(xué)定義的直接實現(xiàn)：
function fib(n)
if n = 0
return 0
else if n = 1
return 1
return fib(n-1) + fib(n-2)
如果我們調(diào)用fib(5)，將產(chǎn)生一棵對于同一值重復(fù)計算多次的調(diào)用樹：
- fib(5)
- fib(4) + fib(3)
- (fib(3) + fib(2)) + (fib(2) + fib(1))
- ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
- (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
特別是，fib(2)計算了3次。在更大規(guī)模的例子中，還有更多fib的值被重復(fù)計算，將消耗指數(shù)級時間。
現(xiàn)在，假設(shè)我們有一個簡單的映射（map）對象m，為每一個計算過的fib及其返回值建立映射，修改上面的函數(shù)fib，使用并不斷更新m。新的函數(shù)將只需O(n)的時間，而非指數(shù)時間：
var m := map(0 → 1, 1 → 1)
function fib(n)
if map m does not contain key n
m[n] := fib(n-1) + fib(n-2)
return m[n]
這一保存已計算出的數(shù)值的技術(shù)即被稱為緩存，這兒使用的是自頂向下的方法：先將問題劃分為若干子問題，然后計算和存儲值。
在自下而上的方法中，我們先計算較小的fib，然后基于其計算更大的fib。這種方法也只花費線性（O(n)）時間，因為它包含一個n-1次的循環(huán)。然而，這一方法只需要常數(shù)（O(1)）的空間，相反，自頂向下的方法則需要O(n)的空間來儲存映射關(guān)系。
function fib(n)
var previousFib := 0, currentFib := 1
if n = 0
return 0
else if n = 1
return 1
repeat n-1 times
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib
在這兩個例子，我們都只計算fib(2)一次，然后用它來計算fib(3)和fib(4)，而不是每次都重新計算。
2. 一種平衡的0-1矩陣
考慮n*n矩陣的賦值問題：只能賦0和1，n為偶數(shù)，使每一行和列均含n/2個0及n/2個1。例如，當(dāng)n=4時，兩種可能的方案是：
+ - - - - + + - - - - +
| 0 1 0 1 | | 0 0 1 1 |
| 1 0 1 0 | | 0 0 1 1 |
| 0 1 0 1 | | 1 1 0 0 |
| 1 0 1 0 | | 1 1 0 0 |
+ - - - - + + - - - - +
問：對于給定n，共有多少種不同的賦值方案。
至少有三種可能的算法來解決這一問題：窮舉法（brute force）、回溯法（backtracking）及動態(tài)規(guī)劃（dynamic programming）。窮舉法列舉所有賦值方案，并逐一找出滿足平衡條件的方案。由于共有C(n, n/2)^n種方案（在一行中，含n/2個0及n/2個1的組合數(shù)為C(n,n/2)，相當(dāng)于從n個位置中選取n/2個位置置0，剩下的自然是1），當(dāng)n=6時，窮舉法就已經(jīng)幾乎不可行了。回溯法先將矩陣中部分元素置為0或1，然后檢查每一行和列中未被賦值的元素并賦值，使其滿足每一行和列中0和1的數(shù)量均為n/2。回溯法比窮舉法更加巧妙一些，但仍需遍歷所有解才能確定解的數(shù)目，可以看到，當(dāng)n=8時，該題解的數(shù)目已經(jīng)高達116963796250。動態(tài)規(guī)劃則無需遍歷所有解便可確定解的數(shù)目（意思是劃分子問題后，可有效避免若干子問題的重復(fù)計算）。
通過動態(tài)規(guī)劃求解該問題出乎意料的簡單。考慮每一行恰含n/2個0和n/2個1的k*n(1<=k<=n)的子矩陣，函數(shù)f根據(jù)每一行的可能的賦值映射為一個向量，每個向量由n個整數(shù)對構(gòu)成。向量每一列對應(yīng)的一個整數(shù)對中的兩個整數(shù)分別表示該列上該行以下已經(jīng)放置的0和1的數(shù)量。該問題即轉(zhuǎn)化為尋找f((n/2,n/2),(n/2,n/2),...,(n/2,n/2))（具有n個參數(shù)或者說是一個含n個元素的向量）的值。其子問題的構(gòu)造過程如下：
1) 最上面一行（第k行）具有C(n, n/2)種賦值；
2) 根據(jù)最上面一行中每一列的賦值情況（為0或1），將其對應(yīng)整數(shù)對中相應(yīng)的元素值減1；
3) 如果任一整數(shù)對中的任一元素為負(fù)，則該賦值非法，不能成為正確解；
4) 否則，完成對k*n的子矩陣中最上面一行的賦值，取k=k-1，計算剩余的(k-1)*n的子矩陣的賦值；
5) 基本情況是一個1*n的細(xì)小的子問題，此時，該子問題的解的數(shù)量為0或1，取決于其向量是否是n/2個(0, 1)和n/2個(1, 0)的排列。
例如，在上面給出的兩種方案中，向量序列為：
((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) k = 4
0 1 0 1 0 0 1 1
((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3
1 0 1 0 0 0 1 1
((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2, 0)) k = 2
0 1 0 1 1 1 0 0
((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0)) k = 1
1 0 1 0 1 1 0 0
((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0) (0, 0))
動態(tài)規(guī)劃在此的意義在于避免了相同f的重復(fù)計算，更進一步的，上面著色的兩個f，雖然對應(yīng)向量不同，但f的值是相同的，想想為什么吧:D。
該問題解的數(shù)量（序列a058527在OEIS）是1, 2, 90, 297200, 116963796250, 6736218287430460752, ...
下面的外部鏈接中包含回溯法的Perl源代碼實現(xiàn)，以及動態(tài)規(guī)劃法的MAPLE和C語言的實現(xiàn)。
3. 棋盤
考慮n*n的棋盤及成本函數(shù)C(i,j)，該函數(shù)返回方格(i,j)相關(guān)的成本。以5*5的棋盤為例：
5 | 6 7 4 7 8
4 | 7 6 1 1 4
3 | 3 5 7 8 2
2 | 2 6 7 0 2
1 | 7 3 5 6 1
- + - - - - -
| 1 2 3 4 5
可以看到：C(1,3)=5
從棋盤的任一方格的第一階（即行）開始，尋找到達最后一階的最短路徑（使所有經(jīng)過的方格的成本之和最小），假定只允許向左對角、右對角或垂直移動一格。
5 |
4 |
3 |
2 | x x x
1 | o
- + - - - - -
| 1 2 3 4 5
該問題展示了最優(yōu)子結(jié)構(gòu)。即整個問題的全局解依賴于子問題的解。定義函數(shù)q(i,j)，令：q(i,j)表示到達方格(i,j)的最低成本。
如果我們可以求出第n階所有方格的q(i,j)值，取其最小值并逆向該路徑即可得到最短路徑。
記q(i,j)為方格(i,j)至其下三個方格（(i-1,j-1)、(i-1,j)、(i-1,j+1)）最低成本與c(i,j)之和，例如：
5 |
4 | A
3 | B C D
2 |
1 |
- + - - - - -
| 1 2 3 4 5
q(A) = min(q(B),q(C),q(D)) + c(A)
定義q(i,j)的一般形式：
|- inf. j<1 or j>n
q(i,j) = -+- c(i,j) i=1
|- min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j) otherwise.
方程的第一行是為了保證遞歸可以退出（處理邊界時只需調(diào)用一次遞歸函數(shù)）。第二行是第一階的取值，作為計算的起點。第三行的遞歸是算法的重要組成部分，與例子A、B、C、D類似。從該定義我們可以直接給出計算q(i,j)的簡單的遞歸代碼。在下面的偽代碼中，n表示棋盤的維數(shù)，C(i,j)是成本函數(shù)，min()返回一組數(shù)的最小值：
function minCost(i, j)
if j < 1 or j > n
return infinity
else if i = 1
return c(i,j)
else
return min(minCost(i-1,j-1),minCost(i-1,j),minCost(i-1,j+1))+c(i,j)
需要指出的是，minCost只計算路徑成本，并不是最終的實際路徑，二者相去不遠(yuǎn)。與Fibonacci數(shù)相似，由于花費大量時間重復(fù)計算相同的最短路徑，這一方式慢的恐怖。不過，如果采用自下而上法，使用二維數(shù)組q[i,j]代替函數(shù)minCost，將使計算過程快得多。我們?yōu)槭裁匆@樣做呢？選擇保存值顯然比使用函數(shù)重復(fù)計算相同路徑要簡單的多。
我們還需要知道實際路徑。路徑問題，我們可以通過另一個前任數(shù)組p[i,j]解決。這個數(shù)組用于描述路徑，代碼如下：
function computeShortestPathArrays()
for x from 1 to n
q[1, x] := c(1, x)
for y from 1 to n
q[y, 0] := infinity
q[y, n + 1] := infinity
for y from 2 to n
for x from 1 to n
m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
q[y, x] := m + c(y, x)
if m = q[y-1, x-1]
p[y, x] := -1
else if m = q[y-1, x]
p[y, x] := 0
else
p[y, x] := 1
剩下的求最小值和輸出就比較簡單了：
function computeShortestPath()
computeShortestPathArrays()
minIndex := 1
min := q[n, 1]
for i from 2 to n
if q[n, i] < min
minIndex := i
min := q[n, i]
printPath(n, minIndex)
function printPath(y, x)
print(x)
print("<-")
if y = 2
print(x + p[y, x])
else
printPath(y-1, x + p[y, x])
4. 序列比對
序列比對是動態(tài)規(guī)劃的一個重要應(yīng)用。序列比對問題通常是使用編輯操作（替換、插入、刪除一個要素等）進行序列轉(zhuǎn)換。每次操作對應(yīng)不同成本，目標(biāo)是找到編輯序列的最低成本。
可以很自然地想到使用遞歸解決這個問題，序列A到B的最優(yōu)編輯通過以下措施之一實現(xiàn)：
插入B的第一個字符，對A和B的剩余序列進行最優(yōu)比對；
刪去A的第一個字符，對A和B進行最優(yōu)比對；
用B的第一個字符替換A的第一個字符，對A的剩余序列和B進行最優(yōu)比對。
局部比對可在矩陣中列表表示，單元(i,j)表示A[1..i]到b[1..j]最優(yōu)比對的成本。單元(i,j)的成本計算可通過累加相鄰單元的操作成本并選擇最優(yōu)解實現(xiàn)。至于序列比對的不同實現(xiàn)算法，參見Smith-Waterman和Needleman-Wunsch。
對序列比對的話題并不熟悉，更多的話也無從談起，有熟悉的朋友倒是可以介紹一下。
- 應(yīng)用動態(tài)規(guī)劃的算法
1) 許多字符串操作算法如最長公共子列、最長遞增子列、最長公共字串；
2) 將動態(tài)規(guī)劃用于圖的樹分解，可以有效解決有界樹寬圖的生成樹等許多與圖相關(guān)的算法問題；
3) 決定是否及如何可以通過某一特定上下文無關(guān)文法產(chǎn)生給定字符串的Cocke-Younger-Kasami (CYK)算法；
4) 計算機國際象棋中轉(zhuǎn)換表和駁斥表的使用；
5) Viterbi算法（用于隱式馬爾可夫模型）；
6) Earley算法（一類圖表分析器）；
7) Needleman-Wunsch及其他生物信息學(xué)中使用的算法，包括序列比對、結(jié)構(gòu)比對、RNA結(jié)構(gòu)預(yù)測；
8) Levenshtein距離（編輯距離）；
9) 弗洛伊德最短路徑算法；
10) 連鎖矩陣乘法次序優(yōu)化；
11) 子集求和、背包問題和分治問題的偽多項式時間算法；
12) 計算兩個時間序列全局距離的動態(tài)時間規(guī)整算法；
13) 關(guān)系型數(shù)據(jù)庫的查詢優(yōu)化的Selinger（又名System R）算法；
14) 評價B樣條曲線的De Boor算法；
15) 用于解決板球運動中斷問題的Duckworth-Lewis方法；
16) 價值迭代法求解馬爾可夫決策過程；
17) 一些圖形圖像邊緣以下的選擇方法，如“磁鐵”選擇工具在Photoshop；
18) 間隔調(diào)度；
19) 自動換行；
20) 巡回旅行商問題（又稱郵差問題或貨擔(dān)郎問題）；
21) 分段最小二乘法；
22) 音樂信息檢索跟蹤。
對于這些算法應(yīng)用，大多未曾接觸，甚至術(shù)語翻譯的都有問題，鑒于本文主要在于介紹動態(tài)規(guī)劃，所以倉促之中，未及查證。
1) 貝爾曼方程
2) 馬爾可夫決策過程
3) 貪心算法
Adda, Jerome, and Cooper, Russell, 2003. Dynamic Economics. MIT Press. An accessible introduction to dynamic programming in economics. The link contains sample programs. Richard Bellman, 1957, Dynamic Programming, Princeton University Press. Dover paperback edition (2003), ISBN 0486428095. Bertsekas, D. P., 2000. Dynamic Programming and Optimal Control, Vols. 1 & 2, 2nd ed. Athena Scientific. ISBN 1-886529-09-4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd ed. MIT Press & McGraw-Hill. ISBN 0-262-03293-7. Especially pp. 323–69. Giegerich, R., Meyer, C., and Steffen, P., 2004, "A Discipline of Dynamic Programming over Sequence Data," Science of Computer Programming 51: 215-263. Nancy Stokey, and Robert E. Lucas, with Edward Prescott, 1989. Recursive Methods in Economic Dynamics. Harvard Univ. Press. S. P. Meyn, 2007. Control Techniques for Complex Networks, Cambridge University Press, 2007. - Dyna, a declarative programming language for dynamic programming algorithms
- Wagner, David B., 1995, "Dynamic Programming." An introductory article on dynamic programming in Mathematica.
- Ohio State University: CIS 680: class notes on dynamic programming, by Eitan M. Gurari
- A Tutorial on Dynamic programming
- MIT course on algorithms - Includes a video lecture on DP along with lecture notes -- See lecture 15.
- More DP Notes
- King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." An introduction to dynamic programming as an important tool in economic theory.
- Dynamic Programming: from novice to advanced A TopCoder.com article by Dumitru on Dynamic Programming
- Algebraic Dynamic Programming - a formalized framework for dynamic programming, including an entry-level course to DP, University of Bielefeld
- Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming."
- Dynamic programming tutorial
- An Introduction to Dynamic Programming
_____________________________________________________________
關(guān)于動態(tài)規(guī)劃，這只是一篇譯文，后面將根據(jù)實際問題具體寫點動態(tài)規(guī)劃的應(yīng)用。