我们给了两个字符串,假设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