動態規劃算法
作者 July 二零一零年十二月三十一日
本文參考：微軟面試100題系列V0.1版第19、56題、算法導論、維基百科。
ok，咱們先來了解下什麼是動態規劃算法。
動態規劃一般也只能應用於有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解
(對有些問題這個要求並不能完全滿足，故有時需要引入一定的近似)。
簡單地說，問題能夠分解成子問題來解決。
動態規劃算法分以下4個步驟：
1.描述最優解的結構
2.遞歸定義最優解的值
3.按自底向上的方式計算最優解的值 //此3步構成動態規劃解的基礎。
4.由計算出的結果構造一個最優解。 //此步如果只要求計算最優解的值時，可省略。
好，接下來，咱們討論適合采用動態規劃方法的最優化問題的倆個要素：
最優子結構性質，和子問題重疊性質。
一、最優子結構。
如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。
意思就是，總問題包含很多歌子問題，而這些子問題的解也是最優的。
二、重疊子問題。
子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，
有些子問題會被重復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，
然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，
從而獲得較高的效率。
ok，咱們馬上進入面試題第56題的求解，即運用經典的動態規劃算法：
56.最長公共子序列。
題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，
則字符串一稱之為字符串二的子串。
注意，並不要求子串（字符串一）的字符必須連續出現在字符串二中。
請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，並打印出最長公共子串。
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，
則輸出它們的長度4，並打印任意一個子串。
分析：求最長公共子串（Longest Common Subsequence, LCS）是一道非常經典的動態規劃題，
因此一些重視算法的公司像MicroStrategy都把它當作面試題。
步驟一、描述一個最長公共子序列
先介紹LCS問題的性質：記Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個字符串，
並設Zk={z0,z1,…zk-1}是X和Y的任意一個LCS，則可得出3條性質：
1. 如果xm-1=yn-1，那麼zk-1=xm-1=yn-1，並且Zk-1是Xm-1和Yn-1的一個LCS；
2. 如果xm-1≠yn-1，那麼當zk-1≠xm-1時，Z是Xm-1和Y的LCS；
3. 如果xm-1≠yn-1，那麼當zk-1≠yn-1時，Z是X和Yn-1的LCS；
下面簡單證明一下由上述相應條件得出的這些性質：
1. 如果zk-1≠xm-1，那麼我們可以把xm-1（yn-1）加到Z中得到Z’，這樣就得到X和Y的一個長度為k+1的公共子串Z’。
這就與長度為k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。
既然zk-1=xm-1=yn-1，那如果我們刪除zk-1（xm-1、yn-1）得到的Zk-1，Xm-1和Yn-1，顯然Zk-1是Xm-1和Yn-1的一個公共子串，現在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設有Xm-1和Yn-1有一個長度超過k-1的公共子串W，那麼我們把加到W中得到W’，那W’就是X和Y的公共子串，並且長度超過k，這就和已知條件相矛盾了。
2. 還是用反證法證明。假設Z不是Xm-1和Y的LCS，則存在一個長度超過k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。矛盾。
3. 證明同2。
步驟二、一個遞歸解
根據上面的性質，我們可以得出如下的思路：
求兩字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，
如果xm-1=yn-1，那麼只需求得Xm-1和Yn-1的LCS，並在其後添加xm-1（yn-1）即可（上述性質1）；
如果xm-1≠yn-1，我們分別求得Xm-1和Y的LCS和Yn-1和X的LCS，並且這兩個LCS中較長的一個為X和Y的LCS（上述性質2、3）。
根據上述結論，可得到以下公式，
如果我們記字符串Xi和Yj的LCS的長度為c[i,j]，我們可以遞歸地求c[i,j]：
/ 0 if i<0 or j<0
c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj
max(c[i,j-1],c[i-1,j] if i,j>=0 and xi≠xj
上面的公式用遞歸函數不難求得。自然想到Fibonacci第n項(本微軟等100題系列V0.1版第19題）問題的求解中可知，
直接遞歸會有很多重復計算，所以，我們用從底向上循環求解的思路效率更高。
為了能夠采用循環求解的思路，我們用一個矩陣（參考下文文末代碼中的LCS_length）保存下來當前已經計算好了的c[i,j]，
當後面的計算需要這些數據時就可以直接從矩陣讀取。
另外，求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個方向計算得到，
相當於在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個各自移動到c[i,j]，
因此在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中只有向左上方移動時才表明找到LCS中的一個字符。
於是我們需要用另外一個矩陣（參考下文文末代碼中的LCS_direction）保存移動的方向。
步驟三，計算LCS的長度
LCS-LENGTH(X, Y)
1 m ← length[X]
2 n ← length[Y]
3 for i ← 1 to m
4 do c[i, 0] ← 0
5 for j ← 0 to n
6 do c[0, j] ← 0
7 for i ← 1 to m
8 do for j ← 1 to n
9 do if xi = yj
10 then c[i, j] ← c[i - 1, j - 1] + 1
11 b[i, j] ← "↖"
12 else if c[i - 1, j] ≥ c[i, j - 1]
13 then c[i, j] ← c[i - 1, j]
14 b[i, j] ← "↑"
15 else c[i, j] ← c[i, j - 1]
16 b[i, j] ← ←
17 return c and b
此過程LCS-LENGTH以倆個序列X = 〈x1, x2, ..., xm〉 和 Y = 〈y1, y2, ..., yn〉為輸入。
它把c[i，j]值填入一個按行計算表項的表c[0 ‥ m, 0 ‥ n] 中， 它還維護b[1 ‥ m, 1 ‥ n] 以簡化最優解的構造。
從直覺上看，b[i, j] 指向一個表項，這個表項對應於與在計算 c[i, j]時所選擇的最優子問題的解是相同的。
該程序返回表中 b and c ， c[m, n] 包含X和Y的一個LCS的長度。
步驟四，構造一個LCS，
PRINT-LCS(b, X, i, j)
1 if i = 0 or j = 0
2 then return
3 if b[i, j] = "↖"
4 then PRINT-LCS(b, X, i - 1, j - 1)
5 print xi
6 elseif b[i, j] = "↑"
7 then PRINT-LCS(b, X, i - 1, j)
8 else PRINT-LCS(b, X, i, j -
