問題描述

??子序列是指，從序列中選出一些子元素，需滿足其前后關(guān)系與在原序列中相同；公共是指該序列同時(shí)是兩個(gè)序列的子序列。如兩個(gè)序列{4，2，1 ，6，5，8，13，18，9，5}和 {3，2，1，9，10，6，5，9}，{2，1}和{1，6，5}都是它們的公共子序列，顯然，這不是最長的。那么如何求解兩個(gè)序列的最長公共子序列（LCS）？

分析

??LCS具有最優(yōu)子結(jié)構(gòu)。令和為兩個(gè)序列，為X和Y的任意LCS。

1. 如果，則且是和的一個(gè)LCS；
2. 如果，那么，意味著是和的一個(gè)LCS;
3. 如果，那么，意味著是和的一個(gè)LCS.

??從上面分析可以看出，當(dāng)時(shí)，需要計(jì)算和的一個(gè)LCS；當(dāng)時(shí)，需要分別計(jì)算和的一個(gè)LCS、和的一個(gè)LCS。具有很明顯的狀態(tài)轉(zhuǎn)移含義，這些重疊的子問題可以用動(dòng)態(tài)規(guī)劃方法快速解決。
??根據(jù)LCS問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，有如下遞歸公式：

狀態(tài)轉(zhuǎn)移方程

??二維數(shù)組dp[i][j]表示序列與序列的最長公共子序列長度。根據(jù)題目中的數(shù)據(jù)，可以畫出如下序列增長過程，看出此動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為，因?yàn)槊總€(gè)表項(xiàng)的計(jì)算時(shí)間是.

序列增長過程

代碼實(shí)現(xiàn)

#include <iostream>
#include <cstring>

using namespace std;
const int maxn = 205;
int dp[maxn][maxn];
int arr1[maxn], arr2[maxn];

int main()
{
    int n, m;
    memset(dp,0,sizeof(dp));
    memset(arr1,0,sizeof(arr1));
    memset(arr2,0,sizeof(arr2));
    cin >> n; for(int i=1;i<=n;i++) cin>>arr1[i];
    cin >> m; for(int i=1;i<=m;i++) cin>>arr2[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(arr1[i]==arr2[j]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    cout << dp[n][m];
    return 0;
}

Tips

• 最長公共子序列和編輯距離，都是衡量字符串相似度的指標(biāo)，也都是動(dòng)態(tài)規(guī)劃算法的典型。