【晴问算法】提高篇—动态规划专题—最长公共子序列
题目描述
现有两个字符串s1与s2,求s1与s2的最长公共子序列的长度(子序列可以不连续)。
输入描述
第一行为字符串s1,仅由小写字母组成,长度不超过
100;第一行为字符串s2,仅由小写字母组成,长度不超过
100。
输出描述
输出一个整数,表示最长公共子序列的长度。
样例1
输入
sadstory adminsorry
输出
6
解释
最长公共子序列为
adsory,长度为6。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;
string s;
string t;
int dp[MAXN][MAXN];//记录子问题的解,dp[i][j]表示字符串s的前i个字符和字符串t的前j个字符的最长公共子序列长度
int main(){cin >> s >> t;int ls = s.length();int lt = t.length();for(int i=1;i<=ls;i++)//填表方式,用i和j作为索引访问数组时候从1开始for(int j=1;j<=lt;j++){//两层循环遍历s和t的每个字符,比较是否相等if(s[i-1] == t[j-1]){//第i-1个和第j-1个相等dp[i][j] = dp[i-1][j-1] + 1;//表示当前位置位置的最长公共子序列长度比前一个位置多1}else if(s[i-1] != t[j-1]){//如果字符不相等dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//表示当前位置的最长公共子序列长度与前一个位置保持一致}}}printf("%d",dp[ls][lt]);//即s1和s2的最长公共子序列长度}
相关文章:
【晴问算法】提高篇—动态规划专题—最长公共子序列
题目描述 现有两个字符串s1与s2,求s1与s2的最长公共子序列的长度(子序列可以不连续)。 输入描述 第一行为字符串s1,仅由小写字母组成,长度不超过100; 第一行为字符串s2…...
Greetings
Problem - 1915F - Codeforces 题意 给一些(l,r)找到所有能够包含(l,r)的数目 引入 也就是找逆序对个数 要用到归并排序中的思想: //https://www.luogu.com.cn/problem/P1216 #include<iostream> #include<cstdio> #include<stack> #include…...
JS03-函数
函数 使用函数 // 函数声明function sayHi(){document.write(Hello!<br>)}for(let i 1; i < 6; i){// 函数调用sayHi()}函数封装 function getScore(arr){sum 0for( let i 0; i < arr.length; i){sum arr[i]}document.write(sum)}getScore([99, 66, 100])函数…...
MySQL | CRUD
目录 1. Create 2. Retrieve 2.1. SELECT列 2.1.1. 全列查询 2.1.2. 指定列查询 2.1.3. 查询字段为表达式 2.1.4. 为查询结果指定别名 2.1.5. 结果去重 2.2. WHERE条件 2.2.1. 年龄小于19的同学 2.2.2. id在2~3的同学 2.2.3. id为1和4的同学 2.2.4. 姓张的同学及张…...
【电路笔记】-MOSFET作为开关
MOSFET 作为开关 文章目录 MOSFET 作为开关1、概述2、MOSFET特性曲线2.1 截住区域2.2 饱和区域3、MOSFET作为开关的示例4、功率MOSFET电机控制5、P沟道MOSFET作为开关6、互补MOSFET作为开关电机控制器当 MOSFET 在截止区和饱和区之间工作时,MOSFET 是非常好的电子开关,用于控…...
SpringBoot+Vue项目(Vue3环境搭建 + 基础页面)
文章目录 1.项目基本介绍2.安装Node.js(SSM部分安装过)3.初始化前端工程1.创建一个文件夹 springboot_vue2.创建vue项目1.在刚才创建的文件夹下打开命令行,使用脚手架搭建项目2.选择手动配置3.选择三个4.选择vue35.选择路由模式6.选择包管理方…...
elementui el-table表格自动循环滚动【超详细图解】
效果如图 1. 当表格内容超出时,自动滚动,滚动到最后一条之后在从头滚动。 2. 鼠标移入表格中,停止滚动;移出后,继续滚动。 直接贴代码 <template><div><div class"app-container"><e…...
关于学习的一点粗浅见解
我们学习的每一个领域,大多都有着宽泛的知识面,那在学习过程中,我们是应该一开始就专钻一个方向(即深度),还是应该先扩展知识面(即广度)?个人认为,应该先扩展知识面宽度,然后再精研某个方向&…...
[java基础揉碎]Object类详解
目录 equals方法: hashCode: toString: finalize: equals方法: 和equals对比 1.: 既可以判断基本类型,又可以判断引用类型 2.: 如果判断基本类型,判断的是值是否相等。示例: int i10; double d10.0; 3.:如果判断引用类型,判断的是地址是…...
23.1 微服务理论基础
23.1 微服务基础 1. 微服务介绍2. 微服务特点3. 微服务优缺点4. 微服务两大门派5. 微服务拆分6. 微服务扩展6.1 服务扩展6.2 按需扩展7. 微服务重要模块******************************************************************************************************************...
数据结构-基本概念-001
1数据结构基本概念 1.1 (1)一组用来保存一种或者多种特定关系的数据的集合(组织和存储数据)(2)程序的设计:将现实中大量而复杂的问题以特定的数据类型和特定的存储结构存储在内存中࿰…...
以题为例浅谈SSRF
什么是ssrf SSRF(Server-Side Request Forgery:服务器端请求伪造) 是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。 一般情况下,SSRF攻击的目标是从外网无法访问的内部系统。(正是因为它是由服务端发起的,所以它能够请求到与它相连…...
Java网络编程:探索奥秘与实践
欢迎来到我的博客!今天我们将一起探索Java网络编程的奥秘。网络编程是计算机科学中的一个重要领域,它使得不同的计算机系统可以相互通信和共享数据。Java的网络编程库提供了一套全面而强大的工具,让我们能够轻松地实现这些功能。我们将通过一…...
Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗
文章目录 题目方法一:滑窗右端每次1,左端来回滑动方法二:(最多K种的子串数) - (最多K-1种的子串数) 恰好K种 题目 1 < nums.length < 20000 1 < nums[i], k < nums.length 方法一…...
【闲聊】-后端框架发展史
框架,是为了解决系统复杂性,提升开发效率而产生的工具,主要服务于研发人员。 当然,框架还有更深层的作用,框架的沉淀是一种高级的抽象,会将人类的业务逐步抽象为统一标准又灵活可变的结构,为各行…...
界面控件DevExpress ASP.NET Scheduler - 助力快速交付个人信息管理系统(下)
DevExpress ASP. NET Scheduler组件能完全复制Microsoft Outlook Scheduler的样式和功能,具有日、周、月和时间轴视图,并包括内置的打印支持,因此用户可以在尽可能短的时间内交付全功能的个人信息管理系统。在上文中(点击这里回顾…...
机器学习-04-分类算法-01决策树
总结 本系列是机器学习课程的系列课程,主要介绍机器学习中分类算法,本篇为分类算法开篇与决策树部分。 参考 决策树——ID3和C4.5(理论图解公式推导) 策略产品经理必读系列—第七讲ID3、C4.5和CART算法详解 决策树(…...
探索大数据时代的决策利器:如何有效应对海量数据?
随着信息技术的快速发展,大数据时代已经到来,海量数据成为了我们生活和工作中不可忽视的一部分。这些数据来自各个方面:社交媒体、传感器、网络交易、移动设备等,每天都在以惊人的速度增长。但是,面对如此庞大的数据量,我们该如何有效地应对呢?本文将探索大数据时代的决…...
Linux 学习笔记(16)
十六、 计划任务 在很多时候为了自动化管理系统,我们都会用到计划任务,比如关机,管理,备份之类的操作,我 们都可以使用计划任务来完成,这样可以是管理员的工作量大大降低,而且可靠度更好。 l…...
【C语言】打印闰年
输⼊⼀个年份year,判断year是否是闰年 闰年判断的规则: 1, 能被4整除并且不能被100整除是闰年 2,能被400整除是闰年 结合起来如下: if ((year % 4 0 && year % 100 ! 0) || (year % 400 0)) 代码如下&…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
