使用 C++ 计算两个字符串中的公共子序列
给定两个字符串，假设 str1 和 str2 包含字符，任务是计算两个字符串中的公共子序列。在下面的程序中，我们使用动态规划，为此我们需要知道什么是动态规划以及它可以用于哪些问题。
动态规划方法类似于分而治之，将问题分解为更小的可能子问题。但与分而治之不同的是，这些子问题不是独立解决的。相反，这些较小子问题的结果会被记住并用于类似或重叠的子问题。
当我们遇到可以分为类似子问题的问题时，会使用动态规划，以便可以重复使用它们的结果。大多数情况下，这些算法用于优化。在解决手头的子问题之前，动态算法将尝试检查先前解决的子问题的结果。子问题的解决方案被组合起来以获得最佳解决方案。
所以我们可以说−
输入 − 字符串 str1 = “abc” 字符串 str2 = “ab” 输出 − 计数为 3
解释 − 从给定的字符串形成的公共子序列是:{‘a’, ‘b’ , ‘ab’}。
输入 −字符串 str1 = “ajblqcpdz” 字符串 str2 = “aefcnbtdi” 输出 − 计数为 11
公共子序列是 − 从给定的字符串形成的公共子序列是:{ “a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ac”, “cd”, “abd”, “acd”
以下程序中使用的方法如下
输入两个字符串，假设为 str1 和 str2。
使用 length() 函数计算给定字符串的长度，该函数将根据字符串中的字符数返回一个整数值，并将其存储在 str1 的 len1 中，以及 str2 的 len2 中。
创建一个二维数组来实现动态规划，假设为 arr[len1+1][len2+1]
开始循环，使 i 从 0 变为 i 直到 i 小于 len1
在循环内部，开始另一个循环，使 j 从 0 变为 j 直到 j 小于 len2
在循环内部，检查 IF str1[i-1] = str2[j-1]，然后设置arr[i][j] = 1 + arr[i][j-1] + arr[i-1][j]
否则，设置 arr[i][j] = arr[i][j-1] + arr[i-1][j] = arr[i-1][j-1]
返回 arr[len1][len2]
打印结果。
示例
#include <iostream>
using namespace std;
// 计算字符串中的子序列数
int countsequences(string str, string str2){
int n1 = str.length();
int n2 = str2.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++){
for (int j = 0; j <= n2; j++){
dp[i][j] = 0;
}
}
// 对于 str 的每个字符
for (int i = 1; i <= n1; i++){
// 对于 str2 中的每个字符
for (int j = 1; j <= n2; j++){
// 如果两个字符相同
// 字符串
if (str[i - 1] == str2[j - 1]){
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
}
else{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}
}
return dp[n1][n2];
}
int main(){
string str = "abcdejkil";
string str2 = "bcdfkaoenlp";
cout <<"count is: "<<countsequences(str, str2) << endl;
return 0;
}
示例
如果运行上述代码，我们将得到以下输出 −
count is: 51
