【动态规划】【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 解法 ---------------🎈🎈题目链接🎈🎈------------------- 解法 😒: 我的代码实现> 动规五部曲 ✒️确定dp数组以及下标的含义 dp[j]表示容量为…...

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

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

继承【C/C++复习版】
目录 一、什么是继承?怎么定义继承? 二、继承关系和访问限定符? 三、基类和派生类对象可以赋值转换吗? 四、什么是隐藏?隐藏vs重载? 五、派生类的默认成员函数? 1)派生类构造函…...

题目 2694: 蓝桥杯2022年第十三届决赛真题-最大数字【暴力解法】
最大数字 原题链接 🥰提交结果 思路 对于每一位,我我们都要尽力到达 9 所以我们去遍历每一位, 如果是 9 直接跳过这一位 如果可以上调到 9 我们将这一位上调到 9 ,并且在a 中减去对应的次数 同样的,如果可以下调到 9,我…...

【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 实现,可以适用微信小程序、其他各种小程序以及 APP、Web等多个平台 具体实现步骤如下: 下载开发者工具 HbuilderX进入 【Dcloud 插…...

基于SSM+Jsp+Mysql的农产品供销服务系统
开发语言:Java框架:ssm技术:JSPJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包…...

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

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

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

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

[ 云计算 | AWS 实践 ] Java 应用中使用 Amazon S3 进行存储桶和对象操作完全指南
本文收录于【#云计算入门与实践 - AWS】专栏中,收录 AWS 入门与实践相关博文。 本文同步于个人公众号:【云计算洞察】 更多关于云计算技术内容敬请关注:CSDN【#云计算入门与实践 - AWS】专栏。 本系列已更新博文: [ 云计算 | …...

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

WPS二次开发系列:Gradle版本、AGP插件与Java版本的对应关系
背景 最近有体验SDK的同学反馈接入SDK出现报错,最终定位到原因为接入的宿主app项目的gradle版本过低导致,SDK兼容支持了android11的特性,需要对应的gradle插件为支持android11的版本。 现象 解决方案 将gradle版本升级至支持android11的插件版…...

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

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

【攻防世界】mfw(.git文件泄露)
首先进入题目环境,检查页面、页面源代码、以及URL: 发现页面无异常。 使用 dirsearch 扫描网站,检查是否存在可访问的文件或者文件泄露: 发现 可访问界面/templates/ 以及 .git文件泄露,故使用 GItHack 来查看泄露的 …...

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

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

ThinkPHP审计(1) 不安全的SQL注入PHP反序列化链子phar利用简单的CMS审计实例
ThinkPHP代码审计(1) 不安全的SQL注入&PHP反序列化链子phar利用&简单的CMS审计实例 文章目录 ThinkPHP代码审计(1) 不安全的SQL注入&PHP反序列化链子phar利用&简单的CMS审计实例一.Thinkphp5不安全的SQL写法二.Thinkphp3 SQL注入三.Thinkphp链5.1.x结合phar实现…...

Centos中一些有趣的命令
目录 1.sl 小火车 2. cowsay 会说话的牛 3.toilet/figlet 图形化输出 4.aafire 小火焰 5.linux_logo 显示系统logo 1.sl 小火车 yum install sl 2. cowsay 会说话的牛 yum install cowsay 3.toilet/figlet 图形化输出 yum install toilet yum install figlet 4.aafire 小火…...

elementUI2
ElementUI 图片引用查询表单表格展示新增修改详情图表 图片引用 <img :src"logo" width"100%" height"100%"/>import logoImg from /assets/logo/home.pngdata() {return {logo: logoImg,}}查询表单 <el-form :model"queryParams…...

Python 爬虫基础——http请求和http响应
写本篇文章,我认为是能把自己所理解的内容分享出来,说不定就有和我一样有这样思维的共同者,希望本篇文章能帮助大家!✨✨ 文章目录 一、 🌈python介绍和分析二、 🌈http请求三、 🌈http响应四、…...

【Hadoop】Hive导入导出数据指南
穿新衣吧 剪新发型呀 轻松一下Windows98 打扮漂亮 18岁是天堂 我们的生活甜得像糖 穿新衣吧 剪新发型呀 轻松一下Windows98 以后的路不再会有痛苦 我们的未来该有多酷 🎵 房东的猫《new boy》 Apache Hive 是一个基于Hadoop的数据仓库工具&…...

Mybatis 执行批量插入
首先,创建一个简单的 insert 语句: <insert id”insertname”>insert into names (name) values (#{value}) </insert>然后在 java 代码中像下面这样执行批处理插入: list < string > names new arraylist(); names.add(“fred”); names.add(“barney”)…...

vivado 使用基本触发器模式
使用基本触发器模式 基本触发器模式用于描述触发条件 , 即由参与其中的调试探针比较器组成的全局布尔公式。当“触发器模式 (Trigger Mode) ”设置为 BASIC_ONLY 或 BASIC_OR_TRIG_IN 时 , 即启用基本触发器模式。使用“基本触发器设置 (Basic Trig…...

Chrome 浏览器无法保存或自动填充密码
Chrome 浏览器无法保存或自动填充密码 分类 平时使用 Chrome 浏览器都会对网站的用户名密码自动填充,今天发现突然不行了,找到一个解决办法: 1、退出 Chrome 浏览器。2、打开 Chrome 安装目录下的的 Profile 目录,删除 Login Da…...

C语言面试指针辨析
1. const int *p int const *p p可以改变,*p不可以改变 p可以指向任意空间,但无法利用p修改指针空间的值 2. int *const p p不能改变,*p可以改变 3. const int *const p int const *const p p和*p都不能改变 4. 面试问题 将内存地址为0x2…...

YOLOV5 分类:利用yolov5进行图像分类
1、前言 之前介绍了yolov5的目标检测示例,这次将介绍yolov5的分类展示 目标检测:YOLOv5 项目:训练代码和参数详细介绍(train)_yolov5训练代码的详解-CSDN博客 yolov5和其他网络的性能对比 yolov5分类的代码部分在这 2、数据集准备 yolov5分类的数据集就是常规的摆放方式…...