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

背包问题和单调栈

背包问题(动态规划)

动态五步曲

  • 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;
http://www.lryc.cn/news/531035.html

相关文章:

  • Java | CompletableFuture详解
  • 【背包问题】二维费用的背包问题
  • Golang 并发机制-5:详解syn包同步原语
  • 实验六 项目二 简易信号发生器的设计与实现 (HEU)
  • 如何用微信小程序写春联
  • LabVIEW无人机航线控制系统
  • C++哈希表深度解析:从原理到实现,全面掌握高效键值对存储
  • Vue.js组件开发-实现字母向上浮动
  • 自研有限元软件与ANSYS精度对比-Bar2D2Node二维杆单元模型-四连杆实例
  • 04树 + 堆 + 优先队列 + 图(D1_树(D11_伸展树))
  • c语言练习题【数据类型、递归、双向链表快速排序】
  • SliverAppBar的功能和用法
  • 五、定时器实现呼吸灯
  • Elasticsearch的索引生命周期管理
  • 【大模型理论篇】最近大火的DeepSeek-R1初探系列1
  • 【数据结构】(4) 线性表 List
  • 【C++ STL】vector容器详解:从入门到精通
  • OpenAI推出Deep Research带给我们怎样的启示
  • 洛谷[USACO08DEC] Patting Heads S
  • CSS 溢出内容处理:从基础到实战
  • Spring Boot项目如何使用MyBatis实现分页查询
  • 飞行汽车中的无刷外转子电机、人形机器人中的无框力矩电机技术解析与应用
  • FreeRTOS学习 --- 队列集
  • 【R语言】R语言安装包的相关操作
  • 15.[前端开发]Day15-HTML+CSS阶段练习(网易云音乐四)
  • 【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户登录
  • 测试方案和测试计划相同点和不同点
  • c++提取矩形区域图像的梯度并拟合直线
  • Unity Shader Graph 2D - 角色身体电流覆盖效果
  • 【LLM-agent】(task4)搜索引擎Agent