動态規劃之最長公共子序列和編輯距離

1.什麼是動态規劃

動态規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動态規劃。1957年出版了他的名著Dynamic Programming，這是該領域的第一本著作。

2.動态規劃的适用範圍

動态規劃通常應用于最優化問題。此類問題可能有很多種可行解，但我們需要找出一個符合我們條件的最優解。這類問題通常可通過分解成成子問題而求解。首先動态規劃是通過組合子問題的解而解決整個問題的。這在某種程度上和分治有點類似，但分治法是将問題分成獨立的子問題，而動态規劃适用于子問題不是獨立的情況，也就是說各個子問題包含着相同的子子問題。動态規劃算法對各個子子問題隻求解一次，将結果儲存下來，下次遇到的時候即可直接适用而無需重複計算。

3.動态規劃的特征

（1）最優子結構 

如果問題的一個解中包含了子問題的最優解，則該問題具有最優子結構。

（2）重疊子問題

第二個特征是當分解原問題時我們所得到的子問題必須是相同的，而不是在産生新的子問題，比如分治法在應用的時候不斷産生新的子問題。動态規劃算法總是充分利用了子問題是相同的這一特征，每個子問題隻求解一次，即第一次遇到的時候進行求解，将其儲存在一張表中，以後在使用時直接查詢擷取。

4.動态規劃的兩個例子

（1）最長公共子序列

問題描述： 一個序列 S ，如果分别是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

首先我們定義X（i）為字元串X的的前i個字元組成的字串，Y（j）為字元串Y的前j個字元組成的字串，很明顯Y（0）為空串。Z（k）為X（i）和Y（j）的最長公共子序列。那麼如果X（i）的最後一個字元x（i）等于Y（j）的最後一個字元y（j）的話，那麼z（k-1）也必然是X（i-1）和Y（j-1）的最長公共子序列。通過反證法很容易得到這一點。這就展現了最優子結構，問題的最優解包含了子問題的最優解。同時我們也看到有很多子子問題是相同的，需要我們重複解決。 令c（i）（j）為X（i）和Y（j）的公共子序列長度。 （a）如果X（i）=Y（j），那麼c（i）（j）=c（i-1）（j-1）； （b）如果X（i）！=Y（j），那麼c（i）（j）=max（c（i-1）（j），c（i）（j-1））； 由上面的狀态轉移方程即可得出，原問題的解即為 c（len1）(len2),len1、len2分别為字元串的長度。

（2）編輯距離

問題描述： 編輯距離（Edit Distance），又稱Levenshtein距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個 字元 替換成另一個字元，插入一個字元，删除一個字元。 例如将kitten一字轉成sitting： sitten （k→s） sittin （e→i） sitting （→g） 同樣的，我們定義c[i][j]為字元串X(i)向字元串Y(j)轉換的操作步驟數。 類似的，我們考慮如果 (a). X(i)的最後一個字元x(i)==Y(j)的最後一個字元y(j) 那麼c[i][j]=c[i-1][j-1];      因為由定義我們知道c[i-1][j-1]是字元串X(i-1)向字元串Y(j-1)的編輯次數，最後一個字元相等的話即x(i)==Y(j)，那麼最後一個字元無需編輯即完成了字元串X(i)向Y(j)的編輯。 (b).X(i)的最後一個字元！=Y(j)的最後一個字元y(j) 這裡又要分三種情況 (1)如果最後一個字元x(i)需要替換成y(j)話，那麼 c[i][j]=c[i-1][j-1]+1; (2)如果最後一個字元x(i)需要删除的話，那麼     c[i][j]=c[i-1][j]+1;    因為由定義可知，c[i-1][j]是字元串X(i-1)轉換成Y(j)所需的操作次數，那麼也就是說在字元串X(i-1)已經成功轉換成了Y(j),那麼顯然最後一個字元x(i)需要删除 (3)如果需要在最後一個字元x(i)後面添加一個字元即y(j)的話，那麼c[i][j]=c[i][j-1]+1; 因為由定義知道，c[i][j-1]是字元串X(i)轉換成Y(j-1)所需的操作次數，想要轉換成Y(j)的話，隻能增加一步添加字元的操作，即插入字元y(j) 綜上所述，c[i][j]=min(c[i-1][j-1],c[i-1][j],c[i][j-1])+1;

csdn程式設計挑戰子產品有道簡易版的編輯距離問題 http://student.csdn.net/mcs/programming_challenges   

描述如下 ： 傳統的編輯距離裡面有三種操作，即增、删、改，我們現在要讨論的編輯距離隻允許兩種操作，即增加一個字元、删除一個字元。我們求兩個字元串的這種編輯距離，即把一個字元串變成另外一個字元串的最少操作次數。 輸入格式： 多組資料，每組資料兩行，每行一個字元串。每個字元串長度不超過1000，隻有大寫英文字母組成。 輸出格式： 每組資料輸出一行包含一個整數，表示需要最少操作的次數。 通過代碼如下：

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int min(int a,int b)
{
    return a<b?a:b;
}
int c[1030][1030];
char stra[10130],strb[1030];
int main(int argc, const char * argv[])
{
    while(scanf("%s",stra)!=EOF)
    {
        scanf("%s",strb);
        
        int len1=strlen(stra);
        int len2=strlen(strb);
        for (int i=0; i<=len1; i++)
        {
            c[0][i]=i;
        }
        for (int j=0; j<=len2; j++)
        {
            c[j][0]=j;
        }
        for (int i=1; i<=len2;i++ )
            for (int j=1; j<=len1; j++)
            {
                if (strb[i-1]==stra[j-1])
                {
                    c[i][j]=c[i-1][j-1];
                }
                else
                {
                    c[i][j]=min(c[i-1][j], c[i][j-1])+1;
                }
            }
        printf("%d\n",c[len2][len1]);
    }
    return 0;
}