Coincidence (九度教程第98题) 最长公共子序列(LCS) 动态规划

2023-10-17 09:38

本文主要是介绍Coincidence (九度教程第98题) 最长公共子序列(LCS) 动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Find a longest common subsequence of two strings.
输入描述:
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
输出描述:
For each case, output k – the length of a longest common subsequence in one line.
示例1
输入
abcd
cxbydz
输出
2

题目大意:
求出两个字符串的最长公共子串长度,典型的最长公共子序列问题。
解题思路:动态规划

与求最长递增子序列一样,我们首先将原问题分割成一些子问题,我们用
dp[ i ][ j ]表示 S1 中前 i 个字符与 S2 中前 j 个字符分别组成的两个前缀字符串的最
长公共子串长度
。显然的,当 i、j 较小时我们可以直接得出答案,如 dp[ 0 ][ j ]必
等于 0。那么,假设我们已经求得 dp[ i ][ j ](0<=i<x || 0<=j<y)的所有值,考虑如何由
这些值继而推得 dp[x][y],求得 S1 前 x 个字符组成的前缀子串和 S2 前 y 个字符
组成的前缀子串的最长公共子序列长度。
若 S1[x] = =S2[y],即 S1 中的第 x 个字符和 S2 中的第 y 个字符相同,同时由于他们都是各自前缀子串的最后一个字符,那么必存在一个最长公共子串以 S1[x]或 S2[y]结尾,其它部分等价于 S1 中前 x-1个字符和S2中前y-1个字符的最长公共子串。所以这个子串的长度比dp[x-1][y-1]又增加 1,即 dp[x][y] = dp[x-1][y-1] + 1。
相反的,若 S1[x] != S2[y],此时其最长公共子串长度为 S1 中前 x-1 个字符和 S2 中前 y 个字符的最长公共子串长度与S1 中前 x 个字符和 S2 中前 y-1 个字符的最长公共子串长度的较大者,即在两种情况下得到的最长公共子串都不会因为其中一个字符串又增加了一个字符长度发生改变。综上所述,dp[x][y] = max{dp[x-1][y],dp[x][y-1]}。

综上所述,最长公共子序列问题的递推条件:

//字符串s1长度为n, 字符串s2长度为m
//dp[i][j]表示s1中前i个字符与s2中前j个字符分别组成的两个前缀字符串的最长公共子串长度
//dp[0][j]=0    0<=j<=m
//dp[i][0]=0    0<=i<=n
//dp[n][m]中保存的值即为两个原始字符串的最长公共子序列长度
if(s1[i]==s2[j]){ dp[i][j] = dp[i-1][j-1] + 1;}
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

AC代码

//最长公共子序列问题
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;int dp[101][101];
char s1[101], s2[101];
int main() {cin >> s1;cin >> s2;int a = strlen(s1);int b = strlen(s2);for (int i = 0; i <= a; i++) { dp[i][0] = 0; }for (int i = 0; i <= b; i++) { dp[0][i] = 0; }for (int i = 1; i <= a; i++) {for (int j = 1; j <= b; j++) {if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max( dp[i][j - 1], dp[i - 1][j] );}}cout << dp[a][b] << endl;//system("pause");return 0;
}

这篇关于Coincidence (九度教程第98题) 最长公共子序列(LCS) 动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/224515

相关文章

Nexus安装和启动的实现教程

《Nexus安装和启动的实现教程》:本文主要介绍Nexus安装和启动的实现教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Nexus下载二、Nexus安装和启动三、关闭Nexus总结一、Nexus下载官方下载链接:DownloadWindows系统根

CnPlugin是PL/SQL Developer工具插件使用教程

《CnPlugin是PL/SQLDeveloper工具插件使用教程》:本文主要介绍CnPlugin是PL/SQLDeveloper工具插件使用教程,具有很好的参考价值,希望对大家有所帮助,如有错... 目录PL/SQL Developer工具插件使用安装拷贝文件配置总结PL/SQL Developer工具插

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

Java中的登录技术保姆级详细教程

《Java中的登录技术保姆级详细教程》:本文主要介绍Java中登录技术保姆级详细教程的相关资料,在Java中我们可以使用各种技术和框架来实现这些功能,文中通过代码介绍的非常详细,需要的朋友可以参考... 目录1.登录思路2.登录标记1.会话技术2.会话跟踪1.Cookie技术2.Session技术3.令牌技

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Python使用Code2flow将代码转化为流程图的操作教程

《Python使用Code2flow将代码转化为流程图的操作教程》Code2flow是一款开源工具,能够将代码自动转换为流程图,该工具对于代码审查、调试和理解大型代码库非常有用,在这篇博客中,我们将深... 目录引言1nVflRA、为什么选择 Code2flow?2、安装 Code2flow3、基本功能演示

Java Spring 中的监听器Listener详解与实战教程

《JavaSpring中的监听器Listener详解与实战教程》Spring提供了多种监听器机制,可以用于监听应用生命周期、会话生命周期和请求处理过程中的事件,:本文主要介绍JavaSprin... 目录一、监听器的作用1.1 应用生命周期管理1.2 会话管理1.3 请求处理监控二、创建监听器2.1 Ser

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

MySQL 安装配置超完整教程

《MySQL安装配置超完整教程》MySQL是一款广泛使用的开源关系型数据库管理系统(RDBMS),由瑞典MySQLAB公司开发,目前属于Oracle公司旗下产品,:本文主要介绍MySQL安装配置... 目录一、mysql 简介二、下载 MySQL三、安装 MySQL四、配置环境变量五、配置 MySQL5.1

MQTT SpringBoot整合实战教程

《MQTTSpringBoot整合实战教程》:本文主要介绍MQTTSpringBoot整合实战教程,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考... 目录MQTT-SpringBoot创建简单 SpringBoot 项目导入必须依赖增加MQTT相关配置编写