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

[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背包
      请添加图片描述
  • 思路

    • 确定状态表示 -> 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.算法原理详解 问题转化&#xff1a;在数组中选择一些数&#xff0c;让这些数的和等于a&#xff0c;一共有多少种选法&#xff1f…...

LabVIEW控制PLC的实现方式

LabVIEW与PLC的结合可以充分发挥两者的优点&#xff0c;实现更高效、灵活和可靠的自动化控制系统。本文将详细介绍LabVIEW控制PLC的实现方式&#xff0c;包括通信接口、数据交换、编程方法及实际应用案例&#xff0c;帮助用户理解并应用这一技术。 通信接口 常见通信协议 La…...

JSTL知识点讲解与配置

JSTL&#xff08;JavaServer Pages Standard Tag Library&#xff09;是Java EE平台中的一个标准库&#xff0c;提供了一组用于在JSP&#xff08;JavaServer Pages&#xff09;中简化和标准化常见任务的标签。这些标签封装了很多常见的JSP功能&#xff0c;可以使得JSP页面更加简…...

Autodesk 3ds Max软件下载安装;3ds Max功能强大的三维建模、渲染软件安装包获取

3ds Max&#xff0c;无论是初学者还是资深设计师&#xff0c;都能通过3ds Max在数字世界中实现自己的创意&#xff0c;打造出令人惊叹的三维作品。 在3ds Max中&#xff0c;灯光系统是至关重要的一环。它提供了光度学灯光和标准灯光两种主要类型&#xff0c;用于照亮和增强场景…...

联合体和枚举<C语言>

导言 在C语言中除了结构体外&#xff0c;联合体和枚举也是自定义类型&#xff0c;联合体主要用于节省空间&#xff0c;在同一块内存存储多种类型的数据&#xff0c;而枚举可以提高代码的可读性、可维护性。 联合体&#xff08;union&#xff09; 它还有个更容易理解的名字&…...

算法人生(21):从“React框架”看“情绪管理”

说起React框架&#xff0c;我们知道它是一种由Facebook开发和维护的开源JavaScript库&#xff0c;主要用于构建用户界面&#xff0c;特别是单页应用程序&#xff08;SPA&#xff09;。React框架围绕组件化&#xff0c;即把用户界面拆分为可复用的独立组件&#xff0c;每个组件负…...

千益畅行:合法合规的旅游卡服务,真实可靠的旅游体验

近期&#xff0c;关于千益畅行旅游卡服务的讨论引起了广泛关注。然而&#xff0c;网络上出现了一些对其误解和质疑的声音。为了澄清事实&#xff0c;我们深入了解了千益畅行的运营模式和业务特点&#xff0c;发现它是一家合法合规的旅游卡服务提供商&#xff0c;为消费者提供真…...

Linux下软件安装

提示&#xff1a;制作不易&#xff0c;可以点个关注和收藏哦。 前言 介绍 Ubuntu 下软件安装的几种方式&#xff0c;及 apt&#xff0c;dpkg 工具的使用。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考. 一、先体验一下 比如我们想安装一个软件&…...

在线按模板批量生成文本工具

具体请前往&#xff1a;在线按模板批量生成文本工具...

Linux之关机重启

服务器除了通过界面 进行关机&#xff0c;重启操作&#xff0c;还可以通过命令的方式实现 shutdown [-t seconds] [-rkhncfF] time [message] 常用选项 参数功能-t seconds设定在几秒钟之后进行关机程序-k并不会真的关机&#xff0c;只是将警告讯息传送给所有使用者-r关机后重…...

【Android】使用EventBus进行线程间通讯

EventBus 简介 EventBus&#xff1a;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. 代码实现 题目链接&#xff1a;3179. Find the N-th Value After K Seconds 1. 解题思路 这一题的话还是一个动态规划的问题&#xff0c;核心递推关系式为&#xff1a; dp(n, k) dp(n-1, k) dp(n, k)我…...

发光二极管十大品牌

日常电路设计中&#xff0c;LED是必用的元器件之一&#xff0c;辅助判定电路异常。 十大发光二极管品牌-LED灯珠生产厂家哪家好-LED发光二极管厂家前十-Maigoo品牌榜...

nginx配置文件

Nginx是一个高性能的HTTP和反向代理服务器&#xff0c;它的配置文件是其灵活性和强大功能的核心。Nginx的配置文件通常位于 /etc/nginx/nginx.conf 或者 /usr/local/nginx/conf/nginx.conf&#xff0c;取决于你的操作系统和安装路径。配置文件的结构和语法决定了Nginx如何处理请…...

Linux基础I/O

一&#xff0c;系统文件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的通信 思考&#xff1a;功耗管理框架&#xff1f;SCP&#xff1f;PPU&#xff1f;LPI&#xff1f;之间的关系&#xff1f…...

uni-app学习--基础组件使用、页面生命周期、本地存储、网络请求、条件编译、路由跳转

文章目录 1. 基本组件的使用1. text文本组件的使用2. view视图容器组件的使用3. button按钮组件的使用4. image组件的使用5. map组件 2. uni-app中的样式1. uni-app&#xff1a;px2rpx计算 3. uni-app的数据绑定1. 基本的数据绑定2. v-bind,v-for,v-on 4. uni-app的生命周期1. …...

Cweek4+5

C语言学习 十.指针详解 6.有关函数指针的代码 代码1&#xff1a;(*(void (*)())0)(); void(*)()是函数指针类型&#xff0c;0是一个函数的地址 (void(*)())是强制转换 总的是调用0地址处的函数&#xff0c;传入参数为空 代码2&#xff1a;void (*signal(int, void(*)(int))…...

Segment Anything CSharp| 在 C# 中通过 OpenVINO™ 部署 SAM 模型实现万物分割

​ OpenVINO™ C# API 是一个 OpenVINO™ 的 .Net wrapper&#xff0c;应用最新的 OpenVINO™ 库开发&#xff0c;通过 OpenVINO™ C API 实现 .Net 对 OpenVINO™ Runtime 调用.Segment Anything Model&#xff08;SAM&#xff09;是一个基于Transformer的深度学习模型&#x…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

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

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