HDU 1159 Common Subsequence 最长公共子序列
2024-10-07 03:56:19
HDU 1159 Common Subsequence 最长公共子序列
题意
给你两个字符串,求出这两个字符串的最长公共子序列,这里的子序列不一定是连续的,只要满足前后关系就可以。
解题思路
这个当然要使用动态规划了。
这里\(dp[i][j]\)代表第一个串的前\(i\)个字符和第二个串的前\(j\)个字符中最长的公共子序列的最长长度,递推关系如下:
\[d[i][j]= \begin{cases} dp[i-1][j-1]+1 & \text{if} &str1[i]==str2[j] \\ max(dp[i-1][j], dp[i][j-1]) & \text{if } &str1[i]!=str2[j] \end{cases}
\]
\]
优化:这里我们看到,每次的\(dp[i][j]\)的更新仅需要当前前一行\(dp[i-1][j-1]\),\(dp[i-1][j]\)的值还有当前行的\(dp[i][j-1]\)的值,所以我们可以进行空间优化,开辟空间为\(dp[maxn][2]\)
代码实现
//带有空间优化的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
int dp[maxn][2];
char s1[maxn], s2[maxn];
int main()
{
int len1, len2;
while(scanf("%s %s", s1+1, s2+1)!=EOF)
{
memset(dp, 0, sizeof(dp));
len1=strlen(s1+1);
len2=strlen(s2+1);
int flag=0;
for(int i=1; i<=len1; i++)
{
for(int j=1; j<=len2; j++)
{
if(s1[i]==s2[j])
dp[j][flag]=dp[j-1][!flag]+1;
else
dp[j][flag]=max(dp[j][!flag], dp[j-1][flag]);
}
flag=!flag;
}
printf("%d\n", dp[len2][!flag]);
}
return 0;
}
//没有空间优化的代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
int dp[maxn][2];
char s1[maxn], s2[maxn];
int main()
{
int len1, len2;
while(scanf("%s %s", s1+1, s2+1)!=EOF)
{
memset(dp, 0, sizeof(dp));
len1=strlen(s1+1);
len2=strlen(s2+1);
int flag=0;
for(int i=1; i<=len1; i++)
{
for(int j=1; j<=len2; j++)
{
if(s1[i]==s2[j])
dp[j][i%2]=dp[j-1][(i-1)%2]+1;
else
dp[j][i%2]=max(dp[j][(i-1)%2], dp[j-1][i%2]);
}
}
printf("%d\n", dp[len2][len1%2]);
}
return 0;
}
最新文章
- 3D旋转菜单
- size_t和size_type
- 如何在Winform界面中设计图文并茂的界面
- windows 7 安装 telnet
- hive复杂类型与java类型的对应
- php 判断table 是否存在 根据返回值继续下一步的操作
- MySQL 库大小、表大小、索引大小查询命令
- jQuery.each的function中有哪些参数(可以大概理解function中的参数问题)
- Python多线程和多进程谁更快?
- 使用github出了些问题?fatal: unable to access;Failed connect to github.com:8087;
- 201521123084 《Java程序设计》第3周学习总结
- YYHS-NOIP模拟赛-gcd
- win10系统搭建虚拟机:VMware Workstation Player 12环境+Ubuntu Kylin 16.04 LTS系统
- Mybatis学习笔记二
- nohup在linux中的挂起
- Git—分支管理
- 求最小环 —— 并查集 与 Floyd
- MySQL数据库和表名大小写敏感开关的打开办法
- Jmeter在非GUI环境下传递参数(命令行&;Jenkins配置)
- mysql 索引type介绍
热门文章
- layer 1.8.5 引用样式失效
- C# 时间格式转换
- Python3学习笔记(十三):装饰器
- 【转】HDU-6035-Colorful Tree
- Jmeter -- 监听 -- 查看每个请求的启动时间等信息
- Javascript事件:this.value()和this.select()
- JMS学习(一)
- Dijk入门(杭电2544题)
- LeetCode 12. 整数转罗马数字(Integer to Roman)
- 1.zookeeper原理解析-数据存储之Zookeeper内存结构