【动态规划】【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]));}
}   

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/306485.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Maven的scope详解

依赖范围介绍 maven 项目不同的阶段引入到classpath中的依赖是不同的&#xff0c;例如&#xff0c;编译时&#xff0c;maven 会将与编译相关的依赖引入classpath中&#xff0c;测试时&#xff0c;maven会将测试相关的的依赖引入到classpath中&#xff0c;运行时&#xff0c;mav…

路由器端口映射是什么意思?

路由器端口映射是一种网络配置技术&#xff0c;在私有网络中允许外部网络访问特定的服务或应用程序。通过将路由器的端口映射到内部客户端设备&#xff0c;可以实现从公共网络访问内部网络资源的目的。 天联组网介绍 天联是一款异地组网内网穿透产品&#xff0c;由北京金万维科…

数据治理项目——深铁集团数据治理规划

目录 一、前言 二、数据治理内容与主要措施 2.1 实施背景 2.2 主要举措 2.2.1 制定数据战略目标 2.2.2 绘制数据治理蓝图 2.2.3 绘制数据治理制度 2.2.4 梳理数据资产目录 三、 应用效果 3.1 数据资产可视化管理 3.2 数据标准治理 3.3 集团大数据平台优化建设 一、…

若依vue中关于字典的使用

文章目录 字典管理页面列表点击某个字典类型展示具体字典数据修改某一条字典数据 字典的应用一般用于select多选框中代码实现根据字典Dict的value获取Label&#xff0c;类似于通过key获得value 源码解析 字典管理页面 列表 点击某个字典类型展示具体字典数据 修改某一条字典数…

力扣HOT100 - 189. 轮转数组

解题思路&#xff1a; 三次反转。 先反转一次&#xff0c;再根据 k 拆分成两部分各反转一次。 class Solution {public void rotate(int[] nums, int k) {k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}pu…

关于DNS解析那些事儿,了解DNS解析的基础知识

DNS&#xff0c;全称Domain Name System域名系统&#xff0c;是一个将域名和IP地址相互映射的一个分布于世界各地的分布式数据库&#xff0c;而DNS解析就是将域名转换为IP地址的过程&#xff0c;使人们可以轻松实现通过域名访问网站。DNS解析是网站建设非常关键的一步&#xff…

防火墙搭建内网 安装路由器

经典网络情况 也就是网吧 先配置网段 科普&#xff1a;子网掩码代表IP前面几位不能动 安装防火墙虚拟机 配置两个网卡 第一个 第二个桥接 设置子网掩码 虚拟机有DHCP 可以不用防火墙的DHCP 配置有网站的ip地址和网关 利用防火墙映射出去外网 然后看防火墙外网ip 然后…

[lesson20]初始化列表的使用

初始化列表的使用 类成员的初始化 C中提供了初始化列表对成员变量进行初始化 语法规则 注意事项 成员的初始化顺序与成员的声明顺序相同成员的初始化顺序与初始化列表中的位置无关初始化列表先于构造函数的函数体执行 类中的const成员 类中的const成员会被分配空间的类中…

C++ primer 第十八章

C语言的三大特性&#xff1a;异常处理、命名空间、多重继承。 1.异常处理 异常处理机制允许我们能够将问题的检测与解决过程分离开来。 1.1、抛出异常 在C语言中&#xff0c;我们通过抛出一条表达式来引发一个异常。 当执行一个throw时&#xff0c;程序的控制权从throw转移…

(学习日记)2024.04.12:UCOSIII第四十节:软件定时器函数接口讲解

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

ArcGIS和ArcGIS Pro快速加载ArcGIS历史影像World Imagery Wayback

ArcGIS在线历史影像网站 World Imagery Wayback(网址:https://livingatlas.arcgis.com/wayback/)提供了数期历史影像在线浏览服务,之前不少自媒体作者在文中宣称其能代表Google Earth历史影像。 1、一点对比 (1)同一级别下的版本覆盖面 以下述区域为例,自2014年2月20…

java 邮件发送表格

邮件发送表格 问题导入效果图 实现方案1. 拼接HTML文件&#xff08;不推荐&#xff09;2. excel 转HTML使用工具类来转化依赖工具类代码示例 使用已工具包 如 aspose-cells依赖代码示例 3.使用模板生成流程准备模板工具类代码示例 问题导入 在一些定时任务中&#xff0c;经常会…

liunx环境变量学习总结

环境变量 在操作系统中&#xff0c;环境变量是一种特殊的变量&#xff0c;它们为运行的进程提供全局配置信息和系统环境设定。本文将介绍如何自定义、删除环境变量&#xff0c;特别是对重要环境变量PATH的管理和定制&#xff0c;以及与环境变量相关的函数使用。 自定义环境变…

《哈迪斯》自带的Lua解释器是哪个版本?

玩过《哈迪斯》&#xff08;英文名&#xff1a;Hades&#xff09;吗&#xff1f;最近在研究怎么给这款游戏做MOD&#xff0c;想把它的振动体验升级到更高品质的RichTap。N站下载了一些别人做的MOD&#xff0c;发现很多都基于相同的格式&#xff0c;均是对游戏.sjon文件或.lua文…

LeetCode-64. 最小路径和【数组 动态规划 矩阵】

LeetCode-64. 最小路径和【数组 动态规划 矩阵】 题目描述&#xff1a;解题思路一&#xff1a;动态规划五部曲。定推初遍举解题思路二&#xff1a;动态规划优化空间&#xff0c;直接改grid解题思路三&#xff1a;dfs 题目描述&#xff1a; 给定一个包含非负整数的 m x n 网格 …

Python代码识别minist手写数字【附pdf】

一、概述 对于人类而言&#xff0c;要识别图片中的数字是一件很容易的事情&#xff0c;但是&#xff0c;如何让机器学会理解图片上的数字&#xff0c;这似乎并不容易。那么&#xff0c;能否找出一个函数&#xff08;模型&#xff09;&#xff0c;通过输入相关的信息&#xff0…

最新版手机软件App下载排行网站源码/App应用商店源码

内容目录 一、详细介绍二、效果展示1.部分代码2.效果图展示 三、学习资料下载 一、详细介绍 一款简洁蓝色的手机软件应用app下载排行&#xff0c;app下载平台&#xff0c;最新手机app发布网站响应式织梦模板。 主要有&#xff1a;主页、app列表页、app介绍详情页、新闻资讯列…

Linux虚拟网络设备:底层原理与性能优化深度解析

在深入探讨Linux虚拟网络设备的底层原理之前&#xff0c;重要的是要理解这些设备如何在Linux内核中实现&#xff0c;以及它们如何与操作系统的其他部分交互以提供高效且灵活的网络功能。虚拟网络设备在现代网络架构中发挥着关键作用&#x1f511;&#xff0c;特别是在云计算☁️…

LeetCode-1143. 最长公共子序列【字符串 动态规划】

LeetCode-1143. 最长公共子序列【字符串 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;动规五部曲解题思路二&#xff1a;1维DP解题思路三&#xff1a;0 题目描述&#xff1a; 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。…

关于转义符 \ 在php正则中的匹配问题

今天做题遇到一个很经典的问题&#xff0c;记录一下&#xff0c;先看一段代码 <?php $str&#xff0c;&#xff0c;"\\"; $pattern&#xff0c;&#xff0c;"/\\/"; if(preg_match($partern,$str,$arr)) { &#xff0c;&#xff0c;&#xff0c;&…