当前位置: 首页 > 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个珠子排成一排,然后将它们串…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...