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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【算法刷题 | 二叉树 04】3.27(翻转二叉树、对称二叉树、完全二叉树的节点个数、平衡二叉树、完全二叉树的所有路径)

文章目录 6.翻转二叉树6.1问题6.2解法一&#xff1a;递归6.2.1递归思路&#xff08;1&#xff09;确定递归函数的参数和返回值&#xff08;2&#xff09;确定终止条件&#xff08;3&#xff09;确定单层递归的逻辑 6.2.2全部代码 6.3解法二&#xff1a;层序遍历 7.对称二叉树7.…

SQLynx发布3.0.0版本:带来更流畅便捷的SQL开发体验

作为新一代的一站式数据库管理开发工具&#xff0c; SQLynx自发布上线以来&#xff0c;一直受到广大用户的好评与鼓励。 为了给用户提供更高效、更便捷、更可靠的数据库管理开发体验&#xff0c;SQLynx今日正式发布3.0.0版本&#xff0c;同步在麦聪软件官网上线&#xff0c;全…

k8s入门到实战(十四)—— Helm详细介绍及使用

Helm 使用 Helm 是一个 k8s 应用的包管理工具&#xff0c;类似于 Ubuntu 的 APT 和 CentOS 中的 YUM。 Helm 使用 chart 来封装 k8s 应用的 yaml 文件&#xff0c;我们只需要设置自己的参数&#xff0c;就可以实现自动化的快速部署应用。 Helm 通过打包的方式&#xff0c;支…

常用的AD规则设置

目录 规则编辑器&#xff1a; 间距规则&#xff1a; 线宽规则&#xff1a; 过孔规则&#xff1a; 铺铜设置&#xff1a; 生成制造过孔&#xff1a; 过孔之间间距&#xff1a; 最小阻焊层间距&#xff1a; 丝印到阻焊的距离&#xff1a; 丝印到丝印距离&#xff1a; 走…

mysql 高阶语句 与视图

目录 一 前言 二 msql 高阶语句使用方法 &#xff08;一&#xff09; 查询并排序&#xff08;order by&#xff09; 1&#xff0c;排序方式 2&#xff0c;查询指定列 并排序 3, 条件判断&#xff08;过滤指定行&#xff09; 再查询指定列 并排序 4&#xff0c;查…

Android Viewpager 内外间距

Android使用Viewpager_内外边距 代码&#xff1a; 1、adapter&#xff1a; <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_par…

Ubuntu20.04 安装 OpenCV3 过程中遇到的各种问题及其解决办法

文章目录 前言开始安装OpenCV3问题1&#xff1a;ICV: Failed to download ICV package: ippicv_linux_20151201.tgz.1.1 具体步骤 问题2&#xff1a;/usr/include/c/7/cstdlib:75:15: fatal error: stdlib.h: No such file or directory问题3&#xff1a;error: CODEC_FLAG_GLO…

安装paddle detection心得

一、安装PaddlePaddle conda create -n mypaddle python3.8 conda activate mypaddle python -m pip install paddlepaddle-gpu2.6.0 -i https://mirror.baidu.com/pypi/simple 请确保您的PaddlePaddle安装成功并且版本不低于需求版本。使用以下命令进行验证。 这是CUDA1…

通过修改ospf的COST值来控制路由选路

配置好OSPF之后,发现默认走的是上面 PC1>tracert 192.168.200.1traceroute to 192.168.200.1, 8 hops max (ICMP), press Ctrl+C to stop1 192.168.100.254 16 ms <1 ms 16 ms2 10.10.10.2 15 ms &l

科普 | Runes 预挖矿概念

作者&#xff1a;Jacky X/推&#xff1a;zxl2102492 关于 Runes 协议的前世今生&#xff0c;可以点击阅读这篇文章 &#x1f447; 《简述 Runes 协议、发展历程及最新的「公开铭刻」发行机制的拓展讨论》 什么是传统预挖矿概念 这轮比特币生态爆发之前&#xff0c;预挖矿&…

基于java+springboot+vue实现的超市货品信息管理系统(文末源码+Lw+ppt)23-355

摘 要 随着世界经济信息化、全球化的到来和互联网的飞速发展&#xff0c;推动了各行业的改革。若想达到安全&#xff0c;快捷的目的&#xff0c;就需要拥有信息化的组织和管理模式&#xff0c;建立一套合理、动态的、交互友好的、高效的超市货品信息管理系统。当前的信息管理…

YOLOv9改进策略:注意力机制 | 二阶通道注意力机制(Second-order Channel Attention,SOCA),实现单图超分效果

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文改进内容&#xff1a;CVPR_2019 SOCA注意力&#xff0c;一种基于二阶通道注意力机制&#xff0c;能够单幅图像超分辨率&#xff0c;从原理角度分析能够在小目标检测领域实现大幅涨点效果&#xff01;&#xff01;&#xff01; &am…

APP测试常见功能测试点汇总

1、安装和卸载 安装和卸载是任何一款APP中都属于最基本功能。一旦出错&#xff0c;就属于优先级为紧要的BUG。因此APP的安装和卸载应作为一个测试点多加重视。 1 应用是否可以正常安装&#xff08;命令行安装&#xff1b;豌豆荚&#xff0f;手机助手等第三方软件安装&#xff…

C语言看完我这篇编译与链接就够啦!!!

1. 前言 Hello&#xff01;大家好我是小陈&#xff0c;今天来给大家介绍最详细的C语言编译与链接。 2. 编译和链接 我们通常用的编译器&#xff0c;比如Visual Sudio,这样的IDE(集成开发环境&#xff09;一般将编译和链接的过程一步完成&#xff0c;通常将这这种编译和链接合…

冗余双写方案下数据一致性问题解决及延申问题处理方案

主要整理了采用冗余双写方案后的问题解决方案。 1、问题&#xff1a;冗余双写场景下&#xff0c;如何解决数据一致性问题&#xff1f; 方案一&#xff1a; 直接RPC调用Seata分布式事务框架&#xff0c;采用该方式实现了事务的强一致性&#xff0c;代码逻辑简单的同时业务侵入…

【ORB-SLAM3】在 Ubuntu20.04 上编译 ORM-SLAM3 并使用 D435i、EuRoC 和 TUM-VI 运行测试

【ORB-SLAM3】在 Ubuntu20.04 上编译 ORM-SLAM3 并使用 D435i、EuRoC 和 TUM-VI 运行测试 1 Prerequisites1.1 C11 or C0x Compiler1.2 Pangolin1.3 OpenCV1.4 Eigen3 2 安装 Intel RealSense™ SDK 2.02.1 测试设备2.2 编译源码安装 (Recommend)2.3 预编译包安装 3 编译 ORB-S…

网络编程基本概念(一篇文章掌握基本内容的详细概念,IP,端口号,协议,协议分层,封装和分用,客户端和服务端,请求和回应,两台主机的通信)

IP地址 概念 IP地址主要⽤于标识⽹络主机、其他⽹络设备&#xff08;如路由器&#xff09;的⽹络地址。简单说&#xff0c;IP地址⽤于定位主机的⽹络地址。 就像我们发送快递⼀样&#xff0c;需要知道对⽅的收货地址&#xff0c;快递员才能将包裹送到⽬的地。 IP的格式 IP地址…

优化iproute2中的tc流控规则下发机制

设备基于IP对每个用户配置流量控制规则&#xff0c;规则如下&#xff1a; tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip src 192.168.0.10 flowid 1:10 上面的tc 是一个配置工具&#xff0c;本身是一个应用程序&#xff0c;tc后面的参数通过应用程序参…

vue3+threejs新手从零开发卡牌游戏(十八):己方场上手牌添加画线

手牌上场后&#xff0c;点击己方怪兽区卡牌会跟随鼠标移动画出线条&#xff0c;之后可以通过判断鼠标移动到对方场地的某卡牌进行战斗操作&#xff0c;代码主要改动在game/index.vue文件。 1.添加鼠标移动监听事件&#xff08;移动端&#xff09;&#xff1a; window.addEven…

Scikit Learn中的概率校准曲线

概率校准是一种用于将二分类的输出分数转换为概率的技术&#xff0c;以与目标类的实际概率相关联。在本文中&#xff0c;我们将讨论概率校准曲线以及如何使用Scikit-learn绘制它们。 概率校准 概率校准曲线是二分类问题的正类的预测概率和实际观察频率之间的图。它用于检查分…