最长公共子序列： Python, C++ 例如：
陈莎拉
什么是最长公共子序列？
最长公共子序列 (LCS) 是指给定两个字符串、模式或对象序列，你需要从中找到两个字符串或序列中元素顺序相同的最长子序列。
例如：
例如，我们提供了两个字符串。假设：
图案_1 = “RGBGARGA”
模式 2 = “BGRARG”
- 根据模式1，可以生成类似“RGB”、“RGGA”、“RGAR”这样的序列。创建序列时，需要保持字符串中每个字符的相对位置。
- 从模式 2 出发，我们可以生成类似“BGR”、“BRAG”、“RARG”这样的序列。只要序列保持与原始字符串的相对位置不变，就可以生成这些序列。
相对位置这个术语意味着顺序。
例如，“BRG”是一个有效的序列，因为在原始字符串模式_2中，“B”出现在最前面，“R”出现在最前面，“G”出现在最前面。但是，如果序列是“RBRG”，则它无效，因为在原始字符串（模式_2）中，“B”出现在最前面。
我们有两个选择可以从给定的两个序列或数组中找到最长公共子序列。
- 朴素方法
- 动态规划解决方案：最长公共子序列也称为LCS。
朴素解法时间复杂度较高，并非最优解。利用动态规划（DP）方法，我们可以克服时间复杂度问题。
朴素方法
朴素方法是一种解决问题的简单方法，它忽略了时间复杂度和其他优化因素。在大多数情况下，它包含“暴力搜索”、多个循环和递归调用。“暴力搜索”指的是遍历给定问题的所有可能模式。
例如：
从上面的 pattern1 和 pattern2 的例子来看，我们假设 pattern1 的长度为 m，pattern2 的长度为 n。为了检查每种可能的情况，我们需要用 pattern1 评估 pattern2 的每个可能子序列。
这是一个简单的四字母字符串“ABCD”。例如，我们需要从“ABCD”中创建一个序列。我们可以选择取一个字符，也可以选择不取任何字符。这意味着，对于每个字符，我们有两种选择：
- 该字符将被添加到子序列中。
- 该字符将不会添加到子序列中。
这里，图像显示了我们可以从字符串“ABCD”创建的所有序列。
包含 1 个字符的序列：
含有 2 个字符的序列：
含有 3 个字符的序列：
从上图可以看出，共有 14 个序列。如果我们不取任何字母，也就是一个空字符串，那么序列总数将为 15 个。此外，字符串“ABCD”本身也是一个序列。因此，序列总数为 16 个。
因此，可以从“ABCD”生成 2^4 或 16 个子序列。然后，长度为 m 总共有 2^m 个子序列。
对于每个子序列，我们需要检查它是否符合整个模式2。这将耗费O(n)的时间。O(n)表示复杂度函数，用于计算执行所需的时间。
因此，总时间复杂度变为 O(n*2^m)。 对于上面我们看到的例子，m=8，n=5。
以下是朴素方法的步骤：
步骤1） 从模式1中取出一个序列。
步骤2） 将步骤 1 中的序列与模式 2 进行匹配。
步骤3） 如果匹配，则保存子序列。
步骤4） 如果模式 1 中还有剩余序列，则再次执行步骤 1。
步骤5） 打印最长子序列。
最优子结构
术语“最优子结构”指的是可以通过求解子问题找到最优解。例如，在上面的例子中，我们有模式1和模式2。
步骤1） 从每个图案中取出前两个字符。
步骤2） 从每个模式中取出第三到第五个字符。
步骤3） 对其余字符继续进行类似操作。
LCS 问题的递归结构
我们找到子串（由原始字符串生成的字符串）的最近公共子序列（LCS）。然后，我们记录所有子串的LCS的长度。
现在，这是另一个有趣的特性 交叠ping 子问题据说一个问题存在重叠。ping 如果问题陈述可以分解成若干个小的子问题，并在程序中多次使用，则称为子问题。
下图显示递归算法多次调用具有相同参数的函数。
例如，观察递归树。在深色框中，您可以注意到重叠部分。ping 子问题。（“RG”、“RA”）、（“RG”“R”）等被多次调用。
为了优化这一点，我们采用了以下方法： 动态编程 （DP）。
最长公共子序列的递归方法
上图所示为递归方法。每个递归函数都有一个基本情况，用于中断递归或从其堆栈返回。
在这个实现中，我们将使用一个基本情况。因此， 算法 就像下面这样：
- 如果最后一个元素之前的所有元素都有匹配项，则将长度加一并返回。
- 向函数传递两个模式，并取返回值的最大值。
- 如果一个模式的长度为零，则没有子序列可供比较。在这种情况下返回 0。这是递归的基本情况。
昵称 Code:
def lcs: input: pattern_1, pattern_2, len_1, len_2 if len_1 or len_2 is zero: return 0 if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]: return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1) else: return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
在实施 C++
#include<iostream> #include<bits/stdc++.h> using namespace std; int lcs(string pattern_1, string pattern_2, int len_1, int len_2) { if (len_1 == 0 || len_2 == 0) return 0; if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) { return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1); } else { return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1)); } } int main() { string pattern_1, pattern_2; pattern_1 = "RGBGARGA"; pattern_2 = "BGRARG"; cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl; }
输出：
Length of LCS is: 5
在实施 Python
def lcs(pattern_1, pattern_2, len_1, len_2): if len_1 == 0 or len_2 == 0: return 0 if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]: return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1) else: return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1)) pattern_1 = "RGBGARGA" pattern_2 = "BGRARG" print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))
输出：
Length of LCS is: 5
最长公共子序列（LCS）的动态规划方法
动态规划是指对普通递归方法进行优化。例如，如果我们观察递归或朴素方法的程序图，会发现其中包含多个相同的函数调用。动态规划方法将所有计算过程记录在一个数组中，并在需要时重复使用。
我们将使用一个维度为 m×n 的二维数组，其中 m 和 n 分别是 pattern1 和 pattern2 的长度。 二维阵列我们可以使用列表数据结构 Python 或向量/数组数据结构 C++.
昵称 Code 对于使用动态规划的LCS：
LCS(pattern_1, pattern_2): m = length of pattern_1 + 1 n = length of pattern_2 + 1 dp[n][m] for i in range 0 to n + 1: for j in range 0 to m + 1: if i or j equals to 0: dp[i][j] = 0 else if pattern_1[i] == pattern_2[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[n][m]
以下是用作动态规划方法的二维数组数据结构的 LCS 表。
让我们来探讨一下我们在这里使用的逻辑。步骤如下：
步骤1） 如果 i 或 j 为零，则表示我们从给定的两个字符串中取出一个空字符串，并尝试找到它们的公共子序列。然而，由于我们取出的子字符串为空，因此子序列的长度为 0。
步骤2） 如果两个字符匹配，我们将通过递增先前计算的 LCS 来将该值赋给 (i,j) 索引，该 LCS 存在于 (i-1,j-1) 索引（来自上一行）中。
步骤3） 如果匹配失败，则取相邻两个索引的最大最小公倍数（LCS）。这样，我们需要填充二维数组中的所有值。
步骤4） 最后，我们将返回二维数组最后一个单元格的值。
基本上，二维数组中的所有值都包含公共子序列的长度。其中，最后一个单元格包含最长公共子序列的长度。
在实施 C++
#include<iostream> using namespace std; int lcs(string pattern_1, string pattern_2) { int m = pattern_1.size(); int n = pattern_2.size(); // dp will store solutions as the iteration goes on int dp[n + 1][m + 1]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < m + 1; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (pattern_2[i - 1] == pattern_1[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; } int main() { string pattern_1 = "RGBGARGA"; string pattern_2 = "BGRARG"; cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl; }
输出：
Length of LCS: 5
在实施 Python
def lcs(pattern_1, pattern_2): m = len(pattern_1) n = len(pattern_2) # dp will store solutions as the iteration goes on dp = [[None] * (n + 1) for item in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: dp[i][j] = 0 elif pattern_1[i - 1] == pattern_2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n] pattern_1 = "RGBGARGA" pattern_2 = "BGRARG" print("Length of LCS: ", lcs(pattern_1, pattern_2))
输出：
Length of LCS: 5
因此，两个字符串都有长度为 5 的最长公共子序列。
简而言之，在动态规划方法中，我们只是对每个任务计算一次。而在递归方法中，可能会出现重叠。ping 子问题。
在这个动态规划算法中，我们使用一个二维矩阵。将给出两个字符串（假设两个字符串的长度均为 n）。那么数组中所需的空间为 nx n。如果字符串足够大，我们将需要一个内存优化版本的 DP 解决方案。
代码中采用的简化逻辑是：
- 声明一个二维数组DP[m][n]。
- 用0填充DP数组的第一行和第一列。
- 取i和j进行迭代。
- 如果 pattern1[i] 等于 pattern2[j]，则更新 DP[i][j] = DP[i-1][j-1] + 1。
- 如果 pattern1[i] 不等于 pattern2[j]，则 DP[i][j] 将是 DP[i-1][j] 和 DP[i][j-1] 中的最大值。
- 继续，直到 i 和 j 达到 m 和 n。
- 最后一个元素 DP[m-1][n-1] 将包含长度。
这里，它被称为 DP[m-1][n-1]，因为数组索引从 0 开始。
