力扣 1049. 最后一块石头的重量 II
题目来源:https://leetcode.cn/problems/last-stone-weight-ii/description/

C++题解(思路来源代码随想录):本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。
动规五步曲:
- 确定dp数组以及下标的含义。dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
- 确定递推公式。01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
- dp数组如何初始化。既然 dp[j]中的j表示容量,那么最大容量(重量)就是所有石头的重量和。而我们要求的target其实只是最大重量的一半。
- 确定遍历顺序。如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
- 举例推导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
题目来源:https://leetcode.cn/problems/last-stone-weight-ii/description/ C题解(思路来源代码随想录):本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。 …...
【广州华锐视点】葡萄种植VR虚拟仿真实训平台
随着虚拟现实(VR)技术的不断发展,越来越多的教育领域开始尝试将VR技术应用于教学中。在葡萄栽培这一专业领域,我们开发了一款创新的VR实训课件,旨在为学生提供沉浸式的互动学习体验。本篇文案将为您介绍葡萄种植VR虚拟仿真实训平台所提供的互…...
PBR材质理解整理
PBR Material 草履虫都能看懂的PBR讲解(迫真) 先前看了很多遍类似的了,结合《Unity Shader 入门精要》中的内容整理了下便于以后理解,以后有补充再添加。 光与材质相交会发生散射和吸收,散射改变光的方向,…...
从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(Advanced Package Tool&…...
【雕爷学编程】Arduino动手做(182)---DRV8833双路电机驱动模块2
37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的&am…...
一个完整的http请求响应过程
一、 HTTP请求和响应步骤 以上完整表示了HTTP请求和响应的7个步骤,下面从TCP/IP协议模型的角度来理解HTTP请求和响应如何传递的。 二、TCP/IP协议 TCP/IP协议模型(Transmission Control Protocol/Internet Protocol),包含了一系…...
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种方法)、校验经纬度是否在圆/多边形区域内的算法推荐
目录 前言 一、根据坐标经纬度计算两点距离(5种方法) 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音视频开发中,网上知识点过于零碎,自学起来难度非常大,不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》。本文是Android音视频任务列表的其中一个, 对应的要学习的内容是:如何使…...
全面升级:华为鸿蒙HarmonyOS4正式发布,玩趣个性化,小艺AI升级
8月4日新闻,今天下午,华为正式发布了最新版本的鸿蒙操作系统——HarmonyOS 4! 在华为发布会上,鸿蒙HarmonyOS迎来了一系列令人激动的功能升级。其中包括个性化空间、多种生产力工具以及增强的手机AI助手"小艺"。这次更…...
【python】使用Selenium和Chrome WebDriver来获取 【腾讯云 Cloud Studio 实战训练营】中的文章信息
文章目录 前言导入依赖库设置ChromeDriver的路径创建Chrome WebDriver对象打开网页找到结果元素创建一个空列表用于存储数据遍历结果元素并提取数据提取标题、作者、发布时间等信息判断是否为目标文章提取目标文章的描述、阅读数量、点赞数量、评论数量等信息将提取的数据存储为…...
使用Feign 的远程调用,把mysql数据导入es
要把数据库数据导入到elasticsearch中,包括下面几步: 1)将商品微服务中的分页查询商品接口定义为一个FeignClient,放到feign-api模块中 2)搜索服务编写一个测试业务,实现下面功能: 调用item-ser…...
Java课题笔记~ MyBatis接口开发(代理开发)
使用XML文件进行开发,在调用SqlSession进行操作时,需要指定MyBatis映射文件中的方法,这种调用方式过于烦琐。为解决此问题,MyBatis提供了接口开发的方式。 接口开发的目的: 解决原生方式中的硬编码 简化后期执行SQL …...
从数学到深度学习的学习资料及教程合集
诸神缄默不语-个人CSDN博文目录 目前仅收集免费内容,最多需要买本纸质书。 付费的如果有免费版本我也会收录。 链接如失效请联系我。 这个笔记主要是为我自己准备的,算是一个可公开的to do list(其实做不完的我也知道)ÿ…...
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?1.3 系统的合法 shell 与 /etc/shells 功能1.4 Bash shell 的功能1.5 查询指令是否为 Bash shell 的内建命令: type1.6 指令的下达与快速编辑按…...
AWS Amplify 部署node版本18报错修复
Amplify env:Amazon Linux:2 Build Error : Specified Node 18 but GLIBC_2.27 or GLIBC_2.28 not found on build 一、原因 报错原因是因为默认情况下,AWS Amplify 使用 Amazon Linux:2 作为其构建镜像,并自带 GLIBC 2.26。不过,…...
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…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
