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

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II

    • 解法

---------------🎈🎈题目链接🎈🎈-------------------
在这里插入图片描述

解法

😒: 我的代码实现============>

动规五部曲

✒️确定dp数组以及下标的含义

dp[j]表示容量为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数组初始化

初始为0即可

✒️确定遍历顺序

正序遍历物品,倒序遍历背包

最后dp[target]里是容量为target的背包所能背的最大重量。
⭐️那么求dp[sum/2] ,即dp[target]即可!
那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。

时间复杂度O(N)
空间复杂度O(N)

📘代码

class Solution {public int lastStoneWeightII(int[] stones) {// 得到总的重量int sum = 0;for(int stone:stones){sum += stone;}// 希望尽可能凑出离total/2近的两组石头  =》 一组离total/2近, 那另一组也一定离total/2近// dp[j] : 装满容量为j的背包 能装下的最大重量为dp[j] int total = sum/2;int[] dp = new int[total+1];for(int i = 0 ; i < stones.length; i++){ // 正序遍历物品for(int j = total; j>=stones[i]; j--){ // 倒序遍历背包dp[j] = Math.max(dp[j] , dp[j-stones[i]]+stones[i]);}}for(int j = 0; j <= total; j++){ // 倒叙遍历背包System.out.println(dp[j]);}return Math.abs(dp[total] - (sum-dp[total]));}
}   

相关文章:

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II

【动态规划】【01背包】Leetcode 1049. 最后一块石头的重量 II 解法 ---------------&#x1f388;&#x1f388;题目链接&#x1f388;&#x1f388;------------------- 解法 &#x1f612;: 我的代码实现> 动规五部曲 ✒️确定dp数组以及下标的含义 dp[j]表示容量为…...

2023 年上海市大学生程序设计竞赛 - 四月赛

A. 宝石划分 A. 宝石划分 - 2023 年上海市大学生程序设计竞赛 - 四月赛 - ECNU Online Judge 找距离N最近的M的因数q&#xff0c;输出M/q 如果是暴力所的话&#xff0c;会超时 #include <bits/stdc.h> using namespace std; int main(){ios::sync_with_stdio(false)…...

别让这6个UI设计雷区毁了你的APP!

一款成功的APP不仅仅取决于其功能性&#xff0c;更取决于用户体验&#xff0c;这其中&#xff0c;UI设计又至关重要。优秀的UI设计能够为用户带来直观、愉悦的交互体验&#xff0c;甚至让用户“一见钟情”&#xff0c;从而大大提高产品吸引力。 然而&#xff0c;有很多设计师在…...

继承【C/C++复习版】

目录 一、什么是继承&#xff1f;怎么定义继承&#xff1f; 二、继承关系和访问限定符&#xff1f; 三、基类和派生类对象可以赋值转换吗&#xff1f; 四、什么是隐藏&#xff1f;隐藏vs重载&#xff1f; 五、派生类的默认成员函数&#xff1f; 1&#xff09;派生类构造函…...

题目 2694: 蓝桥杯2022年第十三届决赛真题-最大数字【暴力解法】

最大数字 原题链接 &#x1f970;提交结果 思路 对于每一位&#xff0c;我我们都要尽力到达 9 所以我们去遍历每一位, 如果是 9 直接跳过这一位 如果可以上调到 9 我们将这一位上调到 9 &#xff0c;并且在a 中减去对应的次数 同样的&#xff0c;如果可以下调到 9&#xff0c;我…...

【C语言】- C语言字符串函数详解

C语言字符串函数详解 1、void *memset(void *dest, int c, size_t count); 将dest前面count个字符置为字符c. 返回dest的值. 2、void *memmove(void *dest, const void *src, size_t count); 从src复制count字节的字符到dest. 如果src和dest出现重叠, 函数会自动处理. 返回…...

如何实现小程序滑动删除组件+全选批量删除组件

如何实现小程序滑动删除组件全选批量删除组件 一、简介 如何实现小程序滑动删除组件全选批量删除组件 采用 uni-app 实现&#xff0c;可以适用微信小程序、其他各种小程序以及 APP、Web等多个平台 具体实现步骤如下&#xff1a; 下载开发者工具 HbuilderX进入 【Dcloud 插…...

基于SSM+Jsp+Mysql的农产品供销服务系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…...

​​​​网络编程学习探索系列之——广播原理剖析

hello &#xff01;大家好呀&#xff01; 欢迎大家来到我的网络编程系列之广播原理剖析&#xff0c;在这篇文章中&#xff0c; 你将会学习到如何在网络编程中利用广播来与局域网内加入某个特定广播组的主机&#xff01; 希望这篇文章能对你有所帮助&#xff0c;大家要是觉得我写…...

小程序开发SSL证书下载和安装

在开发小程序时&#xff0c;确保数据的安全传输至关重要&#xff0c;而实现这一目标的关键在于正确获取与安装SSL证书。以下详细介绍了从获取到安装SSL证书的完整流程&#xff0c;以助您为小程序构建可靠的加密通信环境。 一、小程序SSL证书类型选择&#xff1a; 域名验证型D…...

医疗图像分割 | 基于Pyramid-Vision-Transformer算法实现医疗息肉分割

项目应用场景 面向医疗图像息肉分割场景&#xff0c;项目采用 Pytorch Pyramid-Vision-Transformer 深度学习算法来实现。 项目效果 项目细节 > 具体参见项目 README.md (1) 模型架构 (2) 项目依赖&#xff0c;包括 python 3.8、pytorch 1.7.1、torchvision 0.8.2(3) 下载…...

蓝桥杯 每日2题 day5

碎碎念&#xff1a;哦哈呦&#xff0c;到第二天也是哦哈哟&#xff0c;&#xff0c;学前缀和差分学了半天&#xff01;day6堂堂连载&#xff01; 0.单词分析 14.单词分析 - 蓝桥云课 (lanqiao.cn) 关于这题就差在input前加一个sorted&#xff0c;记录一下下。接下来就是用字…...

[ 云计算 | AWS 实践 ] Java 应用中使用 Amazon S3 进行存储桶和对象操作完全指南

本文收录于【#云计算入门与实践 - AWS】专栏中&#xff0c;收录 AWS 入门与实践相关博文。 本文同步于个人公众号&#xff1a;【云计算洞察】 更多关于云计算技术内容敬请关注&#xff1a;CSDN【#云计算入门与实践 - AWS】专栏。 本系列已更新博文&#xff1a; [ 云计算 | …...

循环单链表算法库

学习贺老师数据结构 数据结构之自建算法库——循环单链表_循环单链表 csdn-CSDN博客​​​​​​ 整理总结出的循环单链表算法库 v1.0 : 基本实现功能 v2.0(2024.4.6): 修复Delete_SpecificLocate_CyclicList()删除节点函数bug,添加验证删除节点是否超范围判断 目录 1.主要功能…...

WPS二次开发系列:Gradle版本、AGP插件与Java版本的对应关系

背景 最近有体验SDK的同学反馈接入SDK出现报错&#xff0c;最终定位到原因为接入的宿主app项目的gradle版本过低导致&#xff0c;SDK兼容支持了android11的特性&#xff0c;需要对应的gradle插件为支持android11的版本。 现象 解决方案 将gradle版本升级至支持android11的插件版…...

绿联 安装MariaDB数据库用于Seatable服务

绿联 安装MariaDB数据库用于Seatable服务 MariaDB MariaDB 是一个流行的开源关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它是MySQL的一个分支&#xff0c;提供了丰富的功能和性能&#xff0c;适用于各种应用场景。 核心功能 SQL支持: MariaDB完全支持SQL&a…...

Spark, Storm, Flink简介

目录 1.Spark VS Storm2.Storm VS Flink 本文主要介绍Spark, Storm, Flink的区别。 1.Spark VS Storm Spark和Storm都是大数据处理框架&#xff0c;但它们在设计理念和使用场景上有一些区别&#xff1a; 实时性&#xff1a;Storm是一个实时计算框架&#xff0c;适合需要实时…...

【攻防世界】mfw(.git文件泄露)

首先进入题目环境&#xff0c;检查页面、页面源代码、以及URL&#xff1a; 发现页面无异常。 使用 dirsearch 扫描网站&#xff0c;检查是否存在可访问的文件或者文件泄露&#xff1a; 发现 可访问界面/templates/ 以及 .git文件泄露&#xff0c;故使用 GItHack 来查看泄露的 …...

递归神经网络(Recursive Neural Networks)

递归神经网络&#xff08;Recursive Neural Networks&#xff09;是一种特殊的神经网络&#xff0c;它们通过处理具有树形结构的数据来捕获数据的深层次关系&#xff0c;尤其是在自然语言处理和计算机视觉中的一些应用&#xff0c;如语法分析和场景理解。 1. 理解基本概念和背…...

【leetcode面试经典150题】29.三数之和(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…...

Umi-OCR插件技术方案:5款引擎深度对比与实战配置指南

Umi-OCR插件技术方案&#xff1a;5款引擎深度对比与实战配置指南 【免费下载链接】Umi-OCR_plugins Umi-OCR 插件库 项目地址: https://gitcode.com/gh_mirrors/um/Umi-OCR_plugins Umi-OCR插件库为开源OCR工具提供了丰富的引擎选择&#xff0c;从本地CPU加速到云端AI识…...

TinyMCE 5插件开发实战:手把手教你定制首行缩进功能(Vue版)

TinyMCE 5插件开发实战&#xff1a;手把手教你定制首行缩进功能&#xff08;Vue版&#xff09; 在内容创作领域&#xff0c;富文本编辑器的灵活性和扩展性往往决定了最终的用户体验。TinyMCE作为一款广受欢迎的富文本编辑器&#xff0c;其插件系统为开发者提供了无限可能。本文…...

Cartographer实战:如何用Velodyne 32E激光雷达跑通GraphSLAM(附避坑指南)

Cartographer实战&#xff1a;Velodyne 32E激光雷达的GraphSLAM全流程解析与性能调优 当Velodyne 32E激光雷达遇上Cartographer的GraphSLAM算法&#xff0c;如何在复杂环境中实现厘米级建图精度&#xff1f;本文将拆解从硬件配置到算法调优的完整落地流程&#xff0c;分享我在大…...

【操作系统】第三章 内存管理(一)

第三章 内存管理 3.1 内存管理概念 3.1.1 内存管理的基本原理和要求 内存管理的主要功能&#xff1a; 内存空间的分配与回收。[连续分配管理方式](#3.1.2 连续分配管理方式)和非连续分配管理方式&#xff08;分页、分段&#xff09;地址转换&#xff1a;实现逻辑地址到物理…...

二分查找/二分答案

0.前言二分算法&#xff08;Binary Search&#xff09;&#xff0c;也叫折半查找&#xff0c;是一种在有序数据集合中高效查找目标值的算法。它通过不断将查找范围缩小一半&#xff0c;快速定位目标&#xff0c;时间复杂度为 O(logn)&#xff0c;远优于线性查找的 O(n)。1.原理…...

RSA宣布与Microsoft扩大合作,进一步巩固公司在无密码身份安全领域的领导地位

创新合作开启安全、基于人工智能的员工身份验证新时代 RSA今日在RSAC 2026大会上宣布&#xff0c;将扩大对全新Microsoft 365 E7&#xff1a;The Frontier Suite解决方案的支持。这一新增支持结合了额外的无密码功能&#xff0c;在企业拥抱人工智能驱动的生产力未来之际&#…...

SAP FICO财务账期管理实战:关键配置与月结操作指南

1. SAP FICO财务账期管理基础概念 财务账期管理是SAP FICO模块中最基础也最重要的功能之一。简单来说&#xff0c;它就像财务部门的"门禁系统"&#xff0c;控制着哪些会计凭证能在特定时间段被录入系统。想象一下&#xff0c;如果超市收银台没有营业时间限制&#xf…...

密码安全必修课:为什么BCrypt比MD5更适合存储用户密码?

密码安全必修课&#xff1a;为什么BCrypt比MD5更适合存储用户密码&#xff1f; 在数字身份成为第二张身份证的时代&#xff0c;密码安全早已不是技术圈的内部话题。去年某社交平台600万用户数据泄露事件中&#xff0c;令人震惊的不是数据被盗本身&#xff0c;而是其中87%的密码…...

AI 开发实战:需求变更后,如何让 AI 自动补回归范围

AI 开发实战&#xff1a;需求变更后&#xff0c;如何让 AI 自动补回归范围 一、这个问题为什么值得专门拿出来做&#xff1f; 在 AI 工程落地里&#xff0c;真正拖慢团队的往往不是模型本身&#xff0c;而是流程和协作方式没有跟上。 围绕“需求变更后&#xff0c;如何让 AI 自…...

java毕业设计基于springboot+vue的电影院座位管理系统

前言 该系统旨在实现电影院座位的高效管理&#xff0c;包括座位预订、售票、座位状态实时监控等功能。通过该系统&#xff0c;电影院可以提高售票效率&#xff0c;优化座位使用率&#xff0c;同时为顾客提供便捷的购票体验。 一、项目介绍 开发语言&#xff1a;Java 框架&…...