Acwing 897. 最长公共子序列 (每日一题)
最长公共子序列
题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N和 M。
第二行包含一个长度为 N 的字符串,表示字符串 A。
第三行包含一个长度为 M 的字符串,表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N,M≤1000
输入样例:
4 5
acbd
abedc
输出样例:
3
状态表示:
集合:所有从A[1,i] B[1,j]
的公共子序列的集合
属性:max
像最长上升子序列,状态的划分依据是找不同的点。最长上升子序列确定以a[i]
为结尾的子序列,共同点便是以a[i]
作为结尾。划分依据:a[1,i-1]
中的每个数作为最后一个不同点进行划分**
有没有发现:
DP基操:
1.找不同和相同之处/不同和固定之处
2.结合定义出发!
最长公共子序列的不同点在于i,j
在不在序列中,可以将集合划分为4类。
实际上只有3类,且往下看。
(1)i、j
均不在
i、j
均不包含其中,那只能从a[i-1]、b[j-1]
中去选
得到如下状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j-1] f[i][j]=f[i−1][j−1]
(2)i
不在,j
在
i
不在序列中,只能从前i-1
中选,j
可在可不在。
刚好i
不在,j
在,包含在这种情况中,且最大值/最小值是可以允许重复的。
得到如下状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]
(3)i
在,j
不在
j
不在序列中,那j
只能从j-1
中选择。i
可在可不在。
刚好**i
在,j
**不在,包含在这种情况中,且最大值/最小值是可以允许重复的。
得到如下状态转移方程:
f [ i ] [ j ] = f [ i ] [ j − 1 ] f[i][j]=f[i][j-1] f[i][j]=f[i][j−1]
(4)i、j
均在
只有满足**a[i]==b[j]
这一条件才存在。
确定了**a[i]、b[j]
之后,剩下的从i-1、j-1
中选出最长公共子序列,从定义出发,恰好就是f[i-1][j-1]
中选。最后再加上固定好的a[i]、b[j]
这一对即可。
得到如下状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 f[i][j]=f[i-1][j-1]+1 f[i][j]=f[i−1][j−1]+1
最后,(1)是既可以包含在(2)也可以包含在(3)中的,允许最值重复。重复没关系,求出的必定是最值且包含在整个集合中,是合法的。最后,总共只有3种情况。
求和/求值则不允许重复!!!
Accode
import java.util.*;
public class Main{static int N=1010;static int f[][]=new int[N][N];public static void main(String []args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();char a[]=(" "+sc.next()).toCharArray();char b[]=(" "+sc.next()).toCharArray();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//情况1包含在情况2、3中//情况2、3取一个maxf[i][j]=Math.max(f[i-1][j],f[i][j-1]);//满足a[i]==b[j]这一条件//再与情况4取一个maxif(a[i]==b[j])f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);}}//输出集合定义System.out.println(f[n][m]); }
}
往期回顾
不清楚蓝桥杯考什么的点点下方👇
考点秘籍
想背纯享模版的伙伴们点点下方👇
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全(第二期)
蓝桥杯省一你一定不能错过的模板大全(第三期)
蓝桥杯省一你一定不能错过的模板大全(第四期)!!!
想背注释模版的伙伴们点点下方👇
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)!!!
蓝桥杯上岸每日N题第一期(二)!!!
蓝桥杯上岸每日N题第一期(三)!!!
蓝桥杯上岸每日N题第二期(一)!!!
蓝桥杯上岸每日N题第三期(一)!!!
蓝桥杯上岸每日N题 第四期(最少刷题数)!!!
蓝桥杯上岸每日N题 第五期(山)!!!
蓝桥杯上岸每日N题 第六期(求阶乘)!!!
蓝桥杯上岸每日N题 第七期(小猫爬山)!!!
蓝桥杯上岸每日N题 第八期 (全球变暖)!!!
蓝桥杯每日N题 (消灭老鼠)
蓝桥杯每日N题(杨辉三角形)
蓝桥杯每日N题 (砝码称重)
蓝桥杯上岸每日N题(鸡尾酒)
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句(期末冲刺)
想看JavaB组填空题的伙伴们点点下方 👇
填空题
竞赛干货
算法竞赛字符串常用操作大全
蓝桥杯上岸必刷!!!(模拟/枚举专题)
蓝桥杯上岸必背!!! (第三期 DP)
蓝桥杯上岸必背!!!(第四期DFS)
蓝桥杯上岸必背!!!(第五期BFS)
蓝桥杯上岸必背!!!(第六期树与图的遍历)
蓝桥杯上岸必背!!!(第七期 最短路算法)
蓝桥杯上岸必背!!!(第八期 简单数论)
蓝桥杯上岸必刷!!!(进制、数位专题)
蓝桥杯上岸考点清单 (冲刺版)!!!
蓝桥杯上岸必背模板 (纯享版)
相关文章:
Acwing 897. 最长公共子序列 (每日一题)
最长公共子序列 题目描述 给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数 N和 M。 第二行包含一个长度为 N 的字符串,表示字符串 A。 第三行包含一个长度为 M …...

CSS中border-radius的来美化table的实战方案
border-radius是一种CSS属性,用于设置元素的边框的圆角程度。其具体的用法如下: 设置一个值:可以为元素设置一个单一的圆角半径,这个半径将应用于元素的四个角。例如: div {border-radius: 10px; }设置四个值&#x…...

移除链表元素_每日一题
“路虽远,行则将至” ❤️主页:小赛毛 ☕今日份刷题:移除链表元素 题目描述: 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val val 的节点,并返回 新的头节点 。 示例1&…...

spring boot + Consul 示例 (Kotlin版)
文章目录 1.docker 安装consul2.创建基于springboot的client2.1 依赖版本2.2 pom.xml2.3 启动类2.4 application.properties 3 搭建完成4. 总结 1.docker 安装consul docker-compose.yaml version: "3"services:consul:image: consul:1.4.4container_name: consule…...

Git企业开发控制理论和实操-从入门到深入(四)|Git的远程操作|Gitee
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…...

SpringCloudAlibaba Gateway(二)详解-内置Predicate、Filter及自定义Predicate、Filter
Predicate(断言) Predicate(断言),用于进行判断,如果返回为真,才会路由到具体服务。SpirnngCloudGateway由路由断言工厂实现,直接配置即生效,当然也支持自定义路由断言工厂。 内置路由断言工厂实现 SpringClo…...
调用chat-gpt
调用chat-gpt 依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><dependency><groupId>org.springframework.boot</groupId><artifact…...
Element组件浅尝辄止6:Dialog 对话框组件
Dialog 对话框组件:在保留当前页面状态的情况下,告知用户并承载相关操作。 大白话就是弹窗组件,日常开发中比较常见 1.怎样使用? //触发方式 <el-button type"text" click"dialogVisible true">打开&…...

Bert和LSTM:情绪分类中的表现
一、说明 这篇文章的目的是评估和比较 2 种深度学习算法(BERT 和 LSTM)在情感分析中进行二元分类的性能。评估将侧重于两个关键指标:准确性(衡量整体分类性能)和训练时间(评估每种算法的效率)。…...
【面试经典150题】跳跃游戏
题目链接 给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 1 < nums…...
【Rust】003-基础语法:流程控制
【Rust】003-基础语法:流程控制 文章目录 【Rust】003-基础语法:流程控制一、概述二、if 表达式1、语法格式2、多个3、获取表达式的值 三、循环1、loop:无限循环,可跳出无限循环跳出循环返回值 2、while:条件循环&…...

0829【综述】面向时空数据的区块链研究综述
摘要:时空数据包括时间和空间2个维度,常被应用于物流、供应链等领域。传统的集中式存储方式虽然具有一定的便捷性,但不能充分满足时空数据存储及查询等要求,而区块链技术采用去中心化的分布式存储机制,并通过共识协议来保证数据的安全性。研究现有区块链1.0、2.0和以Block-DAG为…...

MySQL高级篇(SQL优化、索引优化、锁机制、主从复制)
目录 0 存储引擎介绍1 SQL性能分析2 常见通用的JOIN查询 SQL执行加载顺序七种JOIN写法3 索引介绍 3.1 索引是什么3.2 索引优劣势3.3 索引分类和建索引命令语句3.4 索引结构与检索原理3.5 哪些情况适合建索引3.6 哪些情况不适合建索引4 性能分析 4.1 性能分析前提知识4.2 Expla…...

YOLOV8模型使用-检测-物体追踪
这个最新的物体检测模型,很厉害的样子,还有物体追踪的功能。 有官方的Python代码,直接上手试试就好,至于理论,有想研究在看论文了╮(╯_╰)╭ 简单介绍 YOLOv8 中可用的模型 YOLOv8 模型的每个类别中有五个模型用于检…...
springmvc:设置后端响应给前端的json数据转换成String格式
设置spring-mvc.xml: xml <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.springframework.org/schema/beans"xmlns:context"http://www.springframework.org/schema/context"xmlns:xsi"http://www.w…...

Mac安装brew、mysql、redis
mac安装brew mac安装brewmac安装mysql并配置开机启动mac安装redis并配置开机启动 mac安装brew 第一步:执行. /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"第二步:输入开机密码 第三…...

MLC-LLM 部署RWKV World系列模型实战(3B模型Mac M2解码可达26tokens/s)
0x0. 前言 我的 ChatRWKV 学习笔记和使用指南 这篇文章是学习RWKV的第一步,然后学习了一下之后决定自己应该做一些什么。所以就在RWKV社区看到了这个将RWKV World系列模型通过MLC-LLM部署在各种硬件平台的需求,然后我就开始了解MLC-LLM的编译部署流程和…...

Unity 之 参数类型之值类型参数的用法
文章目录 基本数据类型结构体结构体的进一步补充 总结: 当谈论值类型参数时,我们可以从基本数据类型和结构体两个方面详细解释。值类型参数指的是以值的形式传递给函数或方法的数据,而不是引用。 基本数据类型 基本数据类型的值类型参数&…...

VScode远程连接主机
一、前期准备 1、Windows安装VSCode; 2、在VSCode中安装PHP Debug插件; 3、安装好Docker 4、在容器中安装Xdebug ①写一个展现phpinfo的php文件 <?php phpinfo(); ?>②在浏览器上打开该文件 ③复制所有信息丢到Xdebug: Installation instr…...

【iOS】属性关键字
文章目录 前言一、深拷贝与浅拷贝1、OC的拷贝方式有哪些2. OC对象实现的copy和mutableCopy分别为浅拷贝还是深拷贝?3. 自定义对象实现的copy和mutableCopy分别为浅拷贝还是深拷贝?4. 判断当前的深拷贝的类型?(区别是单层深拷贝还是完全深拷贝…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...