首页 > 代码库 > nyist oj 36 最长公共子序列 (动态规划基础题)
nyist oj 36 最长公共子序列 (动态规划基础题)
最长公共子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。
tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。- 输入
- 第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000. - 输出
- 每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。
- 样例输入
2 asdf adfsd 123abc abc123abc
- 样例输出
3 6
- 来源
- 经典
- 上传者
hzyqazasdf
开始要刷动态规划的题啦;从入门题练练手,http://blog.csdn.net/v_july_v/article/details/6695482 (关于算法的讲解)参考了大神的博客,看了对这个内容有了那么一点点了解了吧,直接用这个题目练练手。主要要掌握动态规划的这种思想!
动态规划思想,主要是递推公式,求最优化问题,保证当时位置是最优,分治的思想;
这个题目的思路就是,从最后一个字符开始,如果两个字符串的最后一个字符相等,说明最后一个字符,在最长的公共序列里面,最长公共序列的前一个,肯定也是两个字符串的最长公共子序列,递推公式就是 dp[i][j]=dp[i-1][j-1]+1;
其他情况,如果不相等就是 dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
第一次水过的代码;
#include <cstdio> #include <cstring> #define max(a, b) a > b ? a : b using namespace std; const int maxn=1001; int dp[maxn][maxn];//保存当前位置最长公共子序列的个数 char s1[maxn],s2[maxn]; int main() { int n; int len1,len2; scanf("%d",&n); getchar(); while(n--) { memset(dp,0,sizeof(dp)); scanf("%s%s",s1,s2); len1=strlen(s1); len2=strlen(s2); for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1])//先前这个地方写成s1[i]==s2[j]就一直wa 不知道为什么,样例都能过 dp[i][j]=dp[i-1][j-1]+1; else dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } printf("%d\n",dp[len1][len2]); } return 0; }
看到别人可以直接用一维数组来做,进行了内存上的优化;值得学习一下;#include <stdio.h> #include <string.h> char s1[1001], s2[1001]; int dp[1001], t, old, tmp; int main(){ scanf("%d", &t); getchar(); while(t--){ gets(s1); gets(s2); memset(dp, 0, sizeof(dp)); int lenS1=strlen(s1), lenS2=strlen(s2); for(int i=0; i<lenS1; i++){ old=0; //若s1[i]==s2[j], dp[i][j] = dp[i-1][j-1]+1 //否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1]) //此处进行了空间优化,old 代表 dp[i-1][j-1] //dp[j-1] 代表 dp[i][j-1], dp[j] 代表 dp[i-1][j] for(int j=0; j<lenS2; j++){ tmp = dp[j]; if(s1[i]==s2[j]) dp[j] = old+1; else if(dp[j-1]>dp[j])dp[j]=dp[j-1]; old = tmp; } } printf("%d\n", dp[lenS2-1]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。