动态规划-背包问题——416.分割等和子集
1.题目解析
题目来源
416.分割等和子集——力扣

测试用例

2.算法原理
1.状态表示
这里背包问题基本上和母题的思路大相径庭,母题请见 [模板]01.背包 ,这里的状态表示与装满背包的情况类似,第二个下标就是当选择的物品体积直接等于j时是否可以装入"背包",本题是求是否可以将一个数组分为大小相等的两部分,不妨变换思路,求出是否可以找一些数字的和等于该数组的一半,即
dp[i][j]:选择[1,i]区间的物品,此时总"体积"完全等于j时是否可以装入"背包"
2.状态转移方程
状态转移方程需要判断最后一个位置是否可以装入"背包",以此来判断此时位置的状态
1.当不选择当前位置:dp[i][j] = dp[i-1][j],不选择则"体积"不变,也就是j不变
2.选择当前位置:需要找到前面位置是否存在,也就是dp[i-1][j-nums[i-1]],注意判断j>=nums[i-1],不然就不能使用该位置的状态

3.初始化
开辟了虚拟位置,需要对虚拟位置进行初始化

4.填表顺序
从上到下,每一行从左到右
5.返回值
返回最后一个位置的dp值
3.实战代码
class Solution {
public:bool canPartition(vector<int>& nums) {int m = nums.size();int sum = 0;for(auto e : nums){sum += e;} int aim = sum / 2;if(sum % 2 == 1){return false;}vector<vector<bool>> dp(m+1,vector<bool>(aim+1));for(int i = 0;i <= m;i++){dp[i][0] = true;}for(int i = 1;i <= m;i++){for(int j = 1;j <= aim;j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1]){dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];}}}return dp[m][aim];}
};
代码解析

代码优化
相关文章:
动态规划-背包问题——416.分割等和子集
1.题目解析 题目来源 416.分割等和子集——力扣 测试用例 2.算法原理 1.状态表示 这里背包问题基本上和母题的思路大相径庭,母题请见 [模板]01.背包 ,这里的状态表示与装满背包的情况类似,第二个下标就是当选择的物品体积直接等于j时是否可…...
Pr:视频过渡快速参考(合集 · 2025版)
Adobe Premiere Pro 自带七组约四十多个视频过渡 Video Transitions效果,包含不同风格和用途,可在两个剪辑之间创造平滑、自然的转场,用来丰富时间、地点或情绪的变化。恰当地应用过渡可让观众更好地理解故事或人物。 提示: 点击下…...
网络安全---安全见闻2
网络安全—安全见闻 拓宽视野不仅能够丰富我们的知识体系,也是自我提升和深造学习的重要途径!!! 设备漏洞问题 操作系统漏洞 渗透测试视角:硬件设备上的操作系统可能存在各种漏洞,攻击者可以利用这些漏洞…...
解决因为TortoiseSVN未安装cmmand line client tools组件,导致idea无法使用svn更新、提交代码
一.错误信息 1.更新代码时:SVN: 更新错误 找不到要更新的版本管理目录。 2.提交代码:检测不到任何更新(实际上有代码修改)。 3.Cannot run program "svn"。 二.原因分析 在电脑上新安装的的客户端TortoiseSVN、ide…...
Ubuntu 20.04安装CUDA 11.0、cuDNN 8.0.5
不知道咋弄的ubuntu20.04电脑的cuda驱动丢了,无奈需装PyTorch环境,只有CUDA11.0以上版本才支持Ubuntu20.04,所以安装了CUDA11.0、cuDNN8.0.5 为防止频繁在浏览器检索对应的贴子,今天记录一下。 一. 驱动安装 为防止驱动安装后没…...
鸿蒙 APP 发布上架
证书创建与打包: https://developer.huawei.com/consumer/cn/doc/app/agc-help-releaseharmony-0000001933963166 不同环境多渠道打包: //todo 备案相关 一、除了发布应用商店以外,还有3个渠道,都适合小规模内测。 【1】开放式测试:发给指定白名单用户 【2】发布企业内…...
【C++笔记】C++三大特性之继承
【C笔记】C三大特性之继承 🔥个人主页:大白的编程日记 🔥专栏:C笔记 文章目录 【C笔记】C三大特性之继承前言一.继承的概念及定义1.1 继承的概念1.2继承的定义1.3继承基类成员访问方式的变化1.4继承类模板 二.基类和派生类间的转…...
如何在CentOS 7上搭建SMB服务
如何在CentOS 7上搭建SMB服务 因项目测试需求,需要自行搭建SMB服务,**SMB(Server Message Block)**协议是一种常用的文件共享方式,它可以让不同操作系统之间共享文件、打印机等资源。本文将带你一步步搭建一个简单的S…...
linux详解,基本网络枚举
基本网络枚举 一、基本网络工具 ifconfig ifconfig是一个用于配置和显示网络接口信息的命令行工具。它可以显示网络接口的P地址、子网掩码、MC地址等信息,还可以用于启动、停止或配置网络接口。 ip ip也是用于查看和管理网络接口的命令。 它提供了比ifconfig更…...
5G智能对讲终端|北斗有源终端|北斗手持机|单兵|单北斗
在当今这个快速发展的数字化时代,5G技术的广泛应用正以前所未有的速度推动着各行各业的变革。作为这一技术浪潮中的重要一环,5G智能终端QM630D凭借其卓越的性能和多样化的功能,在林业、渔业、安保、电力、交通等多个领域展现出了巨大的应用潜…...
第七部分:2. STM32之ADC实验--AD多通道(AD采集三路传感器模块实验:光敏传感器、热敏传感器、反射式传感器附赠温湿度传感器教程)
这个多通道采用非扫描模式--单次转换模式 1.代码配置链路图 2. ADC的输入通道 3.ADC的非扫描模式的转换模式(单次和连续) 4.ADC的扫描模式的转换模式(单次和连续) 5.采集校准 代码实验: 代码部分: #inclu…...
js.零钱兑换
链接:322. 零钱兑换 - 力扣(LeetCode) 题目: 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何…...
GitHub 上的开源项目推荐
GitHub 上的开源项目有成千上万,涵盖了从前端框架到数据科学、机器学习、系统工具等各个领域。不同的人根据兴趣和需求,可能会有不同的排名。不过,一些开源项目因为其广泛的应用、社区支持和技术创新,通常被认为是“最好”的开源项…...
实现Reactor反应堆模型:框架搭建
实现Reactor反应堆模型:框架搭建 Reactor模型是一种常用于处理大量并发I/O操作的设计模式,特别适用于服务器端的网络编程。该模型通过事件驱动的方式,将I/O操作的处理与具体的业务逻辑分离,从而提高系统的并发处理能力和响应速度…...
UE5 样条线组件(未完待续)
按点生成模型 按距离生成 spline mesh 可缩放spline mesh...
计算机网络常见面试题(一):TCP/IP五层模型、TCP三次握手、四次挥手,TCP传输可靠性保障、ARQ协议
文章目录 一、TCP/IP五层模型(重要)二、应用层常见的协议三、TCP与UDP3.1 TCP、UDP的区别(重要)3.2 运行于TCP、UDP上的协议3.3 TCP的三次握手、四次挥手3.3.1 TCP的三次握手3.3.2 TCP的四次挥手3.3.3 随机生成序列号的原因 四、T…...
sql速度优化多条合并为一条语句
在 SQL 中,结合 CASE 和 SUM 可以实现根据特定条件进行分组求和。在 ThinkPHP 中也可以使用类似的方式进行数据库查询操作。 例如,假设有一个销售数据表,包含字段 product_id (产品 ID)、 quantity (销…...
用 PHP或Python加密字符串,用iOS解密
可以使用对称加密算法(如 AES)来加密和解密字符串。对称加密适合这种跨平台加密解密的需求,因为可以使用相同的密钥和算法在不同的编程语言和系统之间进行加密和解密。 下面展示如何使用 Python 或 PHP 进行加密,然后用 iOS (Swi…...
docker容器启动报错error creating overlay mount to /var/lib/docker/overlay2解决办法
背景:客户提供的机器用于部署服务,拿到发现docker是部署好的,但是selinux没有关闭,于是将/etc/selinux/config中的selinux设置成了disabled,但是并未重启,就继续部署服务了;结果几天后客户重启服…...
人工智能在智能家居中的应用
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 人工智能在智能家居中的应用 人工智能在智能家居中的应用 人工智能在智能家居中的应用 引言 人工智能概述 定义与原理 发展历程 …...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
