动态规划-背包问题——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…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

