動态規劃算法

作者 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)

此過程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)

該過程的運作時間為o（m+n）。

-------------------------------

ok，最後給出此面試第56題的代碼，請君自看：

參考代碼如下：

擴充：如果題目改成求兩個字元串的最長公共子字元串，應該怎麼求？

子字元串的定義和子串的定義類似，但要求是連續分布在其他字元串中。

比如輸入兩個字元串bdcaba和abcbdab的最長公共字元串有bd和ab，它們的長度都是2。

附注：算法導論上指出，

一、最長公共子序列問題的一個一般的算法、時間複雜度為o（mn）。

然後，masek和paterson給出了一個o(mn/lgn)時間内執行的算法，其中n<=m，而且此序列是從一個有限集合中而來。

在輸入序列中沒有出現超過一次的特殊情況中，szymansk說明這個問題可在o(（n+m）lg（n+m）)内解決。

二、一篇由gilbert和moore撰寫的關于可變長度二進制編碼的早期論文中有這樣的應用：

在所有的機率pi都是0的情況下構造最優二叉查找樹，這篇論文給出一個o（n^3）時間的算法。

hu和tucker設計了一個算法，它在所有的機率pi都是0的情況下，使用o（n）的時間和o（n）的空間，

最後，knuth把時間降到了o（nlgn）。 

關于此動态規劃算法更多可參考 算法導論一書第15章 動态規劃問題，

至于關于此面試第56題的更多，可參考我即将整理上傳的答案v04版第41-60題的答案。

                              完、july、二零一零年十二月三十一日。

----------------------------------------------------------------------------------------------------------

補一網友提供的關于此最長公共子序列問題的java算法源碼，我自行測試了下，正确：

import java.util.random;

public class lcs{

    public static void main(string[] args){

        //設定字元串長度

        int substringlength1 = 20;

        int substringlength2 = 20;  //具體大小可自行設定

        // 随機生成字元串

        string x = getrandomstrings(substringlength1);

        string y = getrandomstrings(substringlength2);

        long starttime = system.nanotime();

        // 構造二維數組記錄子問題x[i]和y[i]的lcs的長度

        int[][] opt = new int[substringlength1 + 1][substringlength2 + 1];

        // 動态規劃計算所有子問題

        for (int i = substringlength1 - 1; i >= 0; i--){

            for (int j = substringlength2 - 1; j >= 0; j--){

                if (x.charat(i) == y.charat(j))

                    opt[i][j] = opt[i + 1][j + 1] + 1;                                 //參考上文我給的公式。

                else

                    opt[i][j] = math.max(opt[i + 1][j], opt[i][j + 1]);        //參考上文我給的公式。

            }

        }

 -------------------------------------------------------------------------------------

        了解上段，參考上文我給的公式：

        根據上述結論，可得到以下公式，

        如果我們記字元串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

        -------------------------------------------------------------------------------------

-------------------------------------------------------