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

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...