当前位置: 首页 > 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…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

el-amap-bezier-curve运用及线弧度设置

文章目录 简介示例线弧度属性主要弧度相关属性其他相关样式属性完整示例链接简介 ‌el-amap-bezier-curve 是 Vue-Amap 组件库中的一个组件,用于在 高德地图 上绘制贝塞尔曲线。‌ 基本用法属性path定义曲线的路径,可以是多个弧线段的组合。stroke-weight线条的宽度。stroke…...