动态规划-背包问题——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++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
