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

【Java|golang】1105. 填充书架---动态规划

给定一个数组 books ,其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。

按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上(它们的厚度之和小于等于书架的宽度 shelfWidth ),然后再建一层书架。重复这个过程,直到把所有的书都放在书架上。

需要注意的是,在上述过程的每个步骤中,摆放书的顺序与你整理好的顺序相同。

例如,如果这里有 5 本书,那么可能的一种摆放情况是:第一和第二本书放在第一层书架上,第三本书放在第二层书架上,第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高,书架整体的高度为各层高之和。

以这种方式布置书架,返回书架整体可能的最小高度。

示例 1:

在这里插入图片描述

输入:books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出:6
解释:
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。
示例 2:

输入: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
输出: 4

提示:

1 <= books.length <= 1000
1 <= thicknessi <= shelfWidth <= 1000
1 <= heighti <= 1000

    public int minHeightShelves(int[][] books, int shelfWidth) {int length = books.length;int[] dp = new int[length + 1];for (int i = 1; i <= length; i++) {int width=0;int height=0;dp[i]=Integer.MAX_VALUE;for (int j = i-1; j >=0; j--) {if (shelfWidth<(width+=books[j][0])){break;}height=Math.max(height,books[j][1]);dp[i]=Math.min(dp[i],dp[j]+height);}}return dp[length];}

在这里插入图片描述

func minHeightShelves(books [][]int, shelfWidth int) int {length := len(books)dp := make([]int,length + 1)for i := 1; i <= length; i++ {width,height:=0,0dp[i]=math.MaxInt32for j := i-1; j >=0; j-- {if width+=books[j][0];shelfWidth<width{break}if height<books[j][1] {height=books[j][1]}if dp[j]+height<dp[i] {dp[i]=dp[j]+height}}}return dp[length]
}

在这里插入图片描述

相关文章:

【Java|golang】1105. 填充书架---动态规划

给定一个数组 books &#xff0c;其中 books[i] [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。 按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。 先选几本书放在书架上&#xff08;它们的厚度之和小于等于书架的宽度 shelfWidt…...

linux基础命令

linux基础命令 一、linux命令 熟悉账务linux命令对运维的好处是巨大的&#xff0c;只有熟悉了命令咱们在运维的操作上才能如鱼得水。 系统信息 arch #显示机器的处理器架构(1) uname -m #显示机器的处理器架构(2) uname -r #显示正在使用的内核版本 dmidecode -q …...

【三十天精通Vue 3】 第十八天 Vue 3的国际化详解

✅创作者&#xff1a;陈书予 &#x1f389;个人主页&#xff1a;陈书予的个人主页 &#x1f341;陈书予的个人社区&#xff0c;欢迎你的加入: 陈书予的社区 &#x1f31f;专栏地址: 三十天精通 Vue 3 文章目录 引言一、Vue 3 国际化概述1.1 国际化的概念1.2 国际化的作用1.3 V…...

02 - 学会提问

学会提问 一、引言 1.1 GPT简介 GPT&#xff08;Generative Pre-trained Transformer&#xff09;是一种基于Transformer架构的大型预训练语言模型。 凭借其强大的文本生成、理解和处理能力&#xff0c;GPT已在诸如自然语言处理、机器翻译、文本摘要等多个领域取得了显著的…...

Java经典的Main方法面试题

mian方法是做什么用的&#xff1f; main方法是Java程序的入口方法&#xff0c;JVM在运行的时候会首先查找main方法不用main方法如何运行一个类&#xff1f; 不行&#xff0c;没有main方法我们不能运行Java类 在Java7之前&#xff0c;你可以通过使用静态初始化运行Java类。但是&…...

世界大学电子电气工程TOP10,国内大学哪家强?

EE究竟是什么专业 ? 在中国&#xff0c;工程系中跟电相关的专业&#xff0c;一般都切分得非常细。有电子工程、电气工程、通信工程、信息工程、自动化、测控仪器等。但在国外&#xff0c;一般把这些领域都归类到 Electrical Engineering 中&#xff0c;也就是我们常说的EE。 …...

5.3 牛顿-科茨公式

学习目标&#xff1a; 理解微积分基础知识&#xff0c;例如导数和微分的概念。学习牛顿-科茨公式的推导过程。这个公式实际上是使用泰勒公式对被积函数进行展开&#xff0c;并使用微积分的基本原理进行简化得到的。学习如何使用牛顿-科茨公式进行数值积分。这通常涉及到将被积…...

全注解下的SpringIoc 续2-bean的生命周期

spring中bean的生命周期 上一个小节梳理了一下Spring Boot的依赖注入的基本知识&#xff0c;今天来梳理一下spring中bean的生命周期。 下面&#xff0c;让我们一起看看bean在IOC容器中是怎么被创建和销毁的。 bean的生命周期大致分为四个部分&#xff1a; #mermaid-svg-GFXNEU…...

【VQ-VAE代码实战】Neural Discrete Representation Learning

【VQ-VAE代码实战】Neural Discrete Representation Learning 0、前言1、简介2、Basic IdeaLoss3、代码Load DataVector Quantizer LayerEncoder & Decoder ArchitectureTrainPlot LossView ReconstructionsView EmbeddingReference0、前言 论文地址:基于神经网络的,离散…...

gpt3.5和gpt4区别-gpt3.5和gpt4

gpt系列 GPT系列是OpenAI公司开发的一组基于人工智能深度学习技术的自然语言处理模型。GPT代表Generative Pre-trained Transformer&#xff0c;即预训练生成模型。目前&#xff0c;GPT模型已经推出了三代&#xff08;GPT-1&#xff0c;GPT-2&#xff0c;GPT-3&#xff09;&am…...

java获取当前系统时间

在Java中&#xff0c;可以使用以下几种方法获取当前系统时间&#xff1a; 方法1&#xff1a;使用java.util.Date类 java import java.util.Date; public class Main { public static void main(String[] args) { Date date new Date(); System.out.println("当前时间&…...

pbootcms自动配图出图插件

pbootcms文章无图自动出图配图插件的优点 1、提高文章的可读性和吸引力&#xff1a;插入图片可以丰富文章的内容和形式&#xff0c;增强读者的阅读体验和吸引力&#xff0c;提高文章的点击率和转化率。 2、节省时间和精力&#xff1a;手动添加图片需要花费大量时间和精力去寻找…...

手动测试台架搭建,让你的车载测试更轻松

目录&#xff1a;导读 引言 1、概述 2、主要内容 3、汽车测试台架分类 4、汽车测试台架分类 5、汽车测试台架分类台架测试输人台架硬件搭建CANoe台架搭建 6、台架测试输入&#xff1f; 7、需求规范是功能测试用例设计来源测试结果的判断﹔包括∶客户需求(功能规范)需求分…...

分组双轴图:揭示数据中的关联性和趋势变化

简介 分组双轴图是一种数据可视化图表&#xff0c;指有多个&#xff08;≥2&#xff09;Y轴的数据图表&#xff0c;多为分组柱状图折线图的结合&#xff0c;图表显示更为直观&#xff0c;可以很好地展示不同指标之间的关系&#xff0c;帮助用户更好地理解数据&#xff0c;做出…...

MATLAB函数封装1:生成QT可以调用的.dll动态链接库

在进行相关算法的开发和设计过程中&#xff0c;MATLAB具有特别的优势&#xff0c;尤其是对于矩阵运算的处理&#xff0c;具有很多现成的方法和函数可以进行调用&#xff0c;同时MATLAB支持把函数封装成不同的语言方便完成算法的集成。 这里记录利用MATLAB封装成C动态链接库&…...

【算法题】2400. 恰好移动 k 步到达某一位置的方法数目

题目&#xff1a; 给你两个 正 整数 startPos 和 endPos 。最初&#xff0c;你站在 无限 数轴上位置 startPos 处。在一步移动中&#xff0c;你可以向左或者向右移动一个位置。 给你一个正整数 k &#xff0c;返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法…...

探索【Stable-Diffusion WEBUI】的插件:骨骼姿态(OpenPose)

文章目录 &#xff08;零&#xff09;前言&#xff08;一&#xff09;骨骼姿态&#xff08;OpenPose&#xff09;系列插件&#xff08;二&#xff09;插件&#xff1a;PoseX&#xff08;三&#xff09;插件&#xff1a;Depth Lib&#xff08;四&#xff09;插件&#xff1a;3D …...

MySQL数据落盘原理(redo、undo、binlog、2PC、double write等。)

文章目录 前言一、架构图1、MySQL架构图2、InnoDB架构图 二、落盘分析1.第一阶段2.第二阶段3.第三阶段4.第四阶段5.第五阶段6.第六阶段 三、总结 前言 在上一章中我们聊到了事务有四大特性&#xff1a;原子性、一致性、隔离性、持久性。本篇文章就持久性重点聊一下&#xff0c…...

智加科技+舍弗勒,首发量产正向开发的智能重卡冗余转向

对于自动驾驶赛道来说&#xff0c;感知、规划和控制&#xff0c;除了计算平台、算法等核心上层软硬件支持&#xff0c;底盘控制系统同样是关键一环。事实上&#xff0c;从Demo到规模化量产&#xff0c;更好的车身控制能力以及冗余备份&#xff0c;也是自动驾驶公司迈入2.0阶段的…...

C++类的模拟实现

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;C &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容讲解了简单模拟实现string类 C类的模拟实现 文章目录 C类的…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...