首页 > 代码库 > 【noi 2.6_1808】最长公共子序列（DP）
【noi 2.6_1808】最长公共子序列（DP）
题意：给2个字符串求其最大公共子序列的长度。
解法：这个和一般的状态定义有点不一样，f[i][j]表示 str 前i位和 str2 前j的最大公共子序列的长度，而不是选 str 的第i位和 str2 的第j位。
仔细想想就可以知道只表示“前...”的状态可以保证每次拓展答案时，之前的状态已经保证了“公共”，因此str[i]==str2[j]时f[][]+1也不会错。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int L=210; 8 int f[L][L]; 9 char str[L],str2[L];10 11 int mmax(int x,int y) {return x>y?x:y;}12 int main()13 {14 while (scanf("%s%s",str+1,str2+1)!=EOF)15 {16 int len=strlen(str+1),len2=strlen(str2+1);17 f[0][0]=0;18 for (int i=1;i<=len;i++)19 for (int j=1;j<=len2;j++)20 {21 f[i][j]=mmax(f[i-1][j],f[i][j-1]);22 if (str[i]==str2[j]) f[i][j]=mmax(f[i][j],f[i-1][j-1]+1);23 }24 printf("%d\n",f[len][len2]);25 }26 return 0;27 }
【noi 2.6_1808】最长公共子序列（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。