首页 > 代码库 > 杭电1159 Common Subsequence【最长公共子序列】
杭电1159 Common Subsequence【最长公共子序列】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1159
解题思路：任意先给出两个字符串 abcfbc abfcab，用dp[i][j]来记录当前最长的子序列，则如果有x[i]与y[j]相等的话，则相当于公共子序列的长度在dp[i-1][j-1]上增加1,
如果x[i]与y[j]不相等的话，那么dp[i][j]就取得dp[i][j-1]和dp[i-1][j]中的最大值即可。时间复杂度为O(mn)
反思：大概思路想出来之后，因为dp数组赋初值调了很久，dp初值调出来之后，提交发现数组的长度开得不够，改二维数组的长度又改了好久，最后弄成全局变量，水过.
#include<stdio.h>#include<string.h>int dp[1001][1001];int max(int m,int n){ if(m>n) return m; else return n;}int main(){ char a[1000],b[1000]; int len1,len2; while(scanf("%s %s",&a,&b)!=EOF) { int i,j; len1=strlen(a); len2=strlen(b); for(i=0,j=0;j<=len2;j++) dp[i][j]=0; for(j=0,i=0;i<=len1;i++) dp[i][j]=0; for(i=0;a[i]!=‘\0‘;i++) { for(j=0;b[j]!=‘\0‘;j++) { if(a[i]==b[j]) { dp[i+1][j+1]=dp[i][j]+1; } else { dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]); } } } printf("%d\n",dp[i][j]); }}
杭电1159 Common Subsequence【最长公共子序列】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。