最长公共子序列（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和Y的任意LCS。

1. 如果，则且是和的一个LCS；
2. 如果，那么，意味着是和的一个LCS;
3. 如果，那么，意味着是和的一个LCS.

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

状态转移方程

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

序列增长过程

代码实现

#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

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