背包问题和单调栈
背包问题(动态规划)
动态五步曲
- 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 号奶牛外࿰…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果