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

力扣 1049. 最后一块石头的重量 II

题目来源:https://leetcode.cn/problems/last-stone-weight-ii/description/

 

 C++题解(思路来源代码随想录):本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了

动规五步曲:

  1. 确定dp数组以及下标的含义。dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
  2. 确定递推公式。01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);  本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
  3. dp数组如何初始化。既然 dp[j]中的j表示容量,那么最大容量(重量)就是所有石头的重量和。而我们要求的target其实只是最大重量的一半。
  4. 确定遍历顺序。如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
  5. 举例推导dp数组
// 自己的版本
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int len = stones.size();if(len == 1) return stones[0];int sum = 0;for(int i = 0; i < len; i++){sum += stones[i];}int maxheavy = 0;if(sum%2 == 1) maxheavy = (sum-1)/2;else maxheavy = sum/2;vector<int> dp(maxheavy+1, 0);for(int j = 0; j < len; j++) {for(int k = maxheavy; k >= stones[j]; k--) {dp[k] = max(dp[k], dp[k - stones[j]] + stones[j]);}}int res = (sum - dp[maxheavy]) - dp[maxheavy];return res;}
};
// 代码随想录版本
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};

相关文章:

力扣 1049. 最后一块石头的重量 II

题目来源&#xff1a;https://leetcode.cn/problems/last-stone-weight-ii/description/ C题解&#xff08;思路来源代码随想录&#xff09;&#xff1a;本题其实就是尽量让石头分成重量相同的两堆&#xff0c;相撞之后剩下的石头最小&#xff0c;这样就化解成01背包问题了。 …...

【广州华锐视点】葡萄种植VR虚拟仿真实训平台

随着虚拟现实(VR)技术的不断发展&#xff0c;越来越多的教育领域开始尝试将VR技术应用于教学中。在葡萄栽培这一专业领域&#xff0c;我们开发了一款创新的VR实训课件&#xff0c;旨在为学生提供沉浸式的互动学习体验。本篇文案将为您介绍葡萄种植VR虚拟仿真实训平台所提供的互…...

PBR材质理解整理

PBR Material 草履虫都能看懂的PBR讲解&#xff08;迫真&#xff09; 先前看了很多遍类似的了&#xff0c;结合《Unity Shader 入门精要》中的内容整理了下便于以后理解&#xff0c;以后有补充再添加。 光与材质相交会发生散射和吸收&#xff0c;散射改变光的方向&#xff0c…...

从c++的角度来看ffmpeg 的架构

------------------------------------------------------------------------- author: hjjdebug date: 2023年 08月 01日 星期二 11:26:40 CST descriptor: 从c的角度来看ffmpeg 的架构 ------------------------------------------------------------------------…...

Ubuntu安装JDK与IntelliJ IDEA

目录 前言 Ubuntu 安装 JDK 1、更新软件包列表 2、安装OpenJDK 3、验证安装 Ubuntu安装IntelliJ IDEA 1、下载 IntelliJ IDEA 2、解压缩 IntelliJ IDEA 安装包 3、移动 IntelliJ IDEA 到安装目录 4、启动 IntelliJ IDEA 前言 APT&#xff08;Advanced Package Tool&…...

【雕爷学编程】Arduino动手做(182)---DRV8833双路电机驱动模块2

37款传感器与执行器的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&am…...

一个完整的http请求响应过程

一、 HTTP请求和响应步骤 以上完整表示了HTTP请求和响应的7个步骤&#xff0c;下面从TCP/IP协议模型的角度来理解HTTP请求和响应如何传递的。 二、TCP/IP协议 TCP/IP协议模型&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;&#xff0c;包含了一系…...

Unity通过代码切换材质

效果展示 代码 using System.Collections; using System.Collections.Generic; using UnityEngine;public class MaterialSwitcher : MonoBehaviour {public Material newMaterial; // 新材质private Material oldMaterial; // 旧材质private Renderer renderer; // 渲染器组件…...

Java根据坐标经纬度计算两点距离(5种方法)、校验经纬度是否在圆/多边形区域内的算法推荐

目录 前言 一、根据坐标经纬度计算两点距离&#xff08;5种方法&#xff09; 1.方法一 2.方法二 3.方法三 4.方法四 5.方法五 5.1 POM引入第三方依赖 5.2 代码 6.测试结果对比 二、校验经纬度是否在制定区域内 1.判断一个坐标是否在圆形区域内 2.判断一个坐标是否…...

PIC单片机如何设计延时

PIC单片机如何设计延时 PIC单片机的延时基本有两种,一种是自己设计的delay()函数,另一种就是利用其自带的Time定时器。当然一般Time定时器的精度要高于自己设计delay()函数,Time定时器是单片机内部的硬件寄存器模块,而delay()函数是利用自加自减来实现延时,代码进行顺序执…...

FFmpeg常见命令行(二):FFmpeg转封装

前言 在Android音视频开发中&#xff0c;网上知识点过于零碎&#xff0c;自学起来难度非常大&#xff0c;不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》。本文是Android音视频任务列表的其中一个&#xff0c; 对应的要学习的内容是&#xff1a;如何使…...

全面升级:华为鸿蒙HarmonyOS4正式发布,玩趣个性化,小艺AI升级

8月4日新闻&#xff0c;今天下午&#xff0c;华为正式发布了最新版本的鸿蒙操作系统——HarmonyOS 4&#xff01; 在华为发布会上&#xff0c;鸿蒙HarmonyOS迎来了一系列令人激动的功能升级。其中包括个性化空间、多种生产力工具以及增强的手机AI助手"小艺"。这次更…...

【python】使用Selenium和Chrome WebDriver来获取 【腾讯云 Cloud Studio 实战训练营】中的文章信息

文章目录 前言导入依赖库设置ChromeDriver的路径创建Chrome WebDriver对象打开网页找到结果元素创建一个空列表用于存储数据遍历结果元素并提取数据提取标题、作者、发布时间等信息判断是否为目标文章提取目标文章的描述、阅读数量、点赞数量、评论数量等信息将提取的数据存储为…...

使用Feign 的远程调用,把mysql数据导入es

要把数据库数据导入到elasticsearch中&#xff0c;包括下面几步&#xff1a; 1&#xff09;将商品微服务中的分页查询商品接口定义为一个FeignClient&#xff0c;放到feign-api模块中 2&#xff09;搜索服务编写一个测试业务&#xff0c;实现下面功能&#xff1a; 调用item-ser…...

Java课题笔记~ MyBatis接口开发(代理开发)

使用XML文件进行开发&#xff0c;在调用SqlSession进行操作时&#xff0c;需要指定MyBatis映射文件中的方法&#xff0c;这种调用方式过于烦琐。为解决此问题&#xff0c;MyBatis提供了接口开发的方式。 接口开发的目的&#xff1a; 解决原生方式中的硬编码 简化后期执行SQL …...

从数学到深度学习的学习资料及教程合集

诸神缄默不语-个人CSDN博文目录 目前仅收集免费内容&#xff0c;最多需要买本纸质书。 付费的如果有免费版本我也会收录。 链接如失效请联系我。 这个笔记主要是为我自己准备的&#xff0c;算是一个可公开的to do list&#xff08;其实做不完的我也知道&#xff09;&#xff…...

nn.CrossEntropyLoss()报错

RuntimeError: “nll_loss_forward_reduce_cuda_kernel_2d_index” not implemented for ‘Float’ Traceback (most recent call last): File "<string>", line 1, in <module> File "/home/zz/anaconda3/envs/torch1.11/lib/python3.7/site-pack…...

【BASH】回顾与知识点梳理(一)

【BASH】回顾与知识点梳理 一 前言一. 认识与学习 BASH1.1 硬件、核心与 Shell1.2 为何要学文字接口的 shell&#xff1f;1.3 系统的合法 shell 与 /etc/shells 功能1.4 Bash shell 的功能1.5 查询指令是否为 Bash shell 的内建命令&#xff1a; type1.6 指令的下达与快速编辑按…...

AWS Amplify 部署node版本18报错修复

Amplify env&#xff1a;Amazon Linux:2 Build Error : Specified Node 18 but GLIBC_2.27 or GLIBC_2.28 not found on build 一、原因 报错原因是因为默认情况下&#xff0c;AWS Amplify 使用 Amazon Linux:2 作为其构建镜像&#xff0c;并自带 GLIBC 2.26。不过&#xff0c;…...

K8S添加yum源并安装kubectl/kubeadm/kubelet组件

1.安装kubectl/kubeadm/kubelet ##添加yum 源 cat > /etc/yum.repos.d/kubernetes.repo << EOF [kubernetes] nameKubernetes baseurlhttps://mirrors.aliyun.com/kubernetes/yum/repos/kubernetes-el7-x86_64 enabled1 gpgcheck0 repo_gpgcheck0 gpgkeyhttps://mirr…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...