当前位置: 首页 > 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 --…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...