先簡單介紹下什么是最長公共子序列問題，其實問題很直白，假設兩個序列X,Y，X的值是ACBDDCB，Y的值是BBDC，那么XY的最長公共子序列就是BDC。這里解決的問題就是需要一種算法可以快速的計算出這個最大的子序列，當然，用最簡單的方法就是列出XY全部的子系列然后一個個對比，但這樣的時間復雜度是絕對不能接受的。假設X的長度是m，Y的長度是n，拿X的一個子序列和Y進行對比的時間是n，計算X的全部子序列的時間是2^m，所以，如果采用的是一個個全部計算的話，將會花費n*2^m的時間，指數級別的時間復雜度是爆炸式的。我們這里解決的方法是采用動態規劃的方式，所以再講問題之前，先簡單提下動態規劃的概念。

動態規劃

動態規劃是通過組合子問題的解而解決整個問題的，說到這里，是不是有些熟悉？在先前的歸并排序中采用的分治法其實也是對子問題進行分析，但有所不同的是，分治法的思想是通過將問題分解為多個子問題，然后一一解決，最后合并子問題就得到了原問題的答案。當然，分治法所適用的領域就是子問題沒有相互的關聯，而動態規劃所就沒那么簡單了，它的子問題一般都是由相互關聯的情況，也就是說子問題包含了公共的子子問題。什么叫公共的子子問題，就是一個子問題繼續分解，另一個子問題也繼續分解，然后它們驚訝的發現它們分解出來的問題竟然是一樣的。所以假設使用分治法來計算這種問題的話，就會產生許多不必要的重復計算，而動態規劃的目標之一就是去除這種重復的計算，而方法就是講結果放在一張表中，具體的怎么弄可以詳細看最長公共子序列問題怎么解的。

動態規劃常常用于最優解問題，具體的設計可以參考下面的部分：

1.描述最優解的結構

2.遞歸定義最優解的值

3.按自底向上的方式計算最優解的值

4.由計算結果構造一個最優解

這幾個步驟等等就會被用于求解最長公共子序列的問題上，具體步驟請對號入座。

最長公共子序列可以用來干嘛？

在解決這個問題之前，我們當然需要剛清楚自己算出來的東西有什么用處吧~就直接說書上的例子吧，生物里面的DNA由ACGT四種堿基構成，兩種生物的DNA序列就是這四種堿基的集合，而有時候就是需要檢測兩種生物DNA的近似度，一般采用的方法比較多，可以檢測一種生物的DNA是不是另一種生物DNA的子集，或者另一種方式，就是如果有第三條DNA序列同時出現在前面兩條DNA之中，DNA出現的序列順序必須相同，但并不是一定要連續出現。所以，尋找到的那個公共的DNA序列越長，那么兩個生物DNA就越近似。

應用先將這么多，首先需要詳細定義最大公共子序列問題。

一個給定序列的子序列就是該給定序列中去掉零個或者多個元素。另一種形式化的定義（看不看無所謂，看懂開篇說明的話就可以略過），給定一個序列X=<x1,x2,...,xm>，另一個序列Z=<z1,z2,...,zk>是X的一個子序列，如果存在X的一個嚴格遞增下標序列<i1,i2,...,ik>，使得對所有的j=1,2,...,k有xij=zj(注意這里左邊j是i的下標)。

給定兩個序列X和Y，Z是X和Y的公共子序列，假若Z的長度是所有的X和Y的公共子序列中最長的，那么稱Z為最長公共子序列，算法的目的就是為了求解這些最長公共子序列（注意，Z并不一定唯一）

步驟一：描述一個最長公共子序列

對于以下的最長公共子序列問題，簡稱為LCS問題。之前提到的將XY中所有的子序列全部計算出來再進行比較顯然是不現實的，但是，對于LCS問題而言，具有最優子結構特征，具體的說明在下面的定理中。這里，我們先給出前綴的概念，具體定義就不提了，就舉一個例子，假設X=<A,B,C,B,D,A,B>,那么X4=<A,B,C,B>就是X的一個前綴，顯然，X0為空。而下面分解的子問題其實就是分解為前綴。

定理（LCS的最優子結構）：

設X=<x1,x2,...,xm>，Y=<y1,y2,...,yn>為兩個序列，并且Z=<z1,z2,...,zk>為X和Y的任意一個LCS

1.如果xm=yn,那么zk=xm=yn而且Z(k-1)是X(m-1)和Y(n-1)的一個LCS

2.如果xm!=yn,那么zk!=xm蘊含Z是X(m-1)和Y的一個LCS

3.如果xm!=yn,那么zk!=yn蘊含Z是X和Y(n-1)的一個LCS

這些性質的作用其實就是為了說明兩個序列的LCS包含了兩個序列前綴的LCS，那么LCS就具有最優子結構性質（最優子結構就是一個最優解包含了子結構的最優解）。

步驟二：一個遞歸解

從上面的定理我們可以知道，在尋找LCS的時候，一般就是從子序列中尋找LCS，這樣就要檢查一個或者兩個字問題。如果xm=yn，那么就要找出X(m-1)和Y(n-1)的LCS，然后將xm=yn加上去，就是X和Y的LCS了。但如果xm!=yn的話，那么就要分別計算X(m-1)和Y以及X和Y(n-1)的兩個LCS，比價長的LCS就是要找的。這樣雖然表面上是遞歸分治的問題，但實際上如果仔細觀察的話就會發現LCS問題中的重疊子問題，比如對于X(m-1)和Y的子問題，和X和Y(n-1)的子問題中，同時包含了X(m-1)和Y(n-1)的子子問題，這樣就導致了重復計算的問題，這樣使用分治直接解決就不適用了。具體的解決方法后文將會描述。

要求出最長的子序列，首先要知道的是最長有多長。這里定義C[i,j]為序列Xi和Yj的一個LCS的長度，可得到遞歸式：

步驟三：計算LCS的長度

其實就是根據上面的遞歸式給出程序，這里先給出偽代碼，具體程序最后給出：

可以看到，在程序中有兩個二維數組c和b，c用來記錄最長子序列的長度，b的話相當于記錄了軌跡，在最后構造LCS的時候起到作用。

下圖展示的就是程序運行后表格c和b的具體情形（畫在了一張表里）

步驟四：構造一個LCS

只要得到了表b，就可以快速構造出LCS，偽代碼如下：

這是一個遞歸算法，一開始i和j的值為m和n，就是從表格的右下角開始回溯，從而得到LCS。

下面給出具體的C語言實現過程：

?

#include <stdio.h> #include <stdlib.h>#define m 7 #define n 6int c[m+1][n+1]; char b[m+1][n+1];void LCS_LENGTH(char* X,char* Y) {int i,j;for(i=1;i<=m;i++)c[i][0]=0;for(j=0;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(X[i]==Y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]='\\';}else{if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]='|';}else{c[i][j]=c[i][j-1];b[i][j]='-';}}}} }void PRINT_LCS(char* X,int i,int j) {if(i==0 || j==0)return;if(b[i][j]=='\\'){PRINT_LCS(X,i-1,j-1);printf("%c ",X[i]);}else if(b[i][j]=='|')PRINT_LCS(X,i-1,j);elsePRINT_LCS(X,i,j-1); }int main(void) {int i,j;char X[m+1]={'X','A','B','C','B','D','A','B'};char Y[n+1]={'Y','B','D','C','A','B','A'};LCS_LENGTH(X,Y);printf("LCS長度表c打印出來是這個樣子:\n");for(i=1;i<=m;i++){for(j=1;j<=n;j++)printf("%d ",c[i][j]);printf("\n");}printf("路徑表b打印出來是這個樣子\n");for(i=1;i<=m;i++){for(j=1;j<=n;j++)printf("%c ",b[i][j]);printf("\n");}printf("\nLCS的具體值是：\n");PRINT_LCS(X,m,n);return 0; }

?

當然了，改進代碼的方式也有很多，對空間的改進可以完全不使用表b等等，這里就不再詳細敘述了。

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的最长公共子序列（LCS问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。