动态规划-背包问题——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.状态表示 根据数学中的知识我们知道将一个数字分为两个子数后求这两个子数的最小差值,那么就要求这两个子数尽可能接近于原数字的一…...
【C++学习(37)】并发性模式:如生产者-消费者、读写锁等。 架构模式:如MVC、MVVM等。属于23 种设计模式吗? RAII 的关系?
并发性模式(如生产者-消费者、读写锁等)和架构模式(如 MVC、MVVM 等)并不属于 Gang of Four(GoF) 提出的 23 种经典设计模式 中。这些模式是其他领域中的设计模式,虽然它们和 GoF 的设计模式有交集,尤其是在程序架构和资源管理方面,但并不直接包含在 GoF 的 23 种设计…...
[Mysql] Mysql的多表查询----多表关系(下)
4、操作 方式二:创建表之后设置外键约束 外键约束也可以在修改表时添加,但是添加外键约束的前提是:从表中外键列中的数据必须与主表中主键列中的数据一致或者是没有数据。 语法: alter table <从表名> add constr…...
命名空间(namespace)详解(一)
域 在学习命名空间之前,我们首先要了解几种常见的域 一、域的种类 1、类作用域 类作用域是指定义在类内部的成员(包括数据成员和成员函数)的可见性和访问权限的范围 代码示例: #define _CRT_SECURE_NO_WARNINGS 1#include &…...
HarmonyOS ArkTs 解决流式传输编码问题
工作日志 日期:2024-11-15 标题:HarmonyOS ArkTs 解决流式传输编码问题 问题描述 问题:在处理流式数据的 HTTP 请求时,服务器返回的数据存在编码问题,导致数据无法正确地解码为字符串。部分数据在解码后出现了乱码…...
NPOI 实现Excel模板导出
记录一下使用NPOI实现定制的Excel导出模板,已下实现需求及主要逻辑 所需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) 严格来说,本身并不是一个API,它是一个由Khronos组织制定并维护的规范(Specification)。OpenGL规范严格规定了…...
shell命令笔记
一、shell基本基础知识 1. shell命令中捕获上一个命令执行是否成功,通过判断 $? 是否为0,为0则表示成功,其他错误码则表示执行失败。 2. sheel命令中,变量赋值时默认都是字符串类型。赋值时须注意单引号与双引号的区别…...
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个默认成员函数 任何类在什么都不写时,编译器会自动生成以下6个默认成员函数。 默认成员函数:用户没有显式实现,编译器会生成的成员函数称为默认成员函数。 2.构造函数 2.1构造函数特性 构造函数的主要任务是初始化对象。 它有如下特…...
华为云租户网络-用的是隧道技术
1.验证租户网络是vxlan 2.验证用OVS 2.1控制节点VXLAN 本端ip(local ip)192.168.31.8 2.2计算节点VXLAN 本端ip(local ip)192.168.31.11 计算节点用的是bond0做隧道网络 2.3查看bond文件是否主备模式...
手搓神经网络(MLP)解决MNIST手写数字识别问题 | 数学推导+代码实现 | 仅用numpy,tensor和torch基本计算 | 含正反向传播数学推导
手写数字识别(神经网络入门) 文章目录 手写数字识别(神经网络入门)实验概述实验过程数据准备模型实现线性变换层前向传播反向传播更新参数整体实现 激活函数层(ReLU)前向传播反向传播整体实现 Softmax层&am…...
esp32c3安装micropython环境
esp32c3竟然支持micropython环境,真的太让人高兴了。主要是python开发比较友好,开发速度要快于C和C, 可以用来快速创意验证。 下载 首先到官网:MicroPython - Python for microcontrollers 点击“download”进入下载页面&#…...
ES6的Iterator 和 for...of 循环
写在前面 在JavaScript中,Iterator(遍历器)是一种接口,用于遍历数据结构(如数组、对象等)中的元素。它提供了一种统一的方式来访问集合中的每个项,包括值和位置。 默认 Iterator 接口 许多内…...
《C语言程序设计现代方法》note-4 基本类型 强制类型转换 类型定义
文章目录 助记提要7章 基本类型7.1 整数类型有符号整数和无符号整数整数类型的说明符整数类型的范围整型常量整数溢出读/写整数 7.2 浮点类型浮点数的范围浮点常量读/写浮点数 7.3 字符类型字符被当做整数来操作转义序列大小写转换scanf和printf读/写字符getchar和putchar读写字…...
MySQL(4)【数据类型 —— 数值类型】
阅读导航 引言一、数据类型分类二、数值类型取值范围三、tinyint 类型1. 💻数值越界测试⭕有符号案例⭕无符号案例 四、bit 类型1. 基本语法2. 使用示例✅创建表并插入数据✅使用 BIT 存储多个设置✅查询和格式化 BIT 数据✅更新 BIT 数据 五、小数类型1. float&…...
Golang超详细入门教程
Golang超详细入门教程 部分图片可能加载不出来,所以这里我上传到了自己的个人网站上也可以查看:http://dahua.bloggo.chat/testimonials/490.html 一、数据类型转换 C语言中数据可以隐式转换或显示转换, 但是Go语言中数据只能显示转换格式: 数据类型(…...
鸿蒙NEXT自定义组件:太极Loading
【引言】(完整代码在最后面) 本文将介绍如何在鸿蒙NEXT中创建一个自定义的“太极Loading”组件,为你的应用增添独特的视觉效果。 【环境准备】 电脑系统:windows 10 开发工具:DevEco Studio NEXT Beta1 Build Vers…...
FPGA 第7讲 简单组合逻辑译码器
时间:2024.11.15 一、学习内容 1.译码器 译码是编码的逆过程,在编码时,每一种二进制代码,都赋予了特定的含义,即都表示了一个确定的信号或者对象。把代码状态的特定含义翻译出来的过程叫做译码,实现译码操…...
opencv kdtree pcl kdtree 效率对比
由于项目中以一个环节需要使用kdtree ,对性能要求比较严苛,所以看看那个kdtree效率高一些。对比了opencv和pcl。 #include <array> #include <deque> #include <fstream> #include <opencv2/highgui.hpp> #include <opencv2/imgproc.hpp…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...

