一、問題定義

1.1 子序列

子序列是給定序列中在任意位置去掉任意多個字符后得到的結(jié)果。例如：

給定序列$X$：

$X：ABCBDAB$

$X$的子序列：

$X_1：ABCBDAB$

$X_2：ABCB$

$X_3：ACBB$

1.2 公共子序列

給定兩個序列$X$和$Y$：

$X：ABCBDAB$

$Y：BDCABA$

公共子序列示例：

$X_1=Y_1=CA$

$X_2=Y_2=ABA$

$X_3=Y_3=BCAB$

1.3 問題形式化定義

最長公共子序列問題：

輸入：

\quad 序列$X=<x_1,x_2,...,x_n>$和序列$Y=<y_1,y_2,...,y_m>$

輸出：

\quad 求解一個公共子序列$Z=<z_1,z_2,...,z_l>$

\quad \quad \quad 優(yōu)化目標(biāo)：$max|Z|$

\quad \quad \quad 約束條件：$<z_1,z_2,...,z_l>=<x_{i_1},x_{i_2},...,x_{l_1}>=<y_{j_1},y_{j_2},...,y_{j_l}>$，其中

二、求解策略

給定兩個序列$X$和$Y$：

$X：ABCBDAB$

$Y：BDCABA$

其最長公共子序列$Z=BDAB$，觀察可以發(fā)現(xiàn)，其后3位為長度為3的最長公共子序列，其后2位為長度為2的最長公共子序列，最后一位為長度為一的最長公共子序列。這便啟示我們可能存在最優(yōu)子結(jié)構(gòu)和重疊子問題，可以采用動態(tài)規(guī)劃進(jìn)行求解。

2.1 分析問題結(jié)構(gòu)

形式化給出問題表示：

• $C[i,j]$：$X[\mathrm{1..}i]$和$Y[\mathrm{1..}j]$的最長公共子序列長度

明確原始問題：

• $C[n,m]$：$X[\mathrm{1..}n]$和$Y[\mathrm{1..}m]$的最長公共子序列長度

2.2 建立遞推關(guān)系

對于給定序列：

對于末尾來說，有兩種情況：

①$x_i=y_j$

此時，
$$C[i,j]=max?\begin{array}{cc}C[i?1,j?1]+1& ①\\ C[i?1,j]& ②\\ C[i,j?1]& ③\end{array}$$
但是， ① ≥ m a x { ②，③ } {①\ge max\left \{ ②，③ \right \} } ①≥max{②，③}，因此，
$$C[i,j]=C[i?1,j?1]+1$$

②$x_i\ne y_j$

此時，
$$C[i,j]=max\{\begin{array}{cc}C[i?1,j]& ①\\ C[i,j?1]& ②\end{array}$$
綜上所述，得到遞推關(guān)系式：
C [ i , j ] = { C [ i ? 1 , j ? 1 ] + 1 x i = y j m a x { C [ i ? 1 , j ] , C [ i , j ? 1 ] } x i ≠ y j C[i,j]=\left\{\begin{matrix} C[i-1,j-1]+1 & x_i=y_j\\ max\left\{ C[i-1,j],\\ C[i,j-1] \right\} & x_i\ne y_j\\ \end{matrix}\right. C[i,j]={C[i?1,j?1]+1max{C[i?1,j],C[i,j?1]}?xi?=yj?xi?=yj??

2.3 自底向上計算

（1）初始化

當(dāng)其中一段序列長度為0時，最長公共子序列長度為0，即：$C[i,0]=C[0,j]=0$

（2）依照遞推公式計算

2.4 追蹤最優(yōu)方案

構(gòu)造追蹤數(shù)組$rec[\mathrm{1..}n]$，用來記錄子問題的來源：
$$rec[i,j]=?\begin{array}{cc}LU& ifC[i,j]=C[i?1,j?1]+1\\ U& ifC[i,j]=C[i?1,j]\\ L& ifC[i,j]=C[i,j?1]\end{array}$$
（使用$U$代表來自上方，$L$代表來自左方，$LU$代表來自左上角）

當(dāng)左值和上值相等時，任取其一即可。

從右下角開始追蹤，如果其值為$L$，則向左移動1格，$U$則向上移動一格，$LU$向左上角移動一格。當(dāng)且僅當(dāng)$rec[i,j]=LU$時，$X[i]=Y[j]$為最長公共子序列中的一個字符，記錄下來。如此尋找，直至抵達(dá)$rec$數(shù)組的邊界。

2.5 算法實例

給定序列$X$和$Y$：

初始化輔助數(shù)組：

計算完畢：

追蹤最優(yōu)方案：

得到最長公共子序列$BCBA$

三、算法分析

3.1 偽代碼

3.2 時間復(fù)雜度

時間復(fù)雜度$O(nm)$文章來源地址http://www.zghlxwxcb.cn/news/detail-743439.html

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