動態規劃解決LCS問題

1. 問題定義： 給定兩個序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }，找出 X 和 Y 的最長公共子序列。
一個給定序列的子序列是在該序列中刪去若干個元素後得到的序列。給定兩個序列 X 和 Y ，當另一序列 Z 既是 X 的子序列又是 Y 的子序列時，稱 Z 是序列 X 和 Y 的公共子序列。
例如，若 X = {A， B， C， B， D， A， B }，
Y = {B， D， C， A， B， A }，

序列{B， C， A }是 X 和 Y 的一個公共子序列，序列{B， C， B， A }也是 X 和 Y 的一個公共子序列，且為最長公共子序列。
需要注意的是：最長公共子序列與最長公共子串之間的區別。 最長公共子串在原序列中是連續，而最長公共子序列中的各個元素在原序列中不需要連續。如字符串abdewefd和aeffdewsd最長公共子串為dew，而最長公共子序列為adewd。
2. 動態規劃求解LCS問題 分析最長公共子序列的定義，從《算法導論》上有定理:LCS的最優子結構性質

設序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的一個最長公共子序列Z=<z₁, z₂, …, z_k>，則：

1. 若x_m=y_n，則z_k=x_m=y_n且Z_k-1是X_m-1和Y_n-1的最長公共子序列；

2. 若x_m≠y_n且z_k≠x_m，則Z是X_m-1和Y的最長公共子序列；

3. 若x_m≠y_n且z_k≠y_n，則Z是X和Y_n-1的最長公共子序列。

其中X_m-1=<x₁, x₂, …, x_m-1>，Y_n-1=<y₁, y₂, …, y_n-1>，Z_k-1=<z₁, z₂, …, z_k-1>。
由最長公共子序列問題的最優子結構性質可知，要找出X=, x<x₁₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最長公共子序列，可按以下方式遞歸地進行： 當x_m=y_n時，找出X_m-1和Y_n-1的最長公共子序列，然後在其尾部加上x_m(=y_n)即可得X和Y的一個最長公共子序列。 當x_m≠y_n時，必須解兩個子問題，即找出X_m-1和Y的一個最長公共子序列及X和Y_n-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。

由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Y_n-1及X_m-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算X_m-1和Y_n-1的最長公共子序列。

為了求解LCS問題，需要建立子問題最優值的遞歸關系。用c[i,j]記錄序列X_i和Y_j的最長公共子序列的長度。其中X_i=<x₁, x₂, …, x_i>，Y_j=<y₁, y₂, …, y_j>。 當i=0或j=0時，空序列是X_i和Y_j的最長公共子序列，故c[i,j]=0。 其他情況下，由定理可建立遞歸關系如下：

3. 代碼實現 #include <iostream>#include <string>#include <stdlib.h>
typedef enum _eDir{

LEFT_UP = 0,

UP,

LEFT,}eDir;

void PrintLCS(const char* pStr, int length1, int length2, int** b)
{

if(pStr == NULL || b == NULL || length1 <=0 || length2 <= 0)

return;

int i=length1, j=length2;

if(b[i][j] == LEFT_UP)

{

PrintLCS(b, pStr, i-1, j-1);

printf("%c ", pStr[i-1]);

}

else if(b[i][j] == UP)

PrintLCS(b, pStr, i-1, j);

else

PrintLCS(b, pStr, i, j-1);

}

void LCS_Length(const char* pStr1, const char* pStr2)
{
if (pStr1 == NULL || pStr2 == NULL)

throw new std::exception("Invalid Parameter!");

int str1Length = strlen(pStr1);

int str2Length = strlen(pStr2);

if(str1Length == 0 || str2Length == 0)

return;

int** c = (int**)new int[str1Length+1];

int** b = (int**)new int[str1Length+1];

for (int i=0; i<str1Length+1; ++i)

{
c[i] = new int[str2Length+1];

b[i] = new int[str2Length+1];

memset(c[i], 0, str2Length+1);

memset(b[i], 0, str2Length+1);

}

for (int i=1; i<=str1Length; ++i)

for (int j=1; j<=str2Length; ++j)

{

if (pStr1[i-1] == pStr2[j-1])

{

c[i][j] = c[i-1][j-1] + 1;

b[i][j] = LEFT_UP;

}

else if(c[i-1][j] >= c[i][j-1])

{

c[i][j] = c[i-1][j];

b[i][j] = UP;

}

else

{

c[i][j] = c[i][j-1];

b[i][j] = LEFT;

}

}

std::cout<<"str1:"<<pStr1<<std::endl<<"str2:"<<pStr2<<std::endl;

PrintLCS(pStr1, str1Length, str2Length, b);

std::cout<<std::endl;

for(int i=0; i<str1Length+1; ++i)

{

delete[] c[i];

delete[] b[i];

}

delete[] c;

delete[] b;

}

int main()

{

char* pStr1 = "ABCBDAB";

char* pStr2 = "BDCABAB";

LCS_Length(pStr1, pStr2);

return 0;

}
程序輸出：str1:ABCBDAB
str2:BDCABABB C B A B

本文出自 “redpaopaw” 博客，請務必保留此出處http://redpaopaw.blog.51cto.com/7900594/1299601