首页 > 代码库 > uva--10405Longest Common Subsequence+dp
uva--10405Longest Common Subsequence+dp
经典的最长公共子序列问题。
要注意的是题目中的输入会包含空格的情况,所以要用gets实现输入。
代码如下:
<span style="font-size:18px;">#include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[1100][1100]; int main() { char str1[1100],str2[1100]; int i,j; while(gets(str1+1)) { gets(str2+1); int len1=strlen(str1+1); int len2=strlen(str2+1); memset(dp,0,sizeof(dp)); for(i=1;i<=len1;i++) for(j=1;j<=len2;j++) { if(str1[i]==str2[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } int ans=0; for(i=1;i<=len1;i++) for(j=1;j<=len2;j++) ans=max(ans,dp[i][j]); printf("%d\n",ans); } return 0; }</span>
uva--10405Longest Common Subsequence+dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。