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

【线性DP】模型总结(terse版)

【线性DP】模型总结

最长上升子序列

DP法

​ dp[i]表示以i结尾的最长上升子序列的长度。

​ 对于每个i,遍历j=1~i-1,若a[j] < a[i], 则dp[i] = max(dp[i], dp[j] + 1);

二分法

​ 可以优化时间复杂度。

​ dp[]数组用来存储当前最长上升子序列。

​ 若dp[]数组的最末尾的值小于当前原序列的值,则将这个值加入dp[]数组末尾。

​ 否则,使用Lower_bound找到dp[]数组中第一个大于该值的元素,替换。

如果需要输出序列:定义s[]数组,记录下标,随dp[]数组更新。

最长公共子序列

​ 定义dp[] []二维数组,表示a串以i结尾,b串以j结尾的最长公共子序列。

​ 枚举i = 1 ~ a.size(), j = 1 ~ b.size().

​ 若a[i - 1] == b[j - 1], dp[i] [j] = dp[i - 1] [j - 1] + 1;

​ 否则 dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1])。

最大子矩阵

​ 首先遍历len=1~n,再将i从1遍历,确定j的值,得出一个len行n列的值,每一列对应相加,得到1行n列的序列,再求线性最大子段和

​ 得到的最大值就是Len行(从i到j)的最大子矩阵的值。

​ 每次求都不断更新ans = max(ans, dp[i])。

最大正方形

​ 给出一个01矩阵,求都是1的最大正方形的边长

​ dp[i] [j] 表示以x=i,y=j为右下角的最大正方形。 若a[i - 1] [j]、a[i] [j - 1]、a[i - 1] [ j - 1]均为1,则正方形的边长可以加一,即dp[i] [j] + 1。

​ 否则,dp[i] [j] = min(dp[i - 1] [j]、dp[i] [j - 1]、dp[i - 1] [ j - 1])

题目:最大子矩阵

代码:AC代码

最大子段和

线性

​ 定义dp[]一维数组,dp[i]表示以i结尾的最大字段和的值。

​ 有两种情况:

​ 1.独自成串:dp[i] = a[i];

​ 2.与前一个元素连成串:dp[i] = dp[i - 1] + a[i];

​ 合并得:dp[i] = max(dp[i - 1] + a[i], a[i])。

​ 答案是dp[1~n]中最大值。

环形

​ 依照上述方法,求出序列和、最大字段和、最小字段和。

​ 答案 = max(和 - 最小字段和, 最大字段和)。

子集和问题

​ 定义dp[] []bool类二维数组,dp[i] [j] 表示前i个数存在一个子集和等于j,答案就是dp[n] [M]。

​ s[]数组记录集合中元素。

​ 若s[i] > j,则不能放入, dp[i] [j] = dp[i - 1] [j]。

​ 否则, 放不放皆可,dp[i] [j] = (dp[i - 1] [j] || dp[i - 1] [j - s[i]])。

行走问题

​ 类似于爬楼梯。

​ 给出目标阶梯数和每步最多爬几层。

​ 对于每个dp[i]表示走到第i层的步数总数,每次遍历j=i - k~i - 1,dp[i] += dp[j]。

​ 答案就是dp[n]。

相关文章:

【线性DP】模型总结(terse版)

【线性DP】模型总结 最长上升子序列 DP法 ​ dp[i]表示以i结尾的最长上升子序列的长度。 ​ 对于每个i&#xff0c;遍历j1~i-1,若a[j] < a[i], 则dp[i] max(dp[i], dp[j] 1); 二分法 ​ 可以优化时间复杂度。 ​ dp[]数组用来存储当前最长上升子序列。 ​ 若dp[]数…...

conda 常用命令

conda 常用命令 一、创建环境二、删除环境三、环境重命名四 、查看环境列表五、进入某个虚拟环境六、退出当前环境七、查看当前虚拟环境下的所有安装包八、安装或卸载包(进入虚拟环境之后&#xff09;九、分享虚拟环境十、源服务器管理十一、升级十二、卸载十三、卸载十四、pip…...

前端面试:【异步编程】Callback、Promise和Async/Await

嗨&#xff0c;亲爱的JavaScript探险家&#xff01;在JavaScript开发的旅程中&#xff0c;你会经常遇到异步编程的需求。为了处理异步操作&#xff0c;JavaScript提供了多种机制&#xff0c;包括Callbacks、Promises和Async/Await。本文将深入介绍这些机制&#xff0c;让你能够…...

大数据(四):Pandas的基础应用详解

专栏介绍 结合自身经验和内部资料总结的Python教程&#xff0c;每天3-5章&#xff0c;最短1个月就能全方位的完成Python的学习并进行实战开发&#xff0c;学完了定能成为大佬&#xff01;加油吧&#xff01;卷起来&#xff01; 全部文章请访问专栏&#xff1a;《Python全栈教…...

计算机网络第3章(数据链路层)

计算机网络第3章&#xff08;数据链路层&#xff09; 3.1 数据链路层概述3.1.1 概述3.1.2 数据链路层使用的信道3.1.3 三个重要问题 3.2 封装成帧3.2.1 介绍3.2.2 透明传输3.2.3 总结 3.3 差错检测3.3.1 介绍3.3.2 奇偶校验3.3.3 循环冗余校验CRC(Cyclic Redundancy Check)3.3.…...

stm32之4.时钟体系

3.时钟体系(给单片机提供一个非常稳定的频率信号) ①可以使用三种不同的时钟源来驱动系统时钟&#xff08;SYSCLK&#xff09;&#xff0c;CPU运行的频率为168MHZ&#xff1b; HSI(RC振荡器时钟&#xff0c;也就是高速内部时钟&#xff0c;一般来说很少用&#xff0c;因为精度…...

RPC和HTTP协议

RPC 全称&#xff08;Remote Procedure Call&#xff09;&#xff0c;它是一种针对跨进程或者跨网络节点的应用之间的远程过程调用协议。 它的核心目标是&#xff0c;让开发人员在进行远程方法调用的时候&#xff0c;就像调用本地方法一样&#xff0c;不需要额外为了完成这个交…...

BUGFix:onnx -> TensorRT转换过程失败

先附上相关的onnx2trt的部分代码&#xff1a; def onnx2trt(onnx_path):logger trt.Logger(trt.Logger.ERROR)builder trt.Builder(logger)network builder.create_network(1 << int(trt.NetworkDefinitionCreationFlag.EXPLICIT_BATCH))parser trt.OnnxParser(netw…...

FFMPEG小白常用命令行

序列帧转H264视频 ffmpeg -r 60 -f image2 -s 1920x1080 -i fram%d.jpg -vcodec libx264 -crf 25 -pix_fmt yuv420p test.mp4 -vcodec h264 .\ffmpeg -r 60 -f image2 -s 1920x1080 -i %04d.jpeg -vcodec h264 test.mp4 %04d 表示用零来填充直到长度为4&#xff0c;i.e 000…...

个性定制还是纯粹简约:探寻界面选择背后的心理宇宙

在数码世界中&#xff0c;我们的界面选择成为了一张架起的桥梁&#xff0c;连接着个性的渴望与效率的追求。当我们面对个性化定制界面和极简版原装界面&#xff0c;我们仿佛站在了一座分岔路口&#xff0c;左右各有一片令人心驰神往的风景。究竟是走向五光十色的个性世界&#…...

【Java 高阶】一文精通 Spring MVC - 转发重定向(四)

&#x1f449;博主介绍&#xff1a; 博主从事应用安全和大数据领域&#xff0c;有8年研发经验&#xff0c;5年面试官经验&#xff0c;Java技术专家&#xff0c;WEB架构师&#xff0c;阿里云专家博主&#xff0c;华为云云享专家&#xff0c;51CTO 专家博主 ⛪️ 个人社区&#x…...

嵌入式Linux开发实操(十):ADC接口开发

#前言 ADC就是模数转换,可以用来接一些模拟量设备,所谓模拟量就是波形不是方波而是各种包络形状的波形的信号,比如电压、电流等电信号或压力、温度、湿度、位移、声音等非电信号,ADC就是将这些信号转换为数字方波信号,以便于信息传递的。 #ADC硬件设计 key按键连接了AD…...

精进语言模型:探索LLM Training微调与奖励模型技术的新途径

大语言模型训练&#xff08;LLM Training&#xff09; LLMs Trainer 是一个旨在帮助人们从零开始训练大模型的仓库&#xff0c;该仓库最早参考自 Open-Llama&#xff0c;并在其基础上进行扩充。 有关 LLM 训练流程的更多细节可以参考 【LLM】从零开始训练大模型。 使用仓库之…...

数据采集:selenium 提取 Cookie 自动登陆

写在前面 工作需要&#xff0c;简单整理博文内容涉及 通过 selenium 实现自动登陆理解不足小伙伴帮忙指正 对每个人而言&#xff0c;真正的职责只有一个&#xff1a;找到自我。然后在心中坚守其一生&#xff0c;全心全意&#xff0c;永不停息。所有其它的路都是不完整的&#x…...

[Go版]算法通关村第十三关黄金——数字数学问题之数论问题(最大公约数、素数、埃氏筛、丑数)

目录 题目&#xff1a;辗转相除法&#xff08;求最大公约数&#xff09;思路分析&#xff1a;辗转相除法&#xff08;也叫欧几里得算法&#xff09;gcd(a,b) gcd(b,a mod b)复杂度&#xff1a;时间复杂度 O ( n l o g ( m a x ) ) O(nlog(max)) O(nlog(max))、空间复杂度 O (…...

Qt双击某一文件通过自己实现的程序打开,并加载文件显示

双击启动 简述方法一方法二注意 简述 在Windows系统中&#xff0c;双击某类扩展名的文件&#xff0c;通过自己实现的程序打开文件&#xff0c;并正确加载及显示文件。有两种方式可以到达这个目的。 对于系统不知道的扩展名的文件&#xff0c;第一次打开时&#xff0c;需要自行…...

硬件产品的量产问题------硬件工程师在产线关注什么

前言&#xff1a; 产品开发测试无误&#xff0c;但量产缺遇到很多不良甚至DOA问题。 硬件开发过程中如何确保产线的治具、生产及硬件工程师在产线需要关注一些什么。 坚信&#xff1a;好的产品是要可以做出来的。 1、禁忌&#xff1a; 禁忌热插拔&#xff1b;禁忌测试不防呆…...

Vulnhub系列靶机--- Hackadmeic.RTB1

系列&#xff1a;Hackademic&#xff08;此系列共2台&#xff09; 难度&#xff1a;初级 信息收集 主机发现 netdiscover -r 192.168.80.0/24端口扫描 nmap -A -p- 192.168.80.143访问80端口 使用指纹识别插件查看是WordPress 根据首页显示的内容&#xff0c;点击target 点击…...

redis高级----------主从复制

redis的四种模式&#xff1a;单例模式&#xff1b;主从模式&#xff1b;哨兵模式&#xff0c;集群模式 一、主从模式 单例模式虽然操作简单&#xff0c;但是不具备高可用 缺点&#xff1a; 单点的宕机引来的服务的灾难、数据丢失单点服务器内存瓶颈&#xff0c;无法无限纵向扩…...

posgresql通过PL/pgSQL脚本统一修改某字段大小写

项目在做postgresql数据库适配时遇到了某些问题&#xff0c;需要统一将某个模式含id字段的全部表&#xff0c;将id字段由小写转换为大写&#xff0c;可以通过PL/pgSQL脚本实现。 先确保当前用户有足够的权限 DO $$ DECLARE current_table text;current_column text; BEGIN --…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...