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

动态规划基础(二)最长公共子序列 LCS

讲解求两个串中最长的公共的子序列长度或输出子序列等
poj1458

题目大意

给定两个字符串,要求输出两个字符串中最长公共子序列长度

思路

我们定义 a [ i ] [ j ] a[i][j] a[i][j]为,当字串 s t r 1 str1 str1 i i i位置,字串 s t r 2 str2 str2 j j j位置时,最长公共子串的长度,我们有如下关系式:
i f if if s t r 1 [ i ] = = s t r 2 [ j ] , a [ i ] [ j ] = a [ i − 1 ] [ j − 1 ] + 1 str1[i]==str2[j],a[i][j]=a[i-1][j-1]+1 str1[i]==str2[j],a[i][j]=a[i1][j1]+1
e l s e else else a [ i ] [ j ] = m a x ( a [ i − 1 ] [ j ] , a [ i ] [ j − 1 ] a[i][j]=max(a[i-1][j],a[i][j-1] a[i][j]=max(a[i1][j],a[i][j1]
最后打印即可

ACcode

#include<bits/stdc++.h>using namespace std;int a[1005][1005];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);string str1, str2;while (cin >> str1 >> str2) {int len1 = str1.size();int len2 = str2.size();for (int i = 0;i <= len1;i++)a[i][0] = 0;for (int j = 0;j <= len2;j++)a[0][j] = 0;for (int i = 1;i <= len1;i++) {for (int j = 1;j <= len2;j++) {if (str1[i - 1] == str2[j - 1])a[i][j] = a[i - 1][j - 1] + 1;else a[i][j] = max(a[i - 1][j], a[i][j - 1]);}}cout << a[len1][len2] << '\n';}return 0;
} 

相关文章:

动态规划基础(二)最长公共子序列 LCS

讲解求两个串中最长的公共的子序列长度或输出子序列等 poj1458 题目大意 给定两个字符串&#xff0c;要求输出两个字符串中最长公共子序列长度 思路 我们定义 a [ i ] [ j ] a[i][j] a[i][j]为&#xff0c;当字串 s t r 1 str1 str1到 i i i位置&#xff0c;字串 s t r 2 s…...

React配置src根目录@

文章目录 1.打开webpack配置文件2.配置webpack 1.打开webpack配置文件 yarn eject or npm run eject 如果报错了记得提前 git commit一下 2.配置webpack 找到 webpack.config.js 文件在 webpack.config.js 文件中找到 alias 配置在alias里添加: path.resolve(src) , 或者 : pa…...

SQL Povit函数使用及实例

PIVOT函数常用于数据的行转列&#xff0c;同时也可以用此函数实现类似于Excel中的数据透视表的效果。 PIVOT函数 PIVOT 函数的基本语法如下&#xff1a; -- PIVOT 语法 SELECT <非透视的列>,[第一个透视的列] AS <列名称>,[第二个透视的列] AS <列名称>,.…...

Lite AD的安装

1、Lite AD的安装及配置 Lite AD流程&#xff1a; &#xff08;1&#xff09;创建一个新的Windows 10&#xff0c;安装tools&#xff0c;再安装ITA组件&#xff08;安装Lite AD会自动安装VAG/VLB&#xff09; &#xff08;2&#xff09;创建一个新的Windows 10&#xff0c;安…...

限流算法之流量控制的平滑之道:滑动时间窗算法

文章目录 引言简介优点缺点样例样例图样例代码 应用场景结论 引言 在互联网应用中&#xff0c;流量控制是一个重要的组件&#xff0c;用于防止系统过载和保护核心资源。常见的限流算法包括固定窗口算法和滑动时间窗算法。本文将重点介绍滑动时间窗算法&#xff0c;并分析其优缺…...

C语言数据结构——顺序表

&#xff08;图片由AI生成&#xff09; 0.前言 在程序设计的世界里&#xff0c;数据结构是非常重要的基础概念。本文将专注于C语言中的一种基本数据结构——顺序表。我们将从数据结构的基本概念讲起&#xff0c;逐步深入到顺序表的内部结构、分类&#xff0c;最后通过一个实…...

网络安全:守护数字世界的盾牌

在当今数字化的时代&#xff0c;网络已经渗透到我们生活的方方面面。从社交媒体到在线银行&#xff0c;从在线购物到工作文件传输&#xff0c;网络几乎无处不在。然而&#xff0c;随着网络的普及&#xff0c;网络安全问题也日益凸显。那么&#xff0c;如何确保我们的数字资产安…...

vue3hooks的使用

hook是钩子的意思&#xff0c;看到“钩子”是不是就想到了钩子函数&#xff1f;事实上&#xff0c;hooks 还真是函数的一种写法。 vue3 借鉴 react hooks 开发出了 Composition API &#xff0c;所以也就意味着 Composition API 也能进行自定义封装 hooks。 vue3 中的 hooks …...

elementUI+el-upload 上传、下载、删除文件以及文件展示列表自定义为表格展示

Upload 上传组件的使用 官方文档链接使用el-upload组件上传文件 具体参数说明&#xff0c;如何实现上传、下载、删除等功能获取文件列表进行file-list格式匹配代码 文件展示列表自定义为表格展示 使用的具体参数说明文件大小展示问题&#xff08;KB/MB&#xff09;文件下载代码…...

供应链安全项目in-toto开源框架详解

引言&#xff1a;in-toto 是一个开源框架&#xff0c;能够以密码学的方式验证构件生产路径上的每个组件和步骤。它可与主流的构建工具、部署工具进行集成。in-toto已经被CNCF技术监督委员会 (Technical Oversight Committee&#xff0c;TOC)接纳为CNCF孵化项目。 1. 背景 由于…...

自己是如何使用单元测试

前言 自己是如何使用单元测试 进行单元测试能够让我们在编写方法的具体实现代码后&#xff0c;能清晰地看到其是否能实现预期的功能&#xff0c;有助于我们及时修正自己方法中存在的bug&#xff0c;以免在后续使用到某方法时出现意想不到的错误。 一、引入单元测试所使用的依赖…...

第二百七十八回

文章目录 1. 概念介绍2. 使用方法2.1 DropdownMenu2.1 DropdownMenuEntry 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何禁止页面跟随手机自动旋转"相关的内容&#xff0c;本章回中将介绍DropdownMenu组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1.…...

Java 内存模型深度解析

优质博文&#xff1a;IT-BLOG-CN 一、并发编程模型的两个关键问题 【1】并发中常见的两个问题&#xff1a;线程之间如何通信及线程之间如何同步。通信是指线程之间以何种机制来交换信息。在命令式编程中&#xff0c;线程之间的通信机制有两种&#xff1a;内存共享和消息传递&…...

python爬取图片(thumbURL和html文件标签分别爬取)

当查看源代码&#xff0c;发现网址在thumbURL之后时&#xff0c;用此代码: # 当查看源代码&#xff0c;发现网址在thumbURL之后时&#xff0c;用此代码:import requestsheaders {User-Agent:Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:121.0) Gecko/20100101 Firefox/121…...

MySQL、Oracle 常用SQL:建表、建视图、数据增删改查、常用condition

目录 1 MySQL、Oracle 建表语句整理1.1 MySQL 建表1.2 Oracle 建表1.3 补充1.3.1 主键&#xff1a;新增、删除1.3.2 字段&#xff1a;新增、修改、删除 2 MySQL、Oracle 建视图3 数据&#xff1a;增删改查3.1 插入数据3.1.1 MySQL、Oracle 插入一条数据3.1.2 MySQL、Oracle 插入…...

Docker(八)高级网络配置

作者主页&#xff1a; 正函数的个人主页 文章收录专栏&#xff1a; Docker 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01; 高级网络配置 注意&#xff1a;本章属于 Docker 高级配置&#xff0c;如果您是初学者&#xff0c;您可以暂时跳过本章节&#xff0c;直接学习…...

VUE--- ref refs

ref & refs 的作用&#xff1a;用于获取dom元素或组件实例&#xff0c;也可用于组件组件间数据的获取和修改 ref & refs 与querySelector的区别&#xff1a; ● ref & refs 查找的范围是当前组件内&#xff0c;更加精确稳定 ● querySelector 查找的范围是整个页面…...

微信小程序之WXML 模板语法之数据绑定、事件绑定、wx:if和列表渲染

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…...

maven导入无法拉取所需依赖

maven导入无法拉取所需依赖 1.原因2.解决搞定收工&#xff01; 1.原因 公司使用的是gradle&#xff0c;配置的私有云&#xff0c;maven里面配置私有云完全使用不了&#xff0c;无论配置国内还是国外的&#xff0c;导入的项目报错拉不到jar包。 <mirror><id>mirro…...

【2023-08-20】字节跳动秋招笔试四道编程题解

恭喜发现宝藏!搜索公众号【TechGuide】回复公司名,解锁更多新鲜好文和互联网大厂的笔经面经。 作者@TechGuide【全网同名】 订阅专栏【进阶版】2023最新大厂笔试真题 & 题解,不容错过的宝藏资源! 第一题:最小交换次数 题目描述 小盖将n个珠子排成一排,然后将它们串…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...