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

【线性dp必学四道题】线性dp四道经典例题【最长上升子序列】、【最长公共子序列】、【最长公共上升子序列(maxv的由来)】【最长公共子串】

【最长上升子序列】、【最长公共子序列】、【最长公共上升子序列】

    • 最长上升子序列
        • f[i] 表示以i结尾的最长子序列
    • 最长公共子序列
        • f[i][j] 表示 a前i 和 b前j个 最长公共长度
    • 最长公共上升子序列
        • f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合
    • 最长公共子串

最长上升子序列

在这里插入图片描述

f[i] 表示以i结尾的最长子序列

由于我们遍历到i时候
我们需要比较i前面的数据

我们发现如果i 大于 j

那么i就可以拼接在 j 后面

如果f[j] 就是j最长的了
那就
f[i] = f[j] + 1的长度
所以
f[i] 表示以i结尾的最长子序列

#include<iostream>using namespace std;const int N = 1100;int a[N];
int f[N];
int res = 0;
int n;int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];a[0] = -0x3f3f3f3f;for(int i = 1; i <= n; i++){for(int j = 0; j <= i ; j++){if(a[j] < a[i])f[i] = max(f[i],f[j]+1);res = max(res,f[i]);}}cout << res;return 0;
}

最长公共子序列

在这里插入图片描述

f[i][j] 表示 a前i 和 b前j个 最长公共长度

#include<iostream>using namespace std;const int N = 1010;int f[N][N];
char a[N],b[N];
int n,m;int main()
{cin >> n >> m;cin >> a+1 >> b+1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(a[i]==b[j]){f[i][j] = f[i-1][j-1]+1;}else{f[i][j] = max(f[i-1][j],f[i][j-1]);}}}cout << f[n][m];return 0;
}

最长公共上升子序列

在这里插入图片描述

f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合

这道题如何理解?

  1. 记住f[i][j] 表示什么
  2. 当b的j和i 相等时,我们常规思路是就在b数组中按着第一道题的逻辑 循环遍历之前的值,但是这样是麻烦的。我们需要一种方法,不需要遍历就知道之前的最大值,可以定义一个变量maxv,如果i和j相等,直接等于maxv,如果不相等,那么f[i][j] = f[i-1][j]
  3. 如果a[i]>b[j]
    那么maxv = max(maxv,f[i-1][j]+1);

maxv的由来
在这里插入图片描述

#include<iostream>using namespace std;const int N = 3030;int f[N][N];
int a[N],b[N];
int n;int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) cin >> b[i];for(int i = 1; i <= n; i++){int maxv = 1;for(int j = 1; j <= n; j++){f[i][j] = f[i-1][j];if(a[i]==b[j]){f[i][j] = maxv;}if(a[i]>b[j])maxv = max(maxv,f[i-1][j]+1);}}int ans = 0;for(int i = 0; i <= n; i++){ans = max(f[n][i],ans);}cout << ans;return 0;
}

最长公共子串

在这里插入图片描述
在这里插入图片描述

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e4 + 10;
char str1[N], str2[N];int f[N][N];//注意空间限制为256MB,即为2^(8 + 20) = 2^28个字节,
//而一个int型变量占4个字节,那么最多有2^26个int变量,大约为64000000个变量,而此时定义f[N][N]最多有大于1e8个变量,会爆内存
//更何况还有存字符串的空间int main()
{cin >> str1 + 1 >> str2 + 1;    int len1 = strlen(str1 + 1), len2 = strlen(str2 + 1);int res = 0;for (int i = 1; i <= len1; i++){//如果最后一位为数字if (str1[i] >= '0' && str1[i] <= '9'){for (int j = 1; j <= len2; j++)f[i][j] = 0;continue;    }for (int j = 1; j <= len2; j++){//如果最后一位相同且不为数字if (str1[i] == str2[j])f[i][j] = f[i - 1][j - 1] + 1;else f[i][j] = 0;res = max(res, f[i][j]);}}cout << res << endl;return 0;
}

观察我们在状态计算的过程,第i层循环的值,仅与第i-1层循环的值有关
我们可以联想到01背包的优化,利用滚动数组来简化空间复杂度
既然要用到删除一维空间的优化方法,一定要注意:
二维中:f[i][j] = f[i - 1][j - 1] + 1;
在一维中,由于f[j] = f[j - 1],小的j已经被更新,那么就不是上一层(i-1)的数据了
所以必须从大到小遍历

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e4 + 10;
char str1[N], str2[N];int f[N];int main()
{cin >> str1 + 1 >> str2 + 1;    int len1 = strlen(str1 + 1), len2 = strlen(str2 + 1);int res = 0;//用于保存答案for (int i = 1; i <= len1; i++){//如果最后一位为数字if (str1[i] >= '0' && str1[i] <= '9'){for (int j = 1; j <= len2; j++)f[j] = 0;continue;    }for (int j = len2; j >= 1; j--){//如果最后一位相同且不为数字if (str1[i] == str2[j])f[j] = f[j - 1] + 1;else f[j] = 0;res = max(res, f[j]);}}cout << res << endl;return 0;
}

相关文章:

【线性dp必学四道题】线性dp四道经典例题【最长上升子序列】、【最长公共子序列】、【最长公共上升子序列(maxv的由来)】【最长公共子串】

【最长上升子序列】、【最长公共子序列】、【最长公共上升子序列】 最长上升子序列f[i] 表示以i结尾的最长子序列 最长公共子序列f[i][j] 表示 a前i 和 b前j个 最长公共长度 最长公共上升子序列f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合 最长公共子…...

追寻幸福:探索幸福的关键特征和行为

目录 1. 积极的心态 2. 良好的人际关系 3. 自我接纳和自尊 4. 追求意义和目标 5. 健康的身心状态 6. 感知和实现个人价值 幸福是一个主观的感受&#xff0c;因此不同的人对于幸福的定义和追求方式可能会有所不同。然而&#xff0c;有一些共同的特点和行为模式&#xff0c…...

Redis-02-集群

一、redis5搭建集群 1.1、案例&#xff1a;搭建6台redis主机&#xff0c;配置如下 redis并发量&#xff1a;https://www.gxlcms.com/redis-350423.html主机IP&#xff1a;192.168.168.60~65修改redis配置文件hash槽移动&#xff0c;槽内的数据也随之移动 [root60 ~]# vim /e…...

【2023 · CANN训练营第一季】MindSpore模型快速调优攻略 第三章——MindSpore云上调试调优

1.ModelArts云上调试调优 ModelArts密钥初始化 详细教程&#xff1a; 初始化OBS服务 创建训练作业 2.MindSpore IDE插件效率提升 通过智能代码块推荐、代码自动补全等特性&#xff0c;提升MindSpore脚本开发效率&#xff0c;对接ModelArts云服务&#xff0c;实现模型训…...

python笔记17_实例演练_二手车折旧分析p2

…… 书接上文 4.车辆等级维度 探查车龄为5年的车辆&#xff0c;折旧价值与车辆等级的关系。 # 筛选出车龄为5的数据创建新表 data_age5 data[data[age] 5] data_age5 # 分组聚合计算均值 data_car_level data_age5.groupby(car_level_name)[lowest_price].mean().reset…...

android 12.0长按Power弹出关机对话框去掉屏幕截图和紧急呼救功能

1.概述 在12.0的系统长按关机键,会弹出关机的对话框,关机对话框里面由关机重启截图和紧急呼叫等功能,而由于开发功能需求要求去掉屏幕截图和紧急呼叫等功能,所以就要先找到关机对框的代码 然后实现功能 功能分析: 长按电源键弹出关机对话框,通过adb shell命令发现 就是f…...

2023年下半年软考高级需要报班吗?

首先&#xff0c;对于软考高级考试报班与否的问题&#xff0c;需要根据自身的情况来做出决定。如果你有较强的自学能力&#xff0c;且具备丰富的实际工作经验和技术知识&#xff0c;那么不报班也完全可以自学备考。但如果你对软件工程的知识掌握程度较低&#xff0c;或者时间紧…...

使用WordPress提高企业敏捷性

喜欢WordPress的原因有很多&#xff1a;该平台非常适合内容管理以及控制预算。此外&#xff0c; 在 提高开发效率和简化项目管理方面&#xff0c;WordPress可以通过多种方式提供帮助。 对于任何企业业务&#xff0c;目标始终是在不影响质量的情况下更快地启动项目、发布修复和…...

SSM编程---Day 07

目录 SpringMVC 一、概念 二、springMVC的请求处理流程 三、mvc:annotation-driven 标签的作用 四、HandlerMapping、Handler和HandlerAdapter的介绍 五、SpringMVC 体系结构 六、SpringMVC的常用注解 七、view和controller之间的传值 SpringMVC 一、概念 1、 Spring…...

Seata术语

1.什么是Seata Seata是一款开源的分布式事务解决方案&#xff0c;致力于在微服务架构下提供高性能和简单易用的分布式事务服务。 官网 2.Seata能干嘛 一个典型的分布式事务过程 分布式事务处理过程的一ID三组件模型&#xff1a; Transaction ID XID 全局唯一的事务ID三组…...

【Axure教程】通过文本框维护下拉列表选项

下拉列表&#xff08;Dropdown List&#xff09;是一种常见的用户界面元素&#xff0c;用于提供一组选项供用户选择。它通常以一个展开的列表形式出现&#xff0c;用户可以点击或选择列表中的一个选项。一般来说&#xff0c;他的选项值是由系统代码组成的&#xff0c;所以一般是…...

【C++】基础知识--输入/输出(5)

前面部分的示例程序几乎没有提供与用户的交互&#xff08;如果有的话&#xff09;。他们只是在屏幕上打印简单的值&#xff0c;但标准库提供了许多其他方式通过其输入/输出功能与用户交互。本节将简要介绍一些最有用的方法。 cin标准输入cout标准输出cerr标准错误&#xff08;输…...

经典文献阅读之--PIBT(基于可见树的实时规划方案)

0. 简介 作为路径规划而言&#xff0c;不单单有单个机器人自主路径规划&#xff0c;近年来随着机器人行业的兴起&#xff0c;多机器人自主路径规划也越来越受到关注&#xff0c;对于多智能体寻路(MAPF)。一般的操作会给定一个地图、机器人集群、以及它们的初始位置和目的地&am…...

SAP-MM-计算方案字段解析

01、 “步骤”&#xff1a;标识此条件类型在计算方案中的顺序编号&#xff0c;此编号会影响到后续业务中条件类型的排序&#xff0c;不同条件类型之间的编号最好间隔大一些&#xff0c;这样设置便于以后对计算方案进行扩展&#xff1b; 02、 “计数器”&#xff1…...

go-gf框架两个表以事务方式写入示例

下面是对每一行代码的中文解释&#xff1a; // 创建数据库连接对象 var tx gdb.TX这行代码声明了一个名为tx的变量&#xff0c;类型为gdb.TX&#xff0c;表示数据库事务对象。 // 开启事务 if tx, err g.DB().Ctx(ctx).Begin(ctx); err nil {这行代码通过在数据库连接&…...

2023-5-31第三十一天

conform顺从&#xff0c;遵从&#xff0c;一致 squeeze挤压 proprietary专卖权&#xff0c;专利的&#xff0c;所有的 endeavor努力&#xff0c;尽力 comprise由...组成&#xff0c;包含 compose组成&#xff0c;写作 compact小型的 consult咨询&#xff0c;查阅 expan…...

什么是MQTT?mqtt协议和http协议区别

摘要&#xff1a; 什么是MQTT&#xff1f;MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;译为&#xff1a;消息队列遥测传输&#xff0c;是一种轻量级的通讯协议&#xff0c;用于在网络上传输消息。MQTT 最初由 IBM 发布&#xff0c;后来成为 OASIS&#xf…...

平台使用篇 | 批处理(bat)脚本使用教程(四)

导读 一个开启多机软件在环仿真的批处理文件 (对应卓面RflyTools文件夹中SITLRun快捷方式)&#xff0c;双击它&#xff0c;输入想要生成的飞机数量&#xff0c;即可生成多机软件在环仿真&#xff0c;等待RflySim3D显示3DFixed 4/4&#xff0c;然后可通过QGC控制飞机起飞。运行…...

接口的讲解

在这里之前我想童鞋们都学习过了springmvc。mybatis-plus。Springboot等一些框架 那么下面我们就整合这些框架 我们通过写crud这些接口 写接口的第一步就是引入pom文件 在pom文件里引入一下几种依赖 引入父级工程 thymeleaf导入模版工具类 SpringMVCjar包文件 热部署工具 l…...

G0第21章 :gin框架介绍、RESTful API、Gin渲染

G0第21章 &#xff1a;gin框架 01 内容介绍 https://gin-gonic.com/zh-cn/docs/ web本质 Web是基于HTTP协议进行交互的应用网络Web就是通过使用浏览器/APP访问的各种资源 package mainimport ("fmt""net/http" )func sayHello(w http.ResponseWriter, r…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...