我们给了两个字符串，假设str1和str2包含字符，任务是计算两个字符串中的公共子序列。在下面的程序中，我们正在使用动态编程，为此，我们需要知道什么是动态编程以及可以使用哪些问题。
动态编程方法类似于将问题分解为越来越小的可能的子问题的“分而治之”的方法。但是与分而治之不同，这些子问题不是独立解决的。相反，这些较小的子问题的结果将被记住并用于相似或重叠的子问题。
在有问题的地方使用动态编程，可以将其划分为相似的子问题，以便可以重用其结果。通常，这些算法用于优化。在解决现有子问题之前，动态算法将尝试检查先前解决的子问题的结果。将子问题的解决方案组合在一起，以获得最佳解决方案。
所以我们可以说-
Input − string str1 = “abc” String str2 = “ab”Output − count is 3
说明-从给定的字符串中形成的常见子序列为：{'a'，'b'，'ab'}。
Input − string str1 = “ajblqcpdz” String str2 = “aefcnbtdi”Output − count is 11
常见子序列为-从给定的字符串中形成的常见子序列为：{“ a”，“ b”，“ c”，“ d”，“ ab”，“ bd”，“ ad”，“ ac”，“ cd”， “ abd”，“ acd”}
输入两个字符串，假设为str1和str2。
使用该length()函数计算给定字符串的长度，该函数将根据字符串中的字符数返回一个整数值，并将其存储在str1的len1和str2的len2中。
创建一个二维数组来实现动态编程，假设arr [len1 + 1] [len2 + 1]
从0开始直到i小于len1的循环
在循环内，从j到0开始另一个循环，直到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