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

DAY36|动态规划Part04|LeetCode:1049. 最后一块石头的重量 II、494. 目标和、474.一和零

目录

LeetCode:1049. 最后一块石头的重量 II

基本思路

C++代码

LeetCode:494. 目标和

基本思路

C++代码

LeetCode:474.一和零

基本思路

C++代码


LeetCode:1049. 最后一块石头的重量 II

力扣代码链接

文字讲解:LeetCode:1049. 最后一块石头的重量 II

视频讲解:动态规划之背包问题,这个背包最多能装多少?

基本思路

        本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。其中石头的重量为stones[i],物品的价值也为stones[i],对应着01背包里的物品重量weight[i]和物品价值value[i]。

  • 确定dp数组以及下标的含义

        dp[j]的含义,容量为j的背包,最多可以装的价值为 dp[j]。而价值其实也就是背包中能够承载的石头的最大重量。

  • 确定递推公式

        01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);而这里的weight[i]和value[i]实际上都是stone[i],也就是石头的重量。因此,递推公式可以写成:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

  • dp数组如何初始化

        既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。根据提示易知,我们要求的target其实只是最大重量的一半,也就是15000。接下来就是如何初始化dp[j]呢,因为重量都不会是负数,所以dp[j]都初始化为0就可以了。

vector<int> dp(15001, 0);
  • 确定遍历顺序

        因为采用的是一维dp数组的方式,因此遍历物品的for循环放在外层而变量背包容量大小的for循环放在内层,并且要保证内层for循环采用倒序遍历。

for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}
}

        最后dp[target]就是容量为target的背包所能背的最大重量。在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的

C++代码

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};

LeetCode:494. 目标和

力扣代码链接

文字讲解:LeetCode:494. 目标和

视频讲解:动态规划之背包问题,装满背包有多少种方法?

基本思路

        最容易想到的就是回溯算法,但是使用回溯算法容易超时。

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum == target) {result.push_back(path);}// 如果 sum + candidates[i] > target 就终止遍历for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i + 1);sum -= candidates[i];path.pop_back();}}
public:int findTargetSumWays(vector<int>& nums, int S) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (S > sum) return 0; // 此时没有方案if ((S + sum) % 2) return 0; // 此时没有方案,两个int相加的时候要格外小心数值溢出的问题int bagSize = (S + sum) / 2; // 转变为组合总和问题,bagsize就是要求的和// 以下为回溯法代码result.clear();path.clear();sort(nums.begin(), nums.end()); // 需要排序backtracking(nums, bagSize, 0, 0);return result.size();}
};

        我们如果使用动态规划的方法,可以假设正数的总和为x,负数的总和为y,所有元素的绝对值之和为sum,目标和为target。那么易得:

        可以得到:

        这里的x实际上就是背包容量BagSize。和之前的方法不同的地方在于,前面的题是求容量为j的背包最多能装下多少。而这个题目是求,装满容量为j的背包,一共有多少种方法。

  • 确定dp数组以及下标的含义

        dp[j]表示装满容量为j的背包一共有dp[j]种方法。

  • 确定递推公式

        dp[j] = dp[j] + dp[j-nums[i]],可以理解为不包含物品i为上一次循环中的dp[j]和包含物品i的dp[j-nums[i]]。

  • dp数组如何初始化

        这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种,放0件物品。并且如果背包容量j和物品0的大小相同,此时dp[nums[i]] = 1。

  • 确定遍历顺序

        遍历物品放在外循环,遍历背包在内循环,且内循环倒序(为了保证物品只使用一次)。

C++代码

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};

LeetCode:474.一和零

力扣代码链接

文字讲解:LeetCode:474.一和零

视频讲解:动态规划之背包问题,装满这个背包最多用多少个物品?

基本思路

        这个题目依旧是一个01背包问题。但是需要统计每个字符串元素的0和1的数量,也就是两个维度的背包。

  • 确定dp数组以及下标的含义

        dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

  • 确定递推公式

        dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

        所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

  • dp数组如何初始化

        01背包的dp数组初始化为0就可以。因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

  • 确定遍历顺序

        在本题中物品就是strs里的字符串,背包容量是题目描述中的m和n分别代表了dp数组的两个维度。

for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}
}
  • 举例推导dp数组

        以输入:["10","0001","111001","1","0"],m = 3,n = 3为例

C++代码

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};

相关文章:

DAY36|动态规划Part04|LeetCode:1049. 最后一块石头的重量 II、494. 目标和、474.一和零

目录 LeetCode:1049. 最后一块石头的重量 II 基本思路 C代码 LeetCode:494. 目标和 基本思路 C代码 LeetCode:474.一和零 基本思路 C代码 LeetCode:1049. 最后一块石头的重量 II 力扣代码链接 文字讲解&#xff1a;LeetCode:1049. 最后一块石头的重量 II 视频讲解&…...

Linux 下SVN新手操作手册

下面来介绍Linux 下 SVN操作方法&#xff1a; 1、SVN的安装 Centos 7 安装Subversion sudo yum -y install subversion Ubuntu 安装Subversion sudo apt-get install subversion 自定义安装&#xff0c;官方地址&#xff1a;https://subversion.apache.org/ 2、SVN的使用…...

障碍感知 | 基于KD树的障碍物快速处理(附案例分析与ROS C++仿真)

目录 1 障碍处理与KD树2 KD树核心原理2.1 KD树的构造2.2 KD树的查找 3 仿真实现3.1 KD树基本算法3.2 ROS C仿真 1 障碍处理与KD树 在机器人感知系统中&#xff0c;传感器&#xff08;如激光雷达、摄像头等&#xff09;会采集周围的环境数据&#xff0c;例如代价地图、八叉树地…...

Electron -- Electron Fiddle(一)

Electron Fiddle 是一个由 Electron 团队开发的开源工具&#xff0c;它允许开发者快速创建、运行和调试 Electron 应用。这个工具提供了一个简洁的界面&#xff0c;使用户无需配置复杂的开发环境&#xff0c;就能快速体验和学习 Electron。强烈建议将其安装为学习工具。 学习它…...

详解Redis的常用命令

目录 KEYS 语法 EXISTS 语法 DEL 语法 EXPIRE 语法 TTL 语法 TYPE 语法 Redis数据结构和内部编码 KEYS 返回所有满⾜样式&#xff08;pattern&#xff09;的 key。 返回值&#xff1a;匹配 pattern 的所有 key。 语法 ⽀持如下统配样式: h?llo matches hello, ha…...

elasticache备份

Elasticsearch 本地快照操作流程 配置快照存储路径 在 elasticsearch.yml 文件中配置以下字段以指定数据、日志和快照存储路径&#xff1a;path:data: /data/data # 数据存储路径logs: /data/log # 日志存储路径repo: /data/snapshot # 快照存储路径确保路径 /dat…...

Tomcat负载均衡全解析

一、Java项目概述 (一)Java语言特点 Java是一种计算机应用语言,在开发王者和管理系统等方面有着广泛的应用。它具有开源免费的特性,不过需要注意的是,虽然语言本身开源,但是后期开发工具可能会收取费用。 (二)、JDK和Tomcat 1,JDK:作为Java语言的开发工具,在Linu…...

[LeetCode-Python版] 定长滑动窗口8——2461. 长度为 K 子数组中的最大和

题目 给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和&#xff1a; 子数组的长度是 k&#xff0c;且 子数组中的所有元素 各不相同 。 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件&#xff0c;返回 0 。…...

springboot476基于vue篮球联盟管理系统(论文+源码)_kaic

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统篮球联盟管理系统信息管理难度大&#xff0c;容错率低&am…...

预约参观华为基地,见证行业巅峰

✨ 大家好呀&#xff01;今天要跟大家分享一个超酷的体验&#xff0c;关于华为的参观学习之旅&#xff01;&#x1f680; 华为成立于1987年&#xff0c;位于深圳&#xff0c;是全球领先的信息与通信技术&#xff08;ICT&#xff09;解决方案供应商哦&#xff01;他们专注于科技…...

【Flink-scala】DataSet编程模型介绍及数据源

DataStream 学习 1.DataStream编程模型总结 文章目录 DataStream 学习介绍一、DataSet编程模型二、数据源1.文件类数据源2.集合类数据源3.通用类数据源4第三方文件系统 介绍 Flink把批处理看成是一个流处理的特例&#xff0c;因此可以在底层统一的流处理引擎上&#xff0c;同…...

Odrive源码分析(四) 位置爬坡算法

Odrive中自带一个简单的梯形速度爬坡算法&#xff0c;本文分析下这部分代码。 代码如下&#xff1a; #include <cmath> #include "odrive_main.h" #include "utils.hpp"// A sign function where input 0 has positive sign (not 0) float sign_ha…...

[Unity Shader][图形渲染] Shader数学基础11 - 复合变换详解

在图形学与Shader编程中,复合变换是将平移、旋转和缩放等基本几何变换组合在一起,从而实现更复杂的物体变换效果。复合变换的本质是通过矩阵的串联操作,依次应用多个变换。 本文将介绍复合变换的数学原理、矩阵计算方法及注意事项,并结合实际编程中的实现细节帮助你掌握其…...

使用Python实现智能家居控制系统:开启智慧生活的钥匙

友友们好! 我的新专栏《Python进阶》正式启动啦!这是一个专为那些渴望提升Python技能的朋友们量身打造的专栏,无论你是已经有一定基础的开发者,还是希望深入挖掘Python潜力的爱好者,这里都将是你不可错过的宝藏。 在这个专栏中,你将会找到: ● 深入解析:每一篇文章都将…...

使用 HTML5 Canvas 实现动态蜈蚣动画

使用 HTML5 Canvas 实现动态蜈蚣动画 1. 项目概述 我们将通过 HTML 和 JavaScript 创建一个动态蜈蚣。蜈蚣由多个节段组成&#xff0c;每个节段看起来像一个小圆形&#xff0c;并且每个节段上都附带有“脚”。蜈蚣的头部会在画布上随机移动。 完整代码在底部&#xff01;&…...

计算机视觉目标检测——DETR(End-to-End Object Detection with Transformers)

计算机视觉目标检测——DETR(End-to-End Object Detection with Transformers) 文章目录 计算机视觉目标检测——DETR(End-to-End Object Detection with Transformers)摘要Abstract一、DETR算法1. 摘要&#xff08;Abstract&#xff09;2. 引言&#xff08;Introduction&#…...

uniapp .gitignore

打开HBuilderX&#xff0c;在项目根目录下新建文件 .gitignore复制下面内容 #忽略unpackge目录下除了res目录的所有目录 unpackage/* !unpackage/res/#忽略.hbuilderx目录 .hbuilderx# 忽略node_modules目录下的所有文件 node_modules/# 忽略锁文件 package-lock.json yarn.l…...

JavaWeb Servlet的反射优化、Dispatcher优化、视图(重定向)优化、方法参数值获取优化

目录 1. 背景2. 实现2.1 pom.xml2.2 FruitController.java2.3 DispatcherServlet.java2.4 applicationContext.xml 3. 测试 1. 背景 前面我们做了Servlet的一个案例。但是存在很多问题&#xff0c;现在我们要做优化&#xff0c;优化的步骤如下&#xff1a; 每个Fruit请求都需…...

备忘一个FDBatchMove数据转存的问题

使用FDBatchMove的SQL导入excel表到sql表&#xff0c;设置条件时一头雾水&#xff0c;函数不遵守sql的规则。 比如替换字段的TAB键值为空&#xff0c;replace(字段名,char(9),)竟然提示错误&#xff0c;百思不得其解。 试遍了几乎所有的函数&#xff0c;竟然是chr(9)。 这个…...

CEF127 编译指南 MacOS 篇 - 编译 CEF(六)

1. 引言 经过前面的准备工作&#xff0c;我们已经完成了所有必要的环境配置。本文将详细介绍如何在 macOS 系统上编译 CEF127。通过正确的编译命令和参数配置&#xff0c;我们将完成 CEF 的构建工作&#xff0c;最终生成可用的二进制文件。 2. 编译前准备 2.1 确认环境变量 …...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

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

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

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...