做网站多少钱西宁君博领先,兴国电商网站建设,网络公司网站官网,汕头网站建设平台题目六 最长公共子序列
题目描述
我们称一个字符的数组S为一个序列。对于另外一个字符数组Z,如果满足以下条件#xff0c;则称Z是S的一个子序列#xff1a;#xff08;1#xff09;Z中的每个元素都是S中的元素#xff08;2#xff09;Z中元素的顺序与在S中的顺序一致。…题目六 最长公共子序列
题目描述
我们称一个字符的数组S为一个序列。对于另外一个字符数组Z,如果满足以下条件则称Z是S的一个子序列1Z中的每个元素都是S中的元素2Z中元素的顺序与在S中的顺序一致。例如当S (E,R,C,D,F,A,K)时ECF和ER等等都是它的子序列。而RE则不是。 现在我们给定两个序列求它们最长的公共子序列的长度。
关于输入
一共两行分别输入两个序列
关于输出
一行输出最长公共子序列的长度。
例子输入
ABCBDAB
BDCABA例子输出
4
解题分析
这个问题的具体描述是给定两个序列求它们的最长公共子序列的长度。
程序的主要思路如下 首先程序读取两个字符串存储在word1和word2中然后计算它们的长度len1和len2。 然后程序初始化一个二维数组dpdp[i][j]表示word1的前i个字符和word2的前j个字符的最长公共子序列的长度。 程序遍历所有可能的i和j从0到len1和len2。 如果i或j为0那么dp[i][j]就等于0因为空字符串与任何字符串的最长公共子序列的长度都是0。 如果word1[i-1]等于word2[j-1]那么dp[i][j]就等于dp[i-1][j-1] 1。这是因为当前的字符可以加入最长公共子序列。 如果word1[i-1]不等于word2[j-1]那么dp[i][j]就等于dp[i][j-1]和dp[i-1][j]中的较大值。这是因为当前的字符不能同时加入最长公共子序列所以我们只能选择一个。 最后dp[len1][len2]就是word1和word2的最长公共子序列的长度。
这个程序的时间复杂度是O(n^2)因为它需要遍历所有可能的i和j。如果字符串的长度非常大那么这个程序可能会运行得比较慢。
代码实现
#include iostream
#include cstring
using namespace std;int dp[10005][10005];
char word1[10005],word2[10005];int main() {cinword1word2;int len1strlen(word1),len2strlen(word2);for(int i0;ilen1;i)for(int j0;jlen2;j){if(i0 || j0){dp[i][j]0;}else{if(word1[i-1]word2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]max(dp[i][j-1],dp[i-1][j]);}}}coutdp[len1][len2]endl;return 0;
}使用记忆搜索法解决问题
#include iostream
#include cstring
using namespace std;int dp[10005][10005];
char word1[10005],word2[10005];int f(int i,int j){if(i0 || j0){return 0;}if(dp[i][j]){return dp[i][j];}if(word1[i-1]word2[j-1]){dp[i][j]f(i-1,j-1)1;}else{dp[i][j]max(f(i-1,j),f(i,j-1));}return dp[i][j];
}int main() {cinword1word2;int len1strlen(word1),len2strlen(word2);coutf(len1,len2)endl;return 0;
}
