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

leetcode原题: 堆箱子(动态规划实现)

题目:

给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

示例:

 输入:box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
 输出:6


 输入:box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
 输出:10

解题思路:

1.先对数组进行排序,我们按照箱子的第一个值宽来进行升序排序(这里为什么不用高呢?因为尽管我们需要计算的是最大高度,但最终堆箱子需要宽、深、高都小于下面的箱子,所以直接按宽来排序) 

2.用dp[i]记录以第i个箱子结尾的箱堆的最大高度

3.返回dp[n]

源代码如下:

class Solution {
public:int pileBox(vector<vector<int>>& box) {//先按箱子的宽wi 进行升序排序sort(box.begin(),box.end(),[](const vector<int>& a,const vector<int>& b){return a[0]<b[0];});//计算有多少个箱子int n=box.size();vector<int> dp(n,0);//dp[i]表示以第i个箱子结尾的最高箱子高度//起始的高度就是第一个箱子的高度dp[0]=box[0][2];//ans记录答案int ans=dp[0];//从第二个箱子开始找最大高度的箱子堆for(int i=1;i<n;i++){//每找一次 都要讲当前最大高度置为0int max_hi=0;//找第i个箱子之前的其他箱子,组成箱子堆for(int j=0;j<i;j++){//符合条件,长宽高都小于下面的箱子,才能堆到上面if(box[j][0]<box[i][0]&&box[j][1]<box[i][1]&&box[j][2]<box[i][2]){//当前最大高度max_hi=max(max_hi,dp[j]);}//dp[i]就等于当前最大高度+当前箱子的高度dp[i]=max_hi+box[i][2];//更新答案的最大值ans=max(ans,dp[i]);}}//返回答案return ans;}
};

相关文章:

leetcode原题: 堆箱子(动态规划实现)

题目&#xff1a; 给你一堆n个箱子&#xff0c;箱子宽 wi、深 di、高 hi。箱子不能翻转&#xff0c;将箱子堆起来时&#xff0c;下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法&#xff0c;搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。 输入使用数组…...

Java中数组和集合的对比,以及什么情况下使用数组更合适,什么情况下使用集合更合适。集合的基本介绍和集合体系图。

在Java中&#xff0c;数组和集合&#xff08;Java集合框架&#xff09;都用于存储多个元素。它们各自有不同的特点和适用场景。下面我会对数组和集合进行对比&#xff0c;并解释何时使用集合更好&#xff0c;以及何时使用数组更合适。 数组和集合的对比&#xff1a; 数组&…...

STM32之17.PWM脉冲宽度调制

一LED0脉冲宽度调制在TIM14_CHI&#xff0c;先将LED&#xff08;PF9&#xff09;代码配置为AF推挽输出模式&#xff0c;将PF9引脚连接到TIM14&#xff0c; #include <stm32f4xx.h>static GPIO_InitTypeDef GPIO_InitStruct;void Led_init(void) {//打开端口F的硬件时钟&a…...

VS2015打开Qt的pro项目文件 报错

QT报错&#xff1a;Project ERROR: msvc-version.conf loaded but QMAKE_MSC_VER isn‘t set 解决方法&#xff1a; 找到本机安装的QT路径&#xff0c;找到“msvc-version.conf”文件&#xff0c;用记事本打开&#xff0c; 在其中添加版本“QMAKE_MSC_VER 1900”保存即可。 …...

骨传导耳机会头疼吗?骨传导耳机会对身体不好吗

一般情况下&#xff0c;骨传导耳机不会引起头疼。由于骨传导耳机的工作原理是通过将声音传导到颞骨和耳部周围的骨骼来传达音频信号&#xff0c;而不是直接进入耳道&#xff0c;因此不会对耳朵造成压力或产生耳疼的感觉。 然而&#xff0c;每个人的感受和体验可能不同&#xff…...

【面试题系列】(一)

Redis有哪些数据结构&#xff1f;其底层是怎么实现的&#xff1f; Redis 系列&#xff08;一&#xff09;&#xff1a;深入了解 Redis 数据类型和底层数据结构 字符串&#xff08;String&#xff09;&#xff1a; 用于存储文本或二进制数据。可以执行字符串的基本操作&#xf…...

vscode C++17便捷配置教程(懒人版)

环境链接 以上是已经配置好的c17环境链接&#xff0c;直接下载解压即可&#xff08;注意文件路径上不要带有中文&#xff09; 下载解压之后按照msys64-mingw64-bin路径打开 然后单击该路径右方空白区域可直接复制路径 然后点击开始菜单搜索“环境变量“并打开&#xff08;如…...

动态数组实现链地址法哈希表

通常情况下哈希函数的输入空间远大于输出空间&#xff0c;因此理论上哈希冲突是不可避免的。比如&#xff0c;输入空间为全体整数&#xff0c;输出空间为数组容量大小&#xff0c;则必然有多个整数映射至同一数组索引。 解决哈希冲突方法常见有&#xff1a;链地址法、开放寻址…...

Eclipse(STS):pom.xml 报错:Multiple markers at this line

pom.xml 报错&#xff1a;Multiple markers at this line STS中&#xff0c;项目能够正常运行&#xff0c;但是 pom.xml 报错&#xff1a;Multiple markers at this line 项目本身没有任何修改&#xff0c;之前不报错的&#xff0c;突然报错了。 Multiple markers at this li…...

CSerialPort教程4.3.x (3) - CSerialPort在MFC中的使用

CSerialPort教程4.3.x (3) - CSerialPort在MFC中的使用 环境&#xff1a; 系统&#xff1a;windows 10 64位 编译器&#xff1a;Visual Studio 2008前言 CSerialPort项目是一个基于C/C的轻量级开源跨平台串口类库&#xff0c;可以轻松实现跨平台多操作系统的串口读写&#x…...

2022版 的IDEA创建一个maven项目(超详细)

一.设置idea中指定的maven的位置以及本地存储仓库 开发中一般我们使用自己下载的maven&#xff0c;不使用IDEA工具自带的&#xff0c;这就需要将我们下载的maven配置到IDEA工具中&#xff0c;配置如下图所示&#xff1a; 或者直接 快捷键 CtrlAltS 直接进入设置 maven home pa…...

lvs实现DR模型搭建

目录 一&#xff0c;实现DR模型搭建 1&#xff0c; 负载调度器配置 1.1调整ARP参数 1.2 配置虚拟IP地址重启网卡 1.3 安装ipvsadm 1.4 加载ip_vs模块 1.5 启动ipvsadm服务 1.6 配置负载分配策略 1.7 保存策略 2&#xff0c; web节点配置 1.1 调整ARP参数 1.2 配置虚拟I…...

设计模式之迭代器模式(Iterator)的C++实现

1、迭代器模式的提出 在软件开发过程中&#xff0c;操作的集合对象内部结构常常变化&#xff0c;在访问这些对象元素的同时&#xff0c;也要保证对象内部的封装性。迭代器模式提供了一种利用面向对象的遍历方法来遍历对象元素。迭代器模式通过抽象一个迭代器类&#xff0c;不同…...

【0基础入门Python Web笔记】二、python 之逻辑运算和制流程语句

二、python 之逻辑运算和制流程语句 逻辑运算控制流程语句条件语句&#xff08;if语句&#xff09;循环结构&#xff08;for循环、while循环&#xff09;continue、break和pass关键字控制流程语句的嵌套以及elif 更多实战项目可进入下方官网 逻辑运算 Python提供基本的逻辑运算…...

容器——Docker

1.安装docker服务&#xff0c;配置镜像加速器 2.下载系统镜像&#xff08;Ubuntu、 centos&#xff09; 3.基于下载的镜像创建两个容器 &#xff08;容器名一个为自己名字全拼&#xff0c;一个为首名字字母&#xff09; 4.容器的启动、 停止及重启操作 5.怎么查看正在运行的容器…...

SQL注入之宽字节注入

文章目录 宽字节注入是什么&#xff1f;注入练习让转义符失效联合查询 代码审计 宽字节注入是什么&#xff1f; 宽字节注入准确来说不是注入手法&#xff0c;而是另外一种比较特殊的情况。宽字节注入的目的是绕过单双引号转义。 宽字节注入是一种绕过单双引号转义的手段&#x…...

MyBatis动态sql

文章目录 一、MyBatis动态sql1.1 概述1.2 if元素1.3 foreach元素 二、模糊查询2.1 使用#{字段名}2.2 使用${字段名}2.3 使用concat{%,#{字段名},%}2.4 mybatis中#与$的区别 三、MyBatis结果映射3.1 区别3.2 应用场景 一、MyBatis动态sql 1.1 概述 MyBatis是一个Java持久化框架…...

L1-032 Left-pad 测试点全过

题目 根据新浪微博上的消息&#xff0c;有一位开发者不满NPM&#xff08;Node Package Manager&#xff09;的做法&#xff0c;收回了自己的开源代码&#xff0c;其中包括一个叫left-pad的模块&#xff0c;就是这个模块把javascript里面的React/Babel干瘫痪了。这是个什么样的…...

ssm+Vue.js在线购物系统源码和论文

ssmVue.js在线购物系统源码和论文049 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势…...

港联证券|指数或进入磨底阶段 短期关注环保、煤炭等板块

磨底历来都不是一天能达到的&#xff0c;比方2018年的政策底到商场底&#xff0c;半途也阅历两个多月时间。当下政策底出现之后至今也有近一个月时间&#xff0c;并且下跌量能不断缩短&#xff0c;心情面也降至冰点&#xff0c;种种迹象阐明离真正商场底的构成已经不远了。此时…...

OpenClaw智能截图:nanobot自动识别图片中的文字信息

OpenClaw智能截图&#xff1a;nanobot自动识别图片中的文字信息 1. 为什么需要智能截图工具 在日常工作和学习中&#xff0c;我们经常遇到需要从图片中提取文字的场景。比如截取网页上的技术文档片段、保存会议白板上的讨论要点、或者整理纸质书籍中的关键段落。传统做法是手…...

利用快马平台快速构建免费节点测试工具原型,十分钟完成开发

今天想和大家分享一个快速验证免费节点可用性的小工具开发过程。作为一个经常需要测试代理节点的开发者&#xff0c;手动一个个验证实在太费时间&#xff0c;于是我用InsCode(快马)平台快速搭建了一个原型工具&#xff0c;整个过程比想象中简单很多。 需求分析 免费节点测试工具…...

别再傻傻分不清了!用Simulink手把手带你搞懂导纳控制与阻抗控制的本质区别

导纳控制 vs 阻抗控制&#xff1a;从理论到Simulink实战的深度解析 在机器人控制领域&#xff0c;柔性交互是一个永恒的话题。想象一下&#xff0c;当机械臂需要完成精密装配任务时&#xff0c;既要有足够的刚性保证定位精度&#xff0c;又要在意外碰撞时表现出适当的柔顺性——…...

OpenClaw对比测试:Qwen3.5-9B与其他模型在自动化任务中的表现

OpenClaw对比测试&#xff1a;Qwen3.5-9B与其他模型在自动化任务中的表现 1. 测试背景与实验设计 最近在搭建个人自动化工作流时&#xff0c;我遇到了一个关键问题&#xff1a;OpenClaw框架下究竟该选择哪个大模型作为决策核心&#xff1f;为了找到答案&#xff0c;我花了三天…...

【实战解析】从期末试题到工程实践:摄影测量核心概念与计算全攻略

1. 从试卷到工地&#xff1a;摄影测量核心概念实战指南 第一次接触航测项目时&#xff0c;我盯着任务书上的"相机选型""航线规划"等要求完全懵了。这和期末考试那些名词解释、计算题有什么关系&#xff1f;直到在工地摔打半年后才明白&#xff0c;那些看似…...

开源项目主题系统的3大核心机制深度解析:从CSS变量到动态切换的完整实现方案

开源项目主题系统的3大核心机制深度解析&#xff1a;从CSS变量到动态切换的完整实现方案 【免费下载链接】vue-vben-admin vbenjs/vue-vben-admin: 是一个基于 Vue.js 和 Element UI 的后台管理系统&#xff0c;支持多种数据源和插件扩展。该项目提供了一个完整的后台管理系统&…...

新手必看!用PHPStudy一键搭建DVWA靶场(附常见错误解决)

零基础实战&#xff1a;用PHPStudy快速搭建DVWA漏洞靶场全指南 第一次接触网络安全实战时&#xff0c;很多人会被复杂的实验环境搭建劝退。作为过来人&#xff0c;我完全理解那种面对满屏报错信息的无力感。本文将手把手带你用PHPStudy这个神器&#xff0c;在Windows系统上快速…...

抖音高效采集与无水印提取工具使用指南

抖音高效采集与无水印提取工具使用指南 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 在数字内容创作与研究领域&#xff0c;高效的抖音资源管理已成为提升工作流的关键环节。本文将全面介绍一款功能强大的…...

后端架构师转型AI智能体架构师:3个月实战路径,收藏这份落地指南

如果你本身就是后端/全栈/架构师出身&#xff0c;这意味着你已经有了一套非常扎实的“确定性系统”的构建能力——分布式、高并发、数据库事务、系统稳定性&#xff0c;这些都是你的底牌。 而AI智能体恰恰是“不确定性系统”&#xff08;大模型&#xff09;与“确定性系统”&am…...

工单系统已经上线,但 IT 管理并没有真正变好

在很多企业中&#xff0c;引入 IT 工单系统往往被视为 IT 管理升级的重要一步。 有了统一入口、有了记录机制、有了流程流转&#xff0c;看起来一切都开始变得规范起来。但实际运行一段时间后&#xff0c;不少团队会发现&#xff1a; 工单确实在增加&#xff0c;流程也在走&…...