最长公共子序列-动态规划-openjudge
【摘要】 序列str1和序列str2长度分别为m和n；创建1个二维数组str[m][n]来保存结果，并初始化为0；m和n分别从0开始，m++，n++循环：（默认字符串均不为空）如果str1[m] == str2[n]，则L[m,n] = L[m - 1, n -1] + 1；如果str1[m] != str2[n]，则L[m,n] = max{L[m,n - 1]，L[m - 1, n]}最后从L...
序列str1和序列str2
长度分别为m和n；
创建1个二维数组str[m][n]来保存结果，并初始化为0；
m和n分别从0开始，m++，n++循环：
（默认字符串均不为空）
如果str1[m] == str2[n]，则L[m,n] = L[m - 1, n -1] + 1；
如果str1[m] != str2[n]，则L[m,n] = max{L[m,n - 1]，L[m - 1, n]}
最后从L[m,n]中的数字一定是最大的，且这个数字就是最长公共子序列的长度
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
char str1[205];
char str2[205];
int str[205][205];
while(scanf("%s%s",str1+1,str2+1)!=EOF)
{
int length1=strlen(str1+1);
int length2=strlen(str2+1);
memset(str,0,sizeof(str));
for(int i=1; i<=length1; i++)
{
for(int j=1; j<=length2; j++)
{
if(str1[i]==str2[j])
str[i][j]=str[i-1][j-1]+1;
else
str[i][j]=max(str[i-1][j],str[i][j-1]);
}
}
printf("%d\n",str[length1][length2]);
}
return 0;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）