当前位置: 首页 > 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…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Docker 运行 Kafka 带 SASL 认证教程

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

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

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

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...