背包问题和单调栈
背包问题(动态规划)
动态五步曲
- dp数组及下标索引的含义
- 递推公式
- dp数组如何初始化
- 遍历顺序
- 打印dp数组
01背包:n种物品,有一个,二维数组遍历顺序可以颠倒,(滚动数组)一维数组遍历顺序不可颠倒
完全背包:n种物品,有无限多个
多重背包:n种物品,数量各不相同
01背包
思路:
dp[i][j] ---> i是[0, i]之间的任意物品,放容量为j的背包中,所能得到的最大价值为dp[i][j],分不放物品和放物品的情况。
dp[j] ---> 容量为j的背包所能装的最大价值为dp[j],分为不放物品和放物品的情况,滚动数组倒序遍历,保证每一个物品只被添加一次。
// 01背包,滚动数组
for 物品for 背包(倒序 --> 每个物品只被添加一次 ),正序导致,物品被添加两次,不符合每个物品只能用一次
单调栈模版:
使用场景:比当前元素(左/右)大/小的数
// 输入 int[] nums
int len = nums.length;
// 双端队列,既可以实现 栈 还可以实现 队列
Deque<Integer> stack = new LinkedList<>(); // 栈中存储的是元素的索引
for (int i = 0; i <len; i++) {// 递增栈if(nums[i] > nums[stack.peek()]) {// 如果需要存储可以提前 pop()while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {// 当前索引下标 - 栈顶元素下标int res = i - stack.pop();stack.pop();}}stack.push(nums[i]);
}
return res;
相关文章:
背包问题和单调栈
背包问题(动态规划) 动态五步曲 dp数组及下标索引的含义递推公式dp数组如何初始化遍历顺序打印dp数组 01背包:n种物品,有一个,二维数组遍历顺序可以颠倒,(滚动数组)一维数组遍历顺序不可颠倒…...
Java | CompletableFuture详解
关注:CodingTechWork CompletableFuture 概述 介绍 CompletableFuture是 Java 8 引入的一个非常强大的类,属于 java.util.concurrent 包。它是用于异步编程的一个工具,可以帮助我们更方便地处理并发任务。与传统的线程池或 Future 对比&…...
【背包问题】二维费用的背包问题
目录 二维费用的背包问题详解 总结: 空间优化: 1. 状态定义 2. 状态转移方程 3. 初始化 4. 遍历顺序 5. 时间复杂度 例题 1,一和零 2,盈利计划 二维费用的背包问题详解 前面讲到的01背包中,对物品的限定条件…...
Golang 并发机制-5:详解syn包同步原语
并发性是现代软件开发的一个基本方面,Go(也称为Golang)为并发编程提供了一组健壮的工具。Go语言中用于管理并发性的重要包之一是“sync”包。在本文中,我们将概述“sync”包,并深入研究其最重要的同步原语之一…...
实验六 项目二 简易信号发生器的设计与实现 (HEU)
声明:代码部分使用了AI工具 实验六 综合考核 Quartus 18.0 FPGA 5CSXFC6D6F31C6N 1. 实验项目 要求利用硬件描述语言Verilog(或VHDL)、图形描述方式、IP核,结合数字系统设计方法,在Quartus开发环境下ÿ…...
如何用微信小程序写春联
生活没有模板,只需心灯一盏。 如果笑能让你释然,那就开怀一笑;如果哭能让你减压,那就让泪水流下来。如果沉默是金,那就不用解释;如果放下能更好地前行,就别再扛着。 一、引入 Vant UI 1、通过 npm 安装 npm i @vant/weapp -S --production 2、修改 app.json …...
LabVIEW无人机航线控制系统
介绍了一种无人机航线控制系统,该系统利用LabVIEW软件与MPU6050九轴传感器相结合,实现无人机飞行高度、速度、俯仰角和滚动角的实时监控。系统通过虚拟仪器技术,有效实现了数据的采集、处理及回放,极大提高了无人机航线的控制精度…...
C++哈希表深度解析:从原理到实现,全面掌握高效键值对存储
目录 一、核心组件与原理 1. 哈希函数(Hash Function) 2. 冲突解决(Collision Resolution) 3. 负载因子(Load Factor)与扩容 二、C实现:std::unordered_map 1. 模板参数 2. 关键操作与复…...
Vue.js组件开发-实现字母向上浮动
使用Vue实现字母向上浮动的效果 实现步骤 创建Vue项目:使用Vue CLI来创建一个新的Vue项目。定义组件结构:在组件的模板中,定义包含字母的元素。添加样式:使用CSS动画来实现字母向上浮动的效果。绑定动画类:在Vue组件…...
自研有限元软件与ANSYS精度对比-Bar2D2Node二维杆单元模型-四连杆实例
目录 1、四连杆工程实例以及手算求解 2、四连杆的自研有限元软件求解 2.1、选择单元类型 2.2、导入四连杆工程 2.3、节点坐标定义 2.4、单元连接关系、材料定义 2.5、约束定义 2.6、外载定义 2.7、矩阵求解 2.8、变形云图展示 2.9、节点位移 2.10、单元应力 2.11、…...
04树 + 堆 + 优先队列 + 图(D1_树(D11_伸展树))
目录 一、基本介绍 二、伸展操作 1. 左右情况的伸展 2. 左左情况的伸展 3. 右左情况的伸展 4. 右右情况的伸展 三、其它操作 1. 插入 2. 删除 四、代码实现 一、基本介绍 伸展树是一种二叉搜索树,伸展树也是一种平衡树,不过伸展树并不像AVL树那…...
c语言练习题【数据类型、递归、双向链表快速排序】
练习1:数据类型 请写出以下几个数据的数据类型 整数 a a 的地址 存放a的数组 b 存放a的地址的数组 b的地址 c的地址 指向 printf 函数的指针 d 存放 d的数组 整数 a 的类型 数据类型是 int a 的地址 数据类型是 int*(指向 int 类型的指针) …...
SliverAppBar的功能和用法
文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了SliverGrid组件相关的内容,本章回中将介绍SliverAppBar组件.闲话休提,让我们一起Talk Flutter吧。 1 概念介绍 我们在本章回中介绍的SliverAppBar和普通的AppBar类似,它们的…...
五、定时器实现呼吸灯
5.1 定时器与计数器简介 定时器是一种通过对内部时钟脉冲计数来测量时间间隔的模块。它的核心是一个递增或递减的寄存器(计数器值)。如果系统时钟为 1 MHz,定时器每 1 μs 计数一次。 计数器是一种对外部事件(如脉冲信号ÿ…...
Elasticsearch的索引生命周期管理
目录 说明零、参考一、ILM的基本概念二、ILM的实践步骤Elasticsearch ILM策略中的“最小年龄”是如何计算的?如何监控和调整Elasticsearch ILM策略的性能? 1. **监控性能**使用/_cat/thread_pool API基本请求格式请求特定线程池的信息响应内容 2. **调整…...
【大模型理论篇】最近大火的DeepSeek-R1初探系列1
1. 背景介绍 这一整个春节,被DeepSeek-R1刷屏。各种铺天盖地的新闻以及老板发的相关信息,着实感受到DeepSeek-R1在国外出圈的震撼。 DeepSeek推出了新的推理模型:DeepSeek-R1-Zero 和 DeepSeek-R1。DeepSeek-R1-Zero 是一个在没有经过监督微调…...
【数据结构】(4) 线性表 List
一、什么是线性表 线性表就是 n 个相同类型元素的有限序列,每一个元素只有一个前驱和后继(除了第一个和最后一个元素)。 数据结构中,常见的线性表有:顺序表、链表、栈、队列。 二、什么是 List List 是 Java 中的线性…...
【C++ STL】vector容器详解:从入门到精通
【C STL】vector容器详解:从入门到精通 摘要:本文深入讲解C STL中vector容器的使用方法,涵盖常用函数、代码示例及注意事项,助你快速掌握动态数组的核心操作! 一、vector概述 vector是C标准模板库(STL&am…...
OpenAI推出Deep Research带给我们怎样的启示
OpenAI 又发新产品了,这次是面向深度研究领域的智能体产品 ——「Deep Research」,貌似被逼无奈的节奏… 在技术方面,Deep Research搭载了优化后o3模型并通过端到端强化学习在多个领域的复杂浏览和推理任务上进行了训练。因没有更多的技术暴露…...
洛谷[USACO08DEC] Patting Heads S
题目传送门 题目难度:普及/提高一 题面翻译 今天是贝茜的生日,为了庆祝自己的生日,贝茜邀你来玩一个游戏。 贝茜让 N N N ( 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1≤N≤105) 头奶牛坐成一个圈。除了 1 1 1 号与 N N N 号奶牛外࿰…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
