[Algorithm][动态规划][01背包问题][目标和][最后一块石头的重量Ⅱ]详细讲解
目录
- 1.目标和
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 2.最后一块石头的重量 II
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
1.目标和
1.题目链接
- 目标和
2.算法原理详解
-
问题转化:在数组中选择一些数,让这些数的和等于
a,一共有多少种选法?–> 01背包

-
思路:
-
确定状态表示 ->
dp[i][j]的含义dp[i]j]:从前i个数中**选**,总和正好等于j,一共有多少种选法
-
推导状态转移方程:根据最后一个位置的情况,分情况讨论
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

-
初始化:
- 多开一行及一列虚拟结点
- 第一列除
[0, 0],其余无需初始化- 这里第一列不会越界访问,可以交给DP阶段处理
- 因为只有
dp[i - 1][j - nums[i]]可能越界访问- 但是在判定后,只有
j == nums[i] == 0的情况,才会进入第一列,此时又不会越界 - 如果不符合条件,就不会进来,也不会触发越界访问

- 但是在判定后,只有
-
确定填表顺序:从上往下
-
确定返回值:
dp[n][a]
-
-
滚动数字优化同[模板] 背包
3.代码实现
// v1.0
int findTargetSumWays(vector<int>& nums, int target)
{// 问题转换int sum = 0;for(auto& x : nums){sum += x;}int aim = (sum + target) / 2;// 边界处理if(aim < 0 || (sum + target) % 2) return 0;int n = nums.size();vector<vector<int>> dp(n + 1, vector<int>(aim + 1));dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= aim; j++) // 第一列没有初始化,也在DP阶段处理{dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]){dp[i][j] += dp[i - 1][j - nums[i - 1]];}}}return dp[n][aim];
}
-----------------------------------------------------------------------
// v2.0 滚动数组优化
int findTargetSumWays(vector<int>& nums, int target)
{// 问题转换int sum = 0;for(auto& x : nums){sum += x;}int aim = (sum + target) / 2;// 边界处理if(aim < 0 || (sum + target) % 2) return 0;int n = nums.size();vector<int> dp(aim + 1);dp[0] = 1;for(int i = 1; i <= n; i++){for(int j = aim; j >= nums[i - 1]; j--){dp[j] += dp[j - nums[i - 1]];}}return dp[aim];
}
2.最后一块石头的重量 II
1.题目链接
- 最后一块石头的重量 II
2.算法原理详解
-
问题转化:在数组中选择一些数,让这些数的和尽可能接近
sum / 2- 问题转化成了目标和–> 01背包

- 问题转化成了目标和–> 01背包
-
思路:
-
确定状态表示 ->
dp[i][j]的含义dp[i]j]:从前i个数中**选**,总和不超过j,此时的最大和
-
推导状态转移方程:根据最后一个位置的情况,分情况讨论
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])

-
初始化:
- 多开一行及一列虚拟结点
- 第一列除
[0, 0],其余无需初始化- 这里第一列不会越界访问,可以交给DP阶段处理
- 因为只有
dp[i - 1][j - stones[i - 1]]可能越界访问- 但是在判定后,只有
j == stones[i - 1] == 0的情况,才会进入第一列,此时又不会越界 - 如果不符合条件,就不会进来,也不会触发越界访问

- 但是在判定后,只有
-
确定填表顺序:从上往下
-
确定返回值:
sum - 2 * dp[n][sum / 2]
-
-
滚动数字优化同[模板] 背包
3.代码实现
// v1.0
int lastStoneWeightII(vector<int>& stones)
{int sum = 0;for(auto& x : stones){sum += x;}int n = stones.size(), m = sum / 2;vector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++){for(int j = 0; j <= m; 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 - 2 * dp[n][m];
}
-----------------------------------------------------------------------
// v2.0 滚动数组优化
int lastStoneWeightII(vector<int>& stones)
{int sum = 0;for(auto& x : stones){sum += x;}int n = stones.size(), m = sum / 2;vector<int> dp(m + 1);for(int i = 1; i <= n; i++){for(int j = m; j >= stones[i - 1]; j--){dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);}}return sum - 2 * dp[m];
}
相关文章:
[Algorithm][动态规划][01背包问题][目标和][最后一块石头的重量Ⅱ]详细讲解
目录 1.目标和1.题目链接2.算法原理详解3.代码实现 2.最后一块石头的重量 II1.题目链接2.算法原理详解3.代码实现 1.目标和 1.题目链接 目标和 2.算法原理详解 问题转化:在数组中选择一些数,让这些数的和等于a,一共有多少种选法?…...
LabVIEW控制PLC的实现方式
LabVIEW与PLC的结合可以充分发挥两者的优点,实现更高效、灵活和可靠的自动化控制系统。本文将详细介绍LabVIEW控制PLC的实现方式,包括通信接口、数据交换、编程方法及实际应用案例,帮助用户理解并应用这一技术。 通信接口 常见通信协议 La…...
JSTL知识点讲解与配置
JSTL(JavaServer Pages Standard Tag Library)是Java EE平台中的一个标准库,提供了一组用于在JSP(JavaServer Pages)中简化和标准化常见任务的标签。这些标签封装了很多常见的JSP功能,可以使得JSP页面更加简…...
Autodesk 3ds Max软件下载安装;3ds Max功能强大的三维建模、渲染软件安装包获取
3ds Max,无论是初学者还是资深设计师,都能通过3ds Max在数字世界中实现自己的创意,打造出令人惊叹的三维作品。 在3ds Max中,灯光系统是至关重要的一环。它提供了光度学灯光和标准灯光两种主要类型,用于照亮和增强场景…...
联合体和枚举<C语言>
导言 在C语言中除了结构体外,联合体和枚举也是自定义类型,联合体主要用于节省空间,在同一块内存存储多种类型的数据,而枚举可以提高代码的可读性、可维护性。 联合体(union) 它还有个更容易理解的名字&…...
算法人生(21):从“React框架”看“情绪管理”
说起React框架,我们知道它是一种由Facebook开发和维护的开源JavaScript库,主要用于构建用户界面,特别是单页应用程序(SPA)。React框架围绕组件化,即把用户界面拆分为可复用的独立组件,每个组件负…...
千益畅行:合法合规的旅游卡服务,真实可靠的旅游体验
近期,关于千益畅行旅游卡服务的讨论引起了广泛关注。然而,网络上出现了一些对其误解和质疑的声音。为了澄清事实,我们深入了解了千益畅行的运营模式和业务特点,发现它是一家合法合规的旅游卡服务提供商,为消费者提供真…...
Linux下软件安装
提示:制作不易,可以点个关注和收藏哦。 前言 介绍 Ubuntu 下软件安装的几种方式,及 apt,dpkg 工具的使用。 提示:以下是本篇文章正文内容,下面案例可供参考. 一、先体验一下 比如我们想安装一个软件&…...
在线按模板批量生成文本工具
具体请前往:在线按模板批量生成文本工具...
Linux之关机重启
服务器除了通过界面 进行关机,重启操作,还可以通过命令的方式实现 shutdown [-t seconds] [-rkhncfF] time [message] 常用选项 参数功能-t seconds设定在几秒钟之后进行关机程序-k并不会真的关机,只是将警告讯息传送给所有使用者-r关机后重…...
【Android】使用EventBus进行线程间通讯
EventBus 简介 EventBus:github EventBus是Android和Java的发布/订阅事件总线。 简化组件之间的通信 解耦事件发送者和接收者 在 Activities, Fragments, background threads中表现良好 避免复杂且容易出错的依赖关系和生命周期问题 Publisher使用post发出…...
Leetcode 3179. Find the N-th Value After K Seconds
Leetcode 3179. Find the N-th Value After K Seconds 1. 解题思路2. 代码实现 题目链接:3179. Find the N-th Value After K Seconds 1. 解题思路 这一题的话还是一个动态规划的问题,核心递推关系式为: dp(n, k) dp(n-1, k) dp(n, k)我…...
发光二极管十大品牌
日常电路设计中,LED是必用的元器件之一,辅助判定电路异常。 十大发光二极管品牌-LED灯珠生产厂家哪家好-LED发光二极管厂家前十-Maigoo品牌榜...
nginx配置文件
Nginx是一个高性能的HTTP和反向代理服务器,它的配置文件是其灵活性和强大功能的核心。Nginx的配置文件通常位于 /etc/nginx/nginx.conf 或者 /usr/local/nginx/conf/nginx.conf,取决于你的操作系统和安装路径。配置文件的结构和语法决定了Nginx如何处理请…...
Linux基础I/O
一,系统文件I/O 写文件: #include <stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> #include <string.h> int main() {umask(0);int fd open("myfile", O_WRO…...
视觉SLAM14精讲——相机与图像3.1
视觉SLAM14精讲 三维空间刚体运动1.0三维空间刚体运动1.1三维空间刚体运动1.2李群与李代数2.1相机与图像3.1 视觉SLAM14精讲——相机与图像3.1 视觉SLAM14精讲简介相机模型内参K 简介 相机是VSLAM中的核心传感器。本章知识点内容涉及到相机相关的知识以及3D计算视觉的一些基础…...
ARM功耗管理框架之SCP
安全之安全(security)博客目录导读 目录 一、功耗管理框架中的SCP 二、SCP的示例 三、SCP固件 四、SCP启动流程 五、SCP的memory map 六、SCP与AP的通信 思考:功耗管理框架?SCP?PPU?LPI?之间的关系?…...
uni-app学习--基础组件使用、页面生命周期、本地存储、网络请求、条件编译、路由跳转
文章目录 1. 基本组件的使用1. text文本组件的使用2. view视图容器组件的使用3. button按钮组件的使用4. image组件的使用5. map组件 2. uni-app中的样式1. uni-app:px2rpx计算 3. uni-app的数据绑定1. 基本的数据绑定2. v-bind,v-for,v-on 4. uni-app的生命周期1. …...
Cweek4+5
C语言学习 十.指针详解 6.有关函数指针的代码 代码1:(*(void (*)())0)(); void(*)()是函数指针类型,0是一个函数的地址 (void(*)())是强制转换 总的是调用0地址处的函数,传入参数为空 代码2:void (*signal(int, void(*)(int))…...
Segment Anything CSharp| 在 C# 中通过 OpenVINO™ 部署 SAM 模型实现万物分割
OpenVINO™ C# API 是一个 OpenVINO™ 的 .Net wrapper,应用最新的 OpenVINO™ 库开发,通过 OpenVINO™ C API 实现 .Net 对 OpenVINO™ Runtime 调用.Segment Anything Model(SAM)是一个基于Transformer的深度学习模型&#x…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
