当前位置: 首页 > news >正文

【晴问算法】提高篇—动态规划专题—最长公共子序列

题目描述

现有两个字符串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​&#xff0c;求s1​​​​与s2​​​​的最长公共子序列的长度&#xff08;子序列可以不连续&#xff09;。 输入描述 第一行为字符串s1​​&#xff0c;仅由小写字母组成&#xff0c;长度不超过100&#xff1b; 第一行为字符串s2​​​…...

Greetings

Problem - 1915F - Codeforces 题意 给一些(l,r)找到所有能够包含(l,r)的数目 引入 也就是找逆序对个数 要用到归并排序中的思想&#xff1a; //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&#xff08;SSM部分安装过&#xff09;3.初始化前端工程1.创建一个文件夹 springboot_vue2.创建vue项目1.在刚才创建的文件夹下打开命令行&#xff0c;使用脚手架搭建项目2.选择手动配置3.选择三个4.选择vue35.选择路由模式6.选择包管理方…...

elementui el-table表格自动循环滚动【超详细图解】

效果如图 1. 当表格内容超出时&#xff0c;自动滚动&#xff0c;滚动到最后一条之后在从头滚动。 2. 鼠标移入表格中&#xff0c;停止滚动&#xff1b;移出后&#xff0c;继续滚动。 直接贴代码 <template><div><div class"app-container"><e…...

关于学习的一点粗浅见解

我们学习的每一个领域&#xff0c;大多都有着宽泛的知识面&#xff0c;那在学习过程中&#xff0c;我们是应该一开始就专钻一个方向(即深度)&#xff0c;还是应该先扩展知识面(即广度)&#xff1f;个人认为&#xff0c;应该先扩展知识面宽度&#xff0c;然后再精研某个方向&…...

[java基础揉碎]Object类详解

目录 equals方法: hashCode: toString: finalize: equals方法: 和equals对比 1.: 既可以判断基本类型&#xff0c;又可以判断引用类型 2.: 如果判断基本类型&#xff0c;判断的是值是否相等。示例: int i10; double d10.0; 3.:如果判断引用类型&#xff0c;判断的是地址是…...

23.1 微服务理论基础

23.1 微服务基础 1. 微服务介绍2. 微服务特点3. 微服务优缺点4. 微服务两大门派5. 微服务拆分6. 微服务扩展6.1 服务扩展6.2 按需扩展7. 微服务重要模块******************************************************************************************************************...

数据结构-基本概念-001

1数据结构基本概念 1.1 &#xff08;1&#xff09;一组用来保存一种或者多种特定关系的数据的集合&#xff08;组织和存储数据&#xff09;&#xff08;2&#xff09;程序的设计&#xff1a;将现实中大量而复杂的问题以特定的数据类型和特定的存储结构存储在内存中&#xff0…...

以题为例浅谈SSRF

什么是ssrf SSRF(Server-Side Request Forgery:服务器端请求伪造) 是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。 一般情况下&#xff0c;SSRF攻击的目标是从外网无法访问的内部系统。&#xff08;正是因为它是由服务端发起的&#xff0c;所以它能够请求到与它相连…...

Java网络编程:探索奥秘与实践

欢迎来到我的博客&#xff01;今天我们将一起探索Java网络编程的奥秘。网络编程是计算机科学中的一个重要领域&#xff0c;它使得不同的计算机系统可以相互通信和共享数据。Java的网络编程库提供了一套全面而强大的工具&#xff0c;让我们能够轻松地实现这些功能。我们将通过一…...

Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗

文章目录 题目方法一&#xff1a;滑窗右端每次1&#xff0c;左端来回滑动方法二&#xff1a;&#xff08;最多K种的子串数&#xff09; - &#xff08;最多K-1种的子串数&#xff09; 恰好K种 题目 1 < nums.length < 20000 1 < nums[i], k < nums.length 方法一…...

【闲聊】-后端框架发展史

框架&#xff0c;是为了解决系统复杂性&#xff0c;提升开发效率而产生的工具&#xff0c;主要服务于研发人员。 当然&#xff0c;框架还有更深层的作用&#xff0c;框架的沉淀是一种高级的抽象&#xff0c;会将人类的业务逐步抽象为统一标准又灵活可变的结构&#xff0c;为各行…...

界面控件DevExpress ASP.NET Scheduler - 助力快速交付个人信息管理系统(下)

DevExpress ASP. NET Scheduler组件能完全复制Microsoft Outlook Scheduler的样式和功能&#xff0c;具有日、周、月和时间轴视图&#xff0c;并包括内置的打印支持&#xff0c;因此用户可以在尽可能短的时间内交付全功能的个人信息管理系统。在上文中&#xff08;点击这里回顾…...

机器学习-04-分类算法-01决策树

总结 本系列是机器学习课程的系列课程&#xff0c;主要介绍机器学习中分类算法&#xff0c;本篇为分类算法开篇与决策树部分。 参考 决策树——ID3和C4.5&#xff08;理论图解公式推导&#xff09; 策略产品经理必读系列—第七讲ID3、C4.5和CART算法详解 决策树&#xff08;…...

探索大数据时代的决策利器:如何有效应对海量数据?

随着信息技术的快速发展,大数据时代已经到来,海量数据成为了我们生活和工作中不可忽视的一部分。这些数据来自各个方面:社交媒体、传感器、网络交易、移动设备等,每天都在以惊人的速度增长。但是,面对如此庞大的数据量,我们该如何有效地应对呢?本文将探索大数据时代的决…...

Linux 学习笔记(16)

十六、 计划任务 在很多时候为了自动化管理系统&#xff0c;我们都会用到计划任务&#xff0c;比如关机&#xff0c;管理&#xff0c;备份之类的操作&#xff0c;我 们都可以使用计划任务来完成&#xff0c;这样可以是管理员的工作量大大降低&#xff0c;而且可靠度更好。 l…...

【C语言】打印闰年

输⼊⼀个年份year&#xff0c;判断year是否是闰年 闰年判断的规则&#xff1a; 1&#xff0c; 能被4整除并且不能被100整除是闰年 2&#xff0c;能被400整除是闰年 结合起来如下&#xff1a; if ((year % 4 0 && year % 100 ! 0) || (year % 400 0)) 代码如下&…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)

注&#xff1a;文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件&#xff1a;STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...

大模型真的像人一样“思考”和“理解”吗?​

Yann LeCun 新研究的核心探讨&#xff1a;大语言模型&#xff08;LLM&#xff09;的“理解”和“思考”方式与人类认知的根本差异。 核心问题&#xff1a;大模型真的像人一样“思考”和“理解”吗&#xff1f; 人类的思考方式&#xff1a; 你的大脑是个超级整理师。面对海量信…...

EC2安装WebRTC sdk-c环境、构建、编译

1、登录新的ec2实例&#xff0c;证书可以跟之前的实例用一个&#xff1a; ssh -v -i ~/Documents/cert/qa.pem ec2-user70.xxx.165.xxx 2、按照sdk-c demo中readme的描述开始安装环境&#xff1a; https://github.com/awslabs/amazon-kinesis-video-streams-webrtc-sdk-c 2…...

JavaScript性能优化实战大纲

性能优化的核心目标 降低页面加载时间&#xff0c;减少内存占用&#xff0c;提高代码执行效率&#xff0c;确保流畅的用户体验。 代码层面的优化 减少全局变量使用&#xff0c;避免内存泄漏 // 不好的实践 var globalVar I am global;// 好的实践 (function() {var localV…...

【AI学习】wirelessGPT多任务无线基础模型摘要

收看了关于WirelessGPT多任务无线基础模型的演讲视频&#xff0c;边做一个记录。 应该说&#xff0c;在无线通信大模型的探索方面&#xff0c;有一个非常有益的尝试。 在沈学明院士带领下开展 https://www.chaspark.com/#/live/1125484184592834560...