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

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...