LIS、LCS算法模型

文章目录

  • 1.LCS算法模型
  • 2.LIS算法模型

1.LCS算法模型

LCS问题就是给定两个序列A和B,求他们最长的公共子序列。
在求解时,我们会设dp[i][j]表示为A[1 ~ i]序列和B[1 ~ j]序列中(不规定结尾)的最长子序列的长度。

if(a[i]==b[i]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

就是说,当a[i]=b[j]时,可以将他们作为插入到LCS的后面,长度加1即可;当a[i]!=b[j]时,说明此时LCS不会演唱,那么就要从dp[i-1][j]和dp[i][j-1]中取大的作为最长的长度。

例题:
在这里插入图片描述
示例代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3+5;
int n,m;
ll a[N],b[N],dp[N][N];
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int j=1;j<=m;j++)cin>>b[j];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<dp[n][m];return 0;
}

如何求出具体的最长子序列?

	vector<int> v;int x=n,y=m;// 只需要从dp[n][m]向前搜索即可,如果相等则回到左上方,否则回到max(上边,左边)while(x&&y){if(a[x]==b[y]){v.push_back(a[x]);x--,y--;//左上走 }else if(dp[x-1][y]>dp[x][y-1])x--;//向大的走else y--; }reverse(v.begin(),v.end());for(const auto &i:v)cout<<i<<' ';

2.LIS算法模型

最长上升子序列是一个经典的DP模型。
子序列指的是一个序列中,按照原顺序选出若干个不一定连续的元素所组成的序列。
在求解LIS时,一般我们会设dp[i]表示1~i序列中以a[i]结尾的最长上升子序列的长度。
状态转移方程为:dp[i] = max(dp[j] + 1),if a[i] > a[j]
表示a[i]要插入到不同的子序列后面的情况。

模板例题:

在这里插入图片描述
示例代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int a[N],dp[N];
// 设状态 dp[i]表示1~i的最长上升子序列的长度,状态转移方程为 dp[i]=max(dp[j]+1) if a[i]>a[j] 
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){dp[i]=1;for(int j=1;j<i;j++){if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);}}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i]);}cout<<ans;return 0;
}

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

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

相关文章

信号处理--情绪分类数据集DEAP预处理(python版)

关于 DEAP数据集是一个常用的情绪分类公共数据&#xff0c;在日常研究中经常被使用到。如何合理地预处理DEAP数据集&#xff0c;对于后端任务的成功与否&#xff0c;非常重要。本文主要介绍DEAP数据集的预处理流程。 工具 图片来源&#xff1a;DEAP: A Dataset for Emotion A…

从零开始为香橙派orangepi zero 3移植主线linux——1.uboot

从零开始为香橙派orangepi zero 3移植主线linux——1.uboot 0.前言一、准备二、制作引导文件1.BL312.SCP firmware (Crust)3.uboot 三、烧录四、运行 0.前言 之前买了块香橙派zero3&#xff0c;CPU是全志H618&#xff0c;四核cortex-A53&#xff0c;烧录了官方的ubuntu系统后就…

《论文阅读》PAGE:一个用于会话情绪原因蕴含基于位置感知的图模型 ICASSP 2023

《论文阅读》PAGE&#xff1a;一个用于会话情绪原因蕴含基于位置感知的图模型 ICASSP 2023 前言 简介任务定义模型构架Utterances Encoding with EmotionPosition-aware GraphCausal Classifier实验结果 前言 亲身阅读感受分享&#xff0c;细节画图解释&#xff0c;再也不用担…

2024年腾讯云4核8G服务器多少钱一年?买1年送3个月

2024年腾讯云4核8G服务器租用优惠价格&#xff1a;轻量应用服务器4核8G12M带宽646元15个月&#xff0c;CVM云服务器S5实例优惠价格1437.24元买一年送3个月&#xff0c;腾讯云4核8G服务器活动页面 txybk.com/go/txy 活动链接打开如下图&#xff1a; 腾讯云4核8G服务器优惠价格 轻…

【深度学习】【机器学习】用神经网络进行入侵检测,NSL-KDD数据集,基于机器学习(深度学习)判断网络入侵

文章目录 下载数据集NSL-KDD数据集介绍输入的41个特征输出的含义数据处理&&训练技巧建神经网络&#xff0c;输入41个特征&#xff0c;输出是那种类别的攻击模型训练模型推理写gradio前端界面&#xff0c;用户自己输入41个特征&#xff0c;后端用模型推理计算后显示出是…

微服务(基础篇-006-Docker)

Docker是一个开源的应用容器引擎&#xff0c;它让开发者可以打包他们的应用以及依赖包到一个可移植的容器中&#xff0c;然后发布到任何Linux机器上&#xff0c;也可以实现虚拟化。容器是完全使用沙箱机制&#xff0c;相互之间没有任何接口&#xff08;类似 iPhone 的 app&…

【OpenCV】 OpenCV (C++) 与 OpenCvSharp (C#) 之间数据通信

OpenCV是一个基于Apache2.0许可&#xff08;开源&#xff09;发行的跨平台计算机视觉和机器学习软件库&#xff0c;可以运行在Linux、Windows、Android和Mac OS操作系统上。 它轻量级而且高效——由一系列 C 函数和少量 C 类构成&#xff0c;同时提供了Python、Ruby、MATLAB等语…

阿里云实时计算Flink的产品化思考与实践【上】

摘要&#xff1a;本文整理自阿里云高级产品专家黄鹏程和阿里云技术专家陈婧敏在 FFA 2023 平台建设专场中的分享。内容主要为以下五部分&#xff1a; 阿里云实时计算 Flink 简介产品化思考产品化实践SQL 产品化思考及实践展望 该主题由黄鹏程和陈婧敏共同完成&#xff0c;前半程…

BaseDao封装JavaWeb的增删改查

目录 什么是BaseDao&#xff1f; 为什么需要BaseDao&#xff1f; BaseDao的实现逻辑 什么是BaseDao&#xff1f; Basedao 是一种基于数据访问对象&#xff08;Data Access Object&#xff09;模式的设计方法。它是一个用于处理数据库操作的基础类&#xff0c;负责封装数据库…

Adobe推出20多个,企业版生成式AI定制、微调服务

3月27日&#xff0c;全球多媒体领导者Adobe在拉斯维加斯召开“Summit 2024”大会&#xff0c;重磅推出了Firefly Services。 Firefly Services提供了20 多个生成式AI和创意API服务&#xff0c;支持企业自有数据对模型进行定制、微调&#xff0c;同时可以与PS、Illustrator、Ex…

高级DBA带你处理MySQL客户端程序频繁访问MYSQL数据库并错误链接不释放导致连接数爆满事故实战

高级DBA带你处理MySQL客户端程序频繁访问MYSQL数据库并错误链接不释放导致连接数爆满事故实战 一、生产事故描述 Mysql生产数据库最大连接数爆满&#xff0c;其余客户端也同样拿不到数据库连接&#xff0c;生产异常&#xff0c;数据传输失败&#xff01; 报错如下&#xff1a…

架构师之路--Docker的技术学习路径

Docker 的技术学习路径 一、引言 Docker 是一个开源的应用容器引擎&#xff0c;它可以让开发者将应用程序及其依赖包打包成一个可移植的容器&#xff0c;然后在任何支持 Docker 的操作系统上运行。Docker 具有轻量级、快速部署、可移植性强等优点&#xff0c;因此在现代软件开…

解决kubesphere流水线docker登陆错误http: server gave HTTP response to HTTPS client

kubesphere DevOps流水线中&#xff0c;在登录私有的harbor仓库时&#xff0c;报以下错误 docker login 111.230.19.120:80 -u admin -p test123. WARNING! Using --password via the CLI is insecure. Use --password-stdin. Error response from daemon: Get "https://…

使用vue构建一个简单实用的春节红包插件!

摘要&#xff1a;本文将介绍如何使用Vue.js构建一个简单实用的春节红包插件。该插件通过模拟红包的打开和关闭过程&#xff0c;以及金额的随机分配&#xff0c;为春节红包活动提供了一个有趣且互动的体验。 一、引言 在春节这个充满欢乐和祝福的时刻&#xff0c;红包成为了传递…

pt-archiver的实践分享,及为何要用 ob-archiver 归档数据的探讨

作者简介&#xff1a;肖杨&#xff0c;软件开发工程师 在数据密集型业务场景中&#xff0c;数据管理策略是否有效至关重要&#xff0c;它直接关系到系统性能与存储效率的提升。数据归档作为该策略的关键环节&#xff0c;不仅有助于优化数据库性能&#xff0c;还能有效降低存储成…

11.2024

插入排序 代码&#xff1a; public class 第十一题 {public static void main(String[] args) {int a[]{2,2,1,6,4,9,7,6,8};for (int k1;k<a.length;k){int sk-1;//排好序的最后一位int sssa[k];//记录哨兵的值while (s>0&&sss<a[s]){a[s1]a[s];s--;}a[s1]…

Python中的变量与常量

变量&#xff1a;在程序运行过程中&#xff0c;值会发生变化的量&#xff0c; 常量&#xff1a;在程序运行过程中&#xff0c;值不会发生变化的量。 无论是变量还是常量&#xff0c;在创建时都会在内存中开辟一块空间&#xff0c;用于保存它的值。 Python 中的变量不需要声明…

数仓建设实践——58用户画像数仓建设

目录 一、数据仓库&用户画像简介 1.1 数据仓库简介 1.2 数据仓库的价值 1.3 用户画像简介 1.4 用户画像—标签体系 二、用户画像数仓建设过程 2.1 画像数仓—背景&现状 2.2 画像数仓—整体架构 2.3 画像数仓—研发流程 2.4 画像数仓—指标定义 2.5 画像数仓…

基于大语言模型的云故障根因分析|顶会EuroSys24论文

*马明华 微软主管研究员 2021年CCF国际AIOps挑战赛程序委员会主席&#xff08;第四届&#xff09; 2021年博士毕业于清华大学&#xff0c;2020年在佐治亚理工学院做访问学者。主要研究方向是智能运维&#xff08;AIOps&#xff09;、软件可靠性。近年来在ICSE、FSE、ATC、EuroS…

【b站李炎恢】Vue.js Element UI | 十天技能课堂 | 更新中... | 李炎恢

课程地址&#xff1a;【Vue.js Element UI | 十天技能课堂 | 更新中... | 李炎恢】 https://www.bilibili.com/video/BV1U54y127GB/?share_sourcecopy_web&vd_sourceb1cb921b73fe3808550eaf2224d1c155 备注&#xff1a;虽然标题声明还在更新中&#xff0c;但是看一些常用…