最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

子串、子序列還有公共子序列的概念(在上篇LIS中也曾涉及過) ，我們以字符子串和字符子序列為例，更為形象，也能順帶著理解字符的子串和子序列：

 （1）字符子串：指的是字符串中連續(xù)的n個字符，如abcdefg中，ab，cde，fg等都屬于它的字串。
?
 （2）字符子序列：指的是字符串中不一定連續(xù)但先后順序一致的n個字符，即可以去掉字符串中的部分字符，但不可改變其前后順序。如abcdefg中，acdg，bdf屬于它的子序列，而bac，dbfg則不是，因為它們與字符串的字符順序不一致。
?
 ? (3)  公共子序列：如果序列C既是序列A的子序列，同時也是序列B的子序列，則稱它為序列A和序列B的公共子序列。如對序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 來說，序列1,8,7是它們的一個公共子序列。
?
 ? 那么現(xiàn)在，我們再通俗的總結(jié)一下最長公共子序列（LCS）：就是A和B的公共子序列中長度最長的（包含元素最多的）

其實從上面的對比，我們不難發(fā)現(xiàn)公共子序列不嚴(yán)格要求其公共部分是連續(xù)的，只要其出現(xiàn)的先后順序是一致即可，同上方1,3,5,4,2,6,8,7和序列1,4,8,6,7,5；序列1,8,7都是1先出現(xiàn)，8后出現(xiàn)，7最后出現(xiàn)。

仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5為例，它們的最長公共子序列有1,4,8,7和1,4,6,7兩種，但最長公共子序列的長度是4。由此可見，最長公共子序列（LCS）也不一定唯一。

動態(tài)規(guī)劃解決最長子序列思路

概念描述:

解決LCS問題，需要把原問題分解成若干個子問題，所以需要刻畫LCS的特征。
 ? ? ? 設(shè)A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”為它們的最長公共子序列。不難證明有以下性質(zhì)：
 ? ? ? 
 ? ? ? 如果am=bn，則zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一個最長公共子序列；
 ? ? ? 如果am!=bn，則若zk!=am，蘊涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一個最長公共子序列；
 ? ? ? 如果am!=bn，則若zk!=bn，蘊涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一個最長公共子序列。

對應(yīng)圖解:

假如S1的最后一個元素與S2的最后一個元素相等，那么S1和S2的LCS就等于 {S1減去最后一個元素} 與 {S2減去最后一個元素} 的 LCS 再加上 S1和S2相等的最后一個元素。

假如S1的最后一個元素與S2的最后一個元素不等（本例子就是屬于這種情況），那么S1和S2的LCS就等于 ： {S1減去最后一個元素} 與 S2 的LCS， {S2減去最后一個元素} 與 S1 的LCS 中的最大的那個序列。

引進一個二維數(shù)組c[ ] [ ]，用記錄X[ i ]與Y[ j ]的LCS 的長度，b[ i ] [ j ]記錄c[ i ] [ j ]是通過哪一個子問題的值求得的，以決定搜索的方向。 我們是自底向上進行遞推計算，那么在計算c[i,j]之前，c[ i - 1 ] [ j - 1 ]，c[ i - 1 ] [ j ]和c[ i ] [ j - 1 ]均已計算出來。此時我們根據(jù)X[ i ]==Y[ j ]還是X[ i ]!=Y[ j ]，就可以計算出c[ i ] [ j ]。遞推公式如下：

代碼思路整合:

如下圖，也正是由于在求解過程當(dāng)中，有些步驟的結(jié)果會被反復(fù)使用，這也就是為什么使用動態(tài)規(guī)劃建立表格，以空間換取時間的辦法

建立二維數(shù)組及分析字符的比較情況

二維數(shù)組初始情況及轉(zhuǎn)移方程（也就是填寫記錄表的情況）

填寫dp表格的兩種情況：

?dp表格填寫過程說明：

如填寫dp[2] [2]時，X[2-1] = b與Y[2-1] = c不相等，就是選擇第二種情況，選擇其左、上格子較大值填入，發(fā)現(xiàn)都是1，填入1；

?如填寫dp[3] [2]時，X[3-1] = c與Y[2-1] = c相等，就是選擇第一種情況，選擇其dp[i-1] [j-1]填入，發(fā)現(xiàn)是1，填入1+1=2；

?最終結(jié)果：

代碼:

#define Max 51//字符的最大個數(shù)
int m,n;
char a[m],b[n];//兩個字符數(shù)組
int dp[Max][Max];//動態(tài)規(guī)劃數(shù)組
char subs[Max];//存放LCS

void LCSLength()//求dp的過程
{
    int i,j;
    for (i = 0; i <= m; i++)//邊界條件，將dp[i][0]也就是第一列全置為0
        dp[i][0] = 0;
    for (j = 0; j<= n; j++)//邊界條件，將dp[0][j]也就是第一行全置為0
        dp[0][j] = 0;
    for (i = 1; i <= m; i++)//問題規(guī)模m*n
    {
        for (j = 1; j<= n; j++)
        {
            if (a[i-1] == b[j-1])//第一種情況，兩個序列最后的一個字符相等
                dp[i][j] = dp[i-1][j-1] + 1;
            else//第二種情況，兩個序列最后一個字符不相等
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//將該結(jié)點的左、上結(jié)點比較，將更大的值填入該結(jié)點
        }
    }
}

那么到了這里我們只是填好了dp表格，但是我們要怎么樣根據(jù)這個表格得到我們想要的LCS序列字符數(shù)組呢？

原理：由于我們填表的時候，當(dāng)找到一個公共字符我們就會將dp[i] [j]的值設(shè)置為dp[i-1] [j-1] + 1的值，那么這個值也就是我們根據(jù)dp表找公共子序列的那個字符

?尋找字符的過程：

?

?最終情況：

回溯輸出最長公共子序列過程：

對應(yīng)代碼: ?

void BuildSubs()
{
    int k = dp[m][n];//填完了dp表之后，dp最右下角的那個數(shù)值就是子序列的最大長度
    int i = m,j = n;
    int len = 1;
    while (k > 0)//子序列長度大于0時，在subs中放入最長公共子序列(反向)
    {
        if (dp[i][j] == dp[i-1][j])//與上方元素不相等，往上方回溯可能會遇見子序列
            i--;
        else if (dp[i][j] == dp[i][j-1])//與左方元素不相等，往左方回溯可能會遇見子序列
            j--;
        else//與上方、左給、方元素均不相等，即填表時X[i]==Y[j]遇見了子序列情況
        {
            subs[len++] = a[i-1];//subs中添加公共字符
            i--;
            j--;
            k--;
        }
    }
}

?或者直接整合代碼：

#include <stdio.h>
#include <string.h>
#define MAXLEN 51

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
    int i, j;
    for (i = 0; i <= m; i++)
        c[i][0] = 0;
    for (j = 1; j <= n; j++)
        c[0][j] = 0;
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (x[i - 1] == y[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 0;//為了后面回溯，作為公共子序列的判定
            }
            else if (c[i - 1][j] >= c[i][j - 1])
            {
                c[i][j] = c[i - 1][j];
                b[i][j] = 1;//為了后面向上回溯，向上尋找子序列的判定
            }
            else
            {
                c[i][j] = c[i][j - 1];
                b[i][j] = -1;//為了后面向左回溯，向左尋找子序列的判定
            }
        }
    }
}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
    if (i == 0 || j == 0)
        return;
    if (b[i][j] == 0)//找到了公共字符
    {
        PrintLCS(b, x, i - 1, j - 1);
        printf("%c ", x[i - 1]);
    }
    else if (b[i][j] == 1)//向上回溯的過程
        PrintLCS(b, x, i - 1, j);
    else//向左回溯的過程
        PrintLCS(b, x, i, j - 1);
}

int main(int argc, char **argv)
{
    char x[MAXLEN] = { "ABCBDAB" };
    char y[MAXLEN] = { "BDCABA" };
    int b[MAXLEN][MAXLEN];
    int c[MAXLEN][MAXLEN];
    int m, n;

    m = strlen(x);
    n = strlen(y);

    LCSLength(x, y, m, n, c, b);//填寫動態(tài)規(guī)劃表格
    PrintLCS(b, x, m, n);//回溯輸出最長公共子序列

    return 0;
}

部分文檔參考：

BiliBili俠姐聊算法

程序員編程藝術(shù)第十一章：最長公共子序列(LCS)問題_v_JULY_v的博客-CSDN博客

部分圖片引用：

(1條消息) 動態(tài)規(guī)劃 最長公共子序列 過程圖解_Running07的博客-CSDN博客_最長公共子序列

鑒于個人見解整個代碼以及動態(tài)規(guī)劃的過程希望能幫助大家理解，制作不易文章來源地址http://www.zghlxwxcb.cn/news/detail-599423.html

到了這里，關(guān)于最長公共子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！