最长公共子序列（LCS）——动态规划

问题描述

子序列是指，从序列中选出一些子元素，需满足其前后关系与在原序列中相同；公共是指该序列同时是两个序列的子序列。如两个序列{4，2，1 ，6，5，8，13，18，9，5}和 {3，2，1，9，10，6，5，9}，{2，1}和{1，6，5}都是它们的公共子序列，显然，这不是最长的。那么如何求解两个序列的最长公共子序列（LCS）？

分析

LCS具有最优子结构。令 $X=<x_{1}, x_{2}, ..., x_{m}>$ 和 $Y=<y_{1}, y_{2}, ..., y_{n}>$ 为两个序列， $Z=<z_{1}, z_{2}, ..., z_{k}>$ 为X和Y的任意LCS。

如果 $x_{m}=y_{n}$ ，则 $z_{k}=x_{m}=y_{n}$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个LCS；
如果 $x_{m}≠y_{n}$ ，那么 $z_{k}≠x_{m}$ ，意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个LCS;
如果 $x_{m}≠y_{n}$ ，那么 $z_{k}≠y_{n}$ ，意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的一个LCS.

从上面分析可以看出，当 $x_{m}=y_{n}$ 时，需要计算 $X_{m-1}$ 和 $Y_{n-1}$ 的一个LCS；当 $x_{m}≠y_{n}$ 时，需要分别计算 $X_{m-1}$ 和 $Y$ 的一个LCS、 $X$ 和 $Y_{n-1}$ 的一个LCS。具有很明显的状态转移含义，这些重叠的子问题可以用动态规划方法快速解决。
根据LCS问题的最优子结构性质，有如下递归公式：

状态转移方程

二维数组dp[i][j]表示序列 $<x_{1}, x_{2}, ..., x_{i}>$ 与序列 $<y_{1}, y_{2}, ..., y_{j}>$ 的最长公共子序列长度。根据题目中的数据，可以画出如下序列增长过程，看出此动态规划算法的时间复杂度为 $O(nm)$ ，因为每个表项的计算时间是 $O(1)$ .

序列增长过程

代码实现

#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

最长公共子序列和编辑距离，都是衡量字符串相似度的指标，也都是动态规划算法的典型。

最后编辑于：2019.11.08 15:04:53