最长公共子序列问题（动态规划）_最长公共子序列 动态规划

动态规划（Dynamic Programming，简称DP）是一种在有重叠子问题和最优子结构的问题上最常用的优化算法。经过长时间的发展，DP算法已经成为了计算机科学中非常重要的算法之一。在算法设计的过程中，我们常常需要将一个大规模的问题拆分成一系列子问题，这些子问题解决的多了，最后大问题就解决了。

 

一、基本概念

本篇博客将介绍使用DP算法解决的一个典型问题：最长公共子序列（Longest Common Subsequence，简称LCS）。LCS问题是一种经典的算法问题，在许多应用领域都有广泛的应用。它的基本思想是寻找两个字符串中都存在的最长子序列，这个最长子序列可以不是连续的，但是要保证其相对顺序一样。（注意，这里是子序列，而不是子串，子序列可以不连续，而子串是连续的）

以S = “ACCGA” 和T = “CCGAA”为例，其LCS为：”CCGA”，长度为4。

特征分析

最长公共子序列是指两个序列中最长的子序列，且两个子序列在原序列中的顺序都是一致的，但不一定连续。最长公共子序列就是在两个序列中，找出能够匹配的最长子序列。具有如下特征：

1. 长度：最长公共子序列的长度最大为两个序列的最小长度，如果两个序列完全相同，则它们的最长公共子序列即为它们本身。

2. 顺序：最长公共子序列中的子序列在原序列中的顺序一致。

3. 相同元素：最长公共子序列中的子序列所包含的元素必须在两个原序列中都存在。

4. 不连续性：最长公共子序列不需要在原序列中连续出现。

看看下面的例子：

这部分和下面的递归公式参考自文章：动态规划 最长公共子序列 过程图解_Running07的博客-CSDN博客

设A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”为它们的最长公共子序列。不难证明有以下性质：

如果am=bn，则zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一个最长公共子序列；

如果am!=bn，则若zk!=am，蕴涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一个最长公共子序列；

如果am!=bn，则若zk!=bn，蕴涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，   b(n-1)”的一个最长公共子序列。

我们可以得到递归公式

用dp[i][j]表示Si 和 Tj 的LCS的长度。其中S = {s1 ... sm}，T ={t1...tn}，Si = {s1 ... si}，Tj={t1... tj}。可得递归公式如下：

二、程序实现：

考虑求解上述问题，我们首先想到的是，将输入的两个字符串以及它们的长度作为DP算法的输入参数。

dp[i][j]表示在字符串S中前i个元素和字符串T中前j个元素的公共子序列的长度。

首先我们需要进行一定的初始化，以保证程序正常运行，代码如下：

int dp[1010][1010]; 
int LCS(char* s1, char* s2, int l1, int l2) { 
    memset(dp, 0, sizeof(dp)); 
    for (int i = 1; i <= l1; i++) { 
        for (int j = 1; j <= l2; j++) { 
            if (s1[i] == s2[j]) { 
                dp[i][j] = dp[i - 1][j - 1] + 1; 
            } 
            else { 
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 
            } 
        } 
    } 
    return dp[l1][l2]; 
}

上述代码中，我们通过二重循环来遍历字符串S和字符串T，并根据不同的情况进行相应的处理。

若S[i]等于T[j]，那么dp[i][j]的值将会是dp[i - 1][j - 1]的值加1；

否则，dp[i][j]的值将会是dp[i - 1][j]和dp[i][j - 1]的较大值。

根据转移方程，我们可以看到dp[i][j]涉及到了dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]三个值。因此，在算法实现过程中，我们需要先计算出左上方的dp值，再用dp值更新左下方和右上方的dp值。

最后，输出dp矩阵中最右下角的值即可得到最长公共子序列的长度。时间复杂度为O(N^2)。

三、例子

题目来源：【模板】最长公共子序列 - 洛谷

题目描述

给出 1,2,…,n 的两个排列 P1 和P2 ，求它们的最长公共子序列。

输入格式

第一行是一个数 n。

接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

输入输出样例

输入

5 
3 2 1 4 5
1 2 3 4 5

输出

3

我的代码

#include<bits/stdc++.h>
using namespace std;
#define N 100000+5
int main(){
	long long dp[1010][1010]; 
	long long s1[N], s2[N];
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>s1[i];
	}
	for(long long i=1;i<=n;i++){
		cin>>s2[i];
	}
    memset(dp, 0, sizeof(dp)); 
    for (int i = 1; i <= n; i++) { 
        for (int j = 1; j <= n; j++) { 
            if (s1[i] == s2[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][n]; 
    return 0;
 
} 

但是上面写的代码如果在洛谷平台评测会有部分样例超时，所以如果想把这个题拿满分，还需要对其进行优化，比如，可以使用二分查找的思想，可以去参考这篇文章：

【ACM程序设计】动态规划 第二篇 LCS&LIS问题 (bbsmax.com)

总结：

本篇博客介绍了动态规划算法的一个典型应用：最长公共子序列问题。通过构建状态转移方程，我们可以将这个问题用DP算法解决。在算法实现过程中，我们注意到DP算法的时间和空间复杂度都是比较高的，因此，在实际应用中需要考虑到算法的效率和可优化性，以减少计算时间。