算法基础之最长公共子序列

最长公共子序列

  • 核心思想: 线性dp

    • 集合定义 : f[i][j]存 a[1 ~ i] 和 b[1 ~ j] 的最长公共子序列长度

      • 在这里插入图片描述
    • 状态计算: 分为取/不取a[i]/b[j] 共四种情况

      • 其中 中间两种会包含两个都不取的情况(去掉) 但是因为取最大值 有重复也没事
      • 用f[i-1][j] 和 f[i][j-1]表示取一个的情况即可 如果是求和 则必须去掉重复部分
      • 在这里插入图片描述
    •   #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N = 1010;int n,m;char a[N],b[N];int f[N][N];int main(){cin>>n>>m>>a+1>>b+1;  //从1开始存abfor(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j] = max(f[i-1][j] , f[i][j-1]);  //中间两种情况是必定存在的if(a[i] == b[j]) f[i][j] = max(f[i][j] , f[i-1][j-1] +1);  //a[i]=b[j] 才有最后一种情况}}cout<<f[n][m];}
      

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/224692.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【SpringBoot篇】解决缓存击穿问题② — 基于逻辑过期方式

&#x1f38a;专栏【SpringBoot】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f38d;什么是逻辑过期方式⭐思路&#x1f339;代码 &am…

RPC(6):RMI实现RPC

1RMI简介 RMI(Remote Method Invocation) 远程方法调用。 RMI是从JDK1.2推出的功能&#xff0c;它可以实现在一个Java应用中可以像调用本地方法一样调用另一个服务器中Java应用&#xff08;JVM&#xff09;中的内容。 RMI 是Java语言的远程调用&#xff0c;无法实现跨语言。…

Zookeeper的学习笔记

Zookeeper概念 Zookeeper是一个树形目录服务&#xff0c;简称zk。 Zookeeper是一个分布式的、开源的分布式应用程序的协调服务 Zookeeper提供主要的功能包括&#xff1a;配置管理&#xff0c;分布式锁&#xff0c;集群管理 Zookeeper命令操作 zk数据模型 zk中的每一个节点…

【K8S in Action】服务:让客户端发现pod 并与之通信(2)

一 通过Ingress暴露服务 Ingress (名词&#xff09; 一一进入或进入的行为&#xff1b;进入的权利&#xff1b;进入的手段或地点&#xff1b;入口。一个重要的原因是每个 LoadBalancer 服务都需要自己的负载均衡器&#xff0c; 以及 独有的公有 IP 地址&#xff0c; 而 Ingres…

C# WPF上位机开发(windows pad上的应用)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 大部分同学可能都认为c# wpf只能用在pc端。其实这是一种误解。c# wpf固然暂时只能运行在windows平台上面&#xff0c;但是windows平台不仅仅是电脑…

Python - 深夜数据结构与算法之 Recursion

目录 一.引言 二.递归的简介 1.Recursion 递归 2.Factorial 阶乘 3.Template 模版 三.经典算法实战 1.Generate-Parentheses [22] 2.Climbing-Stairs [70] 3.Is-Valid-BST [98] 4.Max-Depth [104] 5.Construct-Binary-Tree [105] 6.Min-Depth [111] 7.Invert-Tree…

Spring Boot3 Web开发技术

前期回顾 springboot项目常见的配置文件类型有哪些&#xff1f;哪种类型的优先级最高 yml properties yaml 读取配置文件里的数据用什么注解&#xff1f; value restful风格 RESTful 风格与传统的 HTTP 请求方式相比&#xff0c;更加简洁&#xff0c;安全&#xff0c;能隐…

企业级“RAS”的数据平台如何炼成?

从“看报表”到“数据分析结果直接投入运营”&#xff0c;数字化正在深入企业经营&#xff0c;数据系统正在成为核心生产系统。相应的&#xff0c;企业对“作业挂了”、“系统崩了”、“算不出来”的容忍度越来越低——只有足够稳定、可靠、专业的数据系统&#xff0c;才能及时…

现代 NLP:详细概述,第 1 部分:transformer

阿比吉特罗伊 一、说明 近五年来&#xff0c;随着 BERT 和 GPT 等思想的引入&#xff0c;我们在自然语言处理领域取得了巨大的成就。在本文中&#xff0c;我们的目标是逐步深入研究改进的细节&#xff0c;并了解它们带来的演变。 二、关注就是你所需要的 2017 年&#xff0c;来…

详解ibm_t60(945)的板子的保护隔离和ec的待机供电

1.,首先看ec待机条件: 待机供电&#xff0c;32k时钟&#xff0c;复位&#xff0c;适配器检测&#xff0c;开关信号。但是视频居然是找适配器的接口&#xff0c;跟着视频走&#xff0c;所以我先找打了适配器接口j24。vint20为公共点&#xff0c;我查了vint20的所有接线发现没有小…

Django-REST-Framework 如何快速生成Swagger, ReDoc格式的 REST API 文档

1、API 接口文档的几种规范格式 前后端分离项目中&#xff0c;使用规范、便捷的API接口文档工具&#xff0c;可以有效提高团队工作效率。 标准化的API文档的益处&#xff1a; 允许开发人员以交互式的方式查看、测试API接口&#xff0c;以方便使用将所有可暴露的API接口进行分…

Stable Diffusion模型原理

AI 图像生成引人注目&#xff0c;它能够根据文字描述生成精美图像&#xff0c;这极大地改变了人们的图像创作方式。Stable Diffusion 作为一款高性能模型&#xff0c;它生成的图像质量更高、运行速度更快、消耗的资源以及内存占用更小&#xff0c;是 AI 图像生成领域的里程碑。…

PPT中加入页码

PPT中加入页码 文章目录 简单版本样式更改 简单版本 PPT中插入页码&#xff0c;基础的就是在“插入”选项卡中单机“幻灯片编号”即可 样式更改 然而&#xff0c;就像我们做幻灯片不满足于白底黑字一样&#xff0c;页码也总不能是默认的样式。 比如&#xff0c;在页码下面…

MyBatis的缓存!!!!

为什么使用缓存&#xff1f; 首次访问时&#xff0c;查询数据库&#xff0c;并将数据存储到内存中&#xff1b;再次访问时直接访问缓存&#xff0c;减少IO、硬盘读写次数、提高效率 Mybatis中的一级缓存和二级缓存&#xff1f; 一级缓存: 它指的是mybatis中的SqlSession对象的…

uni-app pages.json之globalStyle全局页面样式配置

锋哥原创的uni-app视频教程&#xff1a; 2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中...共计23条视频&#xff0c;包括&#xff1a;第1讲 uni…

56.0/DIV+CSS 布局(详细版)

目录 56.1 本章简介 56.2 实例讲解 56.2.1 菜单制作 56.2.2 美化滚动条 56.2.3 DIV+CSS 布局 56.3 综合示例 56.3.1 总体分析 56.3.2 Header 层 56.3.3 最终代码 56.1 本章简介 本章通过几个实例讲解 DIV+CSS 的应用。 采用表格布局的页面内,为了实现设计的布局,制作者往往…

uni-app封装表格组件

组件代码&#xff1a; <template><view><uni-table class"tableBox" border stripe emptyText"暂无更多数据" ><!-- 表头行 --><uni-tr class"tableTr"><uni-th align"center" v-for"item in …

蓝牙物联网通信网络设计方案

随着当前经济的快速发展&#xff0c;社会运行节奏加快&#xff0c;人们更倾向于选择高效的出行方式&#xff0c;而飞机就是其中之一。近年来&#xff0c;全国各地机场的吞吐量不断增长&#xff0c;导致航站楼面积过大&#xff0c;而 GPS全球定位系统在室内感测不到卫星信号无法…

使用tesla gpu 加速大模型,ffmpeg,unity 和 UE等二三维应用

我们知道tesla gpu 没有显示器接口&#xff0c;那么在windows中怎么使用加速unity ue这种三维编辑器呢&#xff0c;答案就是改变注册表来加速相应的三维渲染程序. 1 tesla gpu p40 p100 加速 在windows中使用regedit 来改变 核显配置&#xff0c; 让p100 p40 等等显卡通过核显…