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

动态规划-背包问题——1049.最后一块石头的重量II

1.题目解析

题目来源

1049.最后一块石头的重量II——力扣

测试用例 

2.算法原理

首先需要将该问题转化为0-1背包问题后再做分析 

 

1.状态表示

根据数学中的知识我们知道将一个数字分为两个子数后求这两个子数的最小差值,那么就要求这两个子数尽可能接近于原数字的一半,那么就一定会出现一大一小两个数或者两个相等的数,这时就需要去找总和不大于原数字一半的数字,然后找到另一半,用另一半减去找到的数字即可,所以需要二维dp表,第一个下标表示已经寻找数字的区间,第二个下标表示此时已寻找并选择数字的总和,即dp[i][j]:在[1,i]区间选择的数字总和不大于(小于或等于) j 的总和大小

2.状态转移方程

首先依旧是背包问题的思路,对最后一个位置进行分类讨论,首先判断当第i个位置不会选取,此时就找到dp[i-1][j],判断此时的方法数;然后判断选取第i个位置的数,此时就需要寻找到dp[i-1][j-nums[i-1]]这个位置的dp表的值,然后加到总方法数中去,当然需要判断j>=nums[i-1]

3.初始化

4.填表顺序

从上到下,每一行从左到右

5.返回值

返回两个子数相减,也就是sum - dp[n][aim]*2(sum - dp[n][aim] 与 dp[n][aim]两个子数)

3.实战代码

class Solution {
public:int lastStoneWeightII(vector<int>& stones){int sum = 0;for(auto e : stones){sum += e;}    int aim = sum / 2;int n = stones.size();vector<vector<int>> dp(n+1,vector<int>(aim+1));for(int i = 1;i <= n;i++){for(int j = 0;j <= aim;j++){dp[i][j] = dp[i-1][j];if(j >= stones[i-1]){dp[i][j] = max(dp[i][j],dp[i-1][j - stones[i-1]] + stones[i-1]);}}}return sum - dp[n][aim] - dp[n][aim];}
};

 代码解析

空间优化 

相关文章:

动态规划-背包问题——1049.最后一块石头的重量II

1.题目解析 题目来源 1049.最后一块石头的重量II——力扣 测试用例 2.算法原理 首先需要将该问题转化为0-1背包问题后再做分析 1.状态表示 根据数学中的知识我们知道将一个数字分为两个子数后求这两个子数的最小差值&#xff0c;那么就要求这两个子数尽可能接近于原数字的一…...

【C++学习(37)】并发性模式:如生产者-消费者、读写锁等。 架构模式:如MVC、MVVM等。属于23 种设计模式吗? RAII 的关系?

并发性模式(如生产者-消费者、读写锁等)和架构模式(如 MVC、MVVM 等)并不属于 Gang of Four(GoF) 提出的 23 种经典设计模式 中。这些模式是其他领域中的设计模式,虽然它们和 GoF 的设计模式有交集,尤其是在程序架构和资源管理方面,但并不直接包含在 GoF 的 23 种设计…...

[Mysql] Mysql的多表查询----多表关系(下)

4、操作 方式二&#xff1a;创建表之后设置外键约束 外键约束也可以在修改表时添加&#xff0c;但是添加外键约束的前提是&#xff1a;从表中外键列中的数据必须与主表中主键列中的数据一致或者是没有数据。 语法&#xff1a; alter table <从表名> add constr…...

命名空间(namespace)详解(一)

域 在学习命名空间之前&#xff0c;我们首先要了解几种常见的域 一、域的种类 1、类作用域 类作用域是指定义在类内部的成员&#xff08;包括数据成员和成员函数&#xff09;的可见性和访问权限的范围 代码示例&#xff1a; #define _CRT_SECURE_NO_WARNINGS 1#include &…...

HarmonyOS ArkTs 解决流式传输编码问题

工作日志 日期&#xff1a;2024-11-15 标题&#xff1a;HarmonyOS ArkTs 解决流式传输编码问题 问题描述 问题&#xff1a;在处理流式数据的 HTTP 请求时&#xff0c;服务器返回的数据存在编码问题&#xff0c;导致数据无法正确地解码为字符串。部分数据在解码后出现了乱码…...

NPOI 实现Excel模板导出

记录一下使用NPOI实现定制的Excel导出模板&#xff0c;已下实现需求及主要逻辑 所需Json数据 对应参数 List<PurQuoteExportDataCrInput> listData [{"ItemName": "电缆VV3*162*10","Spec": "电缆VV3*162*10","Uom":…...

【OpenGL】OpenGL简介

文章目录 OpenGL概述OpenGL的本质OpenGL相关库核心库窗口管理glutfreeglutglfw 函数加载glewGLAD OpenGL概述 OpenGL(Open Graphics Library) 严格来说&#xff0c;本身并不是一个API&#xff0c;它是一个由Khronos组织制定并维护的规范(Specification)。OpenGL规范严格规定了…...

shell命令笔记

一、shell基本基础知识 1. shell命令中捕获上一个命令执行是否成功&#xff0c;通过判断 $? 是否为0&#xff0c;为0则表示成功&#xff0c;其他错误码则表示执行失败。 2. sheel命令中&#xff0c;变量赋值时默认都是字符串类型。赋值时须注意单引号与双引号的区别&#xf…...

qml显示OpenCV mat图片

文章目录 方式一QQuickPaintedItem 类介绍主要特点使用方法示例代码在 QML 中使用主要方法和属性注意事项编写OpenCV mat显示代码方式二本篇博客介绍在Qt6.5.3 qml项目里介绍如何显示OpenCV mat图片。视频:https://edu.csdn.net/learn/40003/654043?spm=3001.4143 在qml里显示…...

类与对象(2)---类的6个默认成员函数

1.类的6个默认成员函数 任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员函数。 默认成员函数&#xff1a;用户没有显式实现&#xff0c;编译器会生成的成员函数称为默认成员函数。 2.构造函数 2.1构造函数特性 构造函数的主要任务是初始化对象。 它有如下特…...

华为云租户网络-用的是隧道技术

1.验证租户网络是vxlan 2.验证用OVS 2.1控制节点VXLAN 本端ip&#xff08;local ip&#xff09;192.168.31.8 2.2计算节点VXLAN 本端ip&#xff08;local ip&#xff09;192.168.31.11 计算节点用的是bond0做隧道网络 2.3查看bond文件是否主备模式...

手搓神经网络(MLP)解决MNIST手写数字识别问题 | 数学推导+代码实现 | 仅用numpy,tensor和torch基本计算 | 含正反向传播数学推导

手写数字识别&#xff08;神经网络入门&#xff09; 文章目录 手写数字识别&#xff08;神经网络入门&#xff09;实验概述实验过程数据准备模型实现线性变换层前向传播反向传播更新参数整体实现 激活函数层&#xff08;ReLU&#xff09;前向传播反向传播整体实现 Softmax层&am…...

esp32c3安装micropython环境

esp32c3竟然支持micropython环境&#xff0c;真的太让人高兴了。主要是python开发比较友好&#xff0c;开发速度要快于C和C&#xff0c; 可以用来快速创意验证。 下载 首先到官网&#xff1a;MicroPython - Python for microcontrollers 点击“download”进入下载页面&#…...

ES6的Iterator 和 for...of 循环

写在前面 在JavaScript中&#xff0c;Iterator&#xff08;遍历器&#xff09;是一种接口&#xff0c;用于遍历数据结构&#xff08;如数组、对象等&#xff09;中的元素。它提供了一种统一的方式来访问集合中的每个项&#xff0c;包括值和位置。 默认 Iterator 接口 许多内…...

《C语言程序设计现代方法》note-4 基本类型 强制类型转换 类型定义

文章目录 助记提要7章 基本类型7.1 整数类型有符号整数和无符号整数整数类型的说明符整数类型的范围整型常量整数溢出读/写整数 7.2 浮点类型浮点数的范围浮点常量读/写浮点数 7.3 字符类型字符被当做整数来操作转义序列大小写转换scanf和printf读/写字符getchar和putchar读写字…...

MySQL(4)【数据类型 —— 数值类型】

阅读导航 引言一、数据类型分类二、数值类型取值范围三、tinyint 类型1. &#x1f4bb;数值越界测试⭕有符号案例⭕无符号案例 四、bit 类型1. 基本语法2. 使用示例✅创建表并插入数据✅使用 BIT 存储多个设置✅查询和格式化 BIT 数据✅更新 BIT 数据 五、小数类型1. float&…...

Golang超详细入门教程

Golang超详细入门教程 部分图片可能加载不出来&#xff0c;所以这里我上传到了自己的个人网站上也可以查看&#xff1a;http://dahua.bloggo.chat/testimonials/490.html 一、数据类型转换 C语言中数据可以隐式转换或显示转换, 但是Go语言中数据只能显示转换格式: 数据类型(…...

鸿蒙NEXT自定义组件:太极Loading

【引言】&#xff08;完整代码在最后面&#xff09; 本文将介绍如何在鸿蒙NEXT中创建一个自定义的“太极Loading”组件&#xff0c;为你的应用增添独特的视觉效果。 【环境准备】 电脑系统&#xff1a;windows 10 开发工具&#xff1a;DevEco Studio NEXT Beta1 Build Vers…...

FPGA 第7讲 简单组合逻辑译码器

时间&#xff1a;2024.11.15 一、学习内容 1.译码器 译码是编码的逆过程&#xff0c;在编码时&#xff0c;每一种二进制代码&#xff0c;都赋予了特定的含义&#xff0c;即都表示了一个确定的信号或者对象。把代码状态的特定含义翻译出来的过程叫做译码&#xff0c;实现译码操…...

opencv kdtree pcl kdtree 效率对比

由于项目中以一个环节需要使用kdtree ,对性能要求比较严苛&#xff0c;所以看看那个kdtree效率高一些。对比了opencv和pcl。 #include <array> #include <deque> #include <fstream> #include <opencv2/highgui.hpp> #include <opencv2/imgproc.hpp…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...