题目描述
又来写这个傻逼题目了
最长公共子序列的重要的特征
1、就是状态转移方程,这个是一个可以使用动态规划来解答的问题
状态转移方程1 在str1[i] == str2[j] 的情况下,说明字符相等,所以就采用dp[i][j] = dp[i-1][j-1] +1 , 来继承前面的最长子序列的状态
状态转移方程2 在str1[i]!=str2[j] 的情况下, 说明字符不相等,那么我们将忽略这个字符的情况, 同时我们会从str1和str2这两个字符串的记录里面去选择一个最长的记录 , 所以使用max函数来获得最长的记录的情况
状态转移方程为dp[i][j] = max(dp[i-1][j] , dp[i][j]),
2、避免在计算最长公共子序列(LCS)时重复计算同一个字符的问题
在动态规划算法中,每个 dp[i][j] 的值都是基于之前计算过的状态(dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1])来确定的。这个过程确保了算法在构建 LCS 时不会重复计算同一个字符。
当我们发现 str_1[i-1] 和 str_2[j-1] 相等时,这意味着这两个字符可以被添加到目前为止的 LCS 中。但是,这里的关键是 “目前为止” 的意思是直到 str_1 的前 i-1 个字符和 str_2 的前 j-1 个字符。这意味着我们只在这两个字符首次匹配时将它们纳入 LCS 中,而不是在之后的比较中再次计算它们。
让用一个例子来阐明这一点:
假设 str_1 = “abbc” 和 str_2 = “acbc”。在这个例子中,字符 b 和 c 在两个字符串中出现多次。但是,当我们使用动态规划算法时,每个 b 或 c 只被计算一次。这是因为当我们填充 dp 数组时,每个 dp[i][j] 的值都是基于之前的状态,而不是当前字符在整个字符串中的其他位置。
例如,当我们对比 str_1 的第二个字符 b (i=2) 和 str_2 的第三个字符 b (j=3) 时,我们会发现它们匹配,并将 dp[2][3] 设置为 dp[1][2] + 1。但这个匹配只是基于目前为止的字符串 “ab” 和 “acb”。算法不会考虑 str_1 或 str_2 中后面的 b 或 c 字符,直到算法在遍历过程中达到那些字符。
样例
//
// Created by asdfsa on 2024/1/10.
//
//状态转移方程的推导
//当 str_1[i-1] == str_2[j-1]:
//
//如果 str_1 的第 i 个字符和 str_2 的第 j 个字符相等(注意数组是从 0 开始索引的,所以我们比较 str_1[i-1] 和 str_2[j-1]),这意味着这两个字符可以成为当前考虑的两个子字符串的一个公共子序列的一部分。
//因此,我们可以把这两个字符添加到之前 str_1 的前 i-1 个字符和 str_2 的前 j-1 个字符形成的最长公共子序列的末尾。这就是为什么我们使用 dp[i-1][j-1] + 1,因为我们发现了一个额外的公共字符。
//当 str_1[i-1] != str_2[j-1]:
//
//如果当前字符不匹配,我们无法将它们同时添加到公共子序列中。
//因此,我们需要考虑两种情况来找到最长的公共子序列:一种是忽略 str_1 的当前字符(即 dp[i-1][j]),另一种是忽略 str_2 的当前字符(即 dp[i][j-1])。我们取这两种情况下的最长公共子序列长度的最大值。
#include <bits/stdc++.h>
int dp[1024][1024];
std::string lcs;
int sequence (std::string str_1, std::string str_2 ) {
// 循环
// i此处扮演的角色就是str_1字符串的某一个下标
// j扮演的角色如上,只不过是str_2字符串的某一个下标
// 遍历所有的字符串组合 O(n^2)的 时间复杂度
//为什么需要两次遍历两个字符串?
//我们需要考虑所有可能的子字符串组合来确定最长的公共子序列。这就意味着我们需要考虑 str_1 的每个前缀和 str_2 的每个前缀。
//双层循环确保我们对于每一对前缀(来自 str_1 和 str_2),都计算了其最长公共子序列的长度,并将这个信息存储在 dp 数组中。
//这样做确保了我们没有错过任何可能的子序列组合,从而能够准确地找到最长的公共子序列。
// 其实 i 是str_1 ; j 是 str_2, 其实可以这么去抽象理解这两个变量
for (int i = 0; i < str_1.size()+1; ++i) {
for (int j = 0; j < str_2.size()+1; ++j) {
if (i==0 || j==0) { // 这里代表任何一个字符对于一个空字符串 , 他们的最长子序列都是0
dp[i][j] = 0;
}else if (str_1[i-1] == str_2[j-1]) {
// 当字符相等的时候,当前字符的长度等于 当前字符之前的长度 加上1
// dp[i-1][j-1]代表的是当前字符的之前字符的长度
// 如果 str_1 的第 i 个字符和 str_2 的第 j 个字符相等(注意数组是从 0 开始索引的,所以我们比较 str_1[i-1] 和 str_2[j-1]),这意味着这两个字符可以成为当前考虑的两个子字符串的一个公共子序列的一部分。
//因此,我们可以把这两个字符添加到之前 str_1 的前 i-1 个字符和 str_2 的前 j-1 个字符形成的最长公共子序列的末尾。这就是为什么我们使用 dp[i-1][j-1] + 1,因为我们发现了一个额外的公共字符。
dp[i][j] = dp[i-1][j-1] + 1;
// 如果 A[i-1] == B[j-1],说明这个字符属于最长公共子序列。将该字符添加到 lcs 的前面,并将两个指针都向前移动一位(i-- 和 j--)
lcs.push_back(str_1[i-1]); // 这里只是为了获取lcs字符串
}else if (str_1[i-1] != str_2[j-1]) { // 不满足相等的条件
// 取两个字符串里面 当前字符最长的长度 , 等待下次相等的机会
// 这个题目是最长公共子序列, 又不是最长公共连续子序列,所以即使当前的字符不相等,也可以延长坐标等待下次字符相等
// 如果当前字符不匹配,我们无法将它们同时添加到公共子序列中。
// 因此,我们需要考虑两种情况来找到最长的公共子序列:一种是忽略 str_1 的当前字符(即 dp[i-1][j]),另一种是忽略 str_2 的当前字符(即 dp[i][j-1])。
// 我们取这两种情况下的最长公共子序列长度的最大值。
dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[str_1.size()][str_2.size()];
}
int main () {
std::string str_1, str_2;
int n_1, n_2;
// std::cin >> n_1; std::cin>>n_2;
std::cin >> str_1; std::cin >> str_2;
std::memset(dp, 0, sizeof (dp));
int len = sequence(str_1,str_2); //i 为str_1 j 为str_2
// 最长公共子序列
std::cout << len << std::endl;
// 打印字符
std::cout << lcs << std::endl;
}