动态规划-背包问题——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主页 ⏩ 文章专栏:《热点资讯》 人工智能在智能家居中的应用 人工智能在智能家居中的应用 人工智能在智能家居中的应用 引言 人工智能概述 定义与原理 发展历程 …...
OpenClaw安全指南:使用GLM-4.7-Flash时的权限管理
OpenClaw安全指南:使用GLM-4.7-Flash时的权限管理 1. 为什么需要特别关注OpenClaw的安全配置 当我第一次在本地部署OpenClaw并接入GLM-4.7-Flash模型时,最让我震惊的是这个框架赋予AI的权限范围。它不仅能读取我的文件,还能执行系统命令、发…...
【独家逆向分析】:2026年Python官方AOT预编译包(.so/.dylib/.dll)签名验证失败报错的底层机制——绕过签名强制校验的合规临时方案
第一章:Python原生AOT编译方案2026报错解决方法总览Python原生AOT(Ahead-of-Time)编译在2026年生态中已进入稳定试用阶段,但开发者常遭遇如 ModuleNotFoundError: No module named _aot_runtime、Unsupported AST node: Match 或 …...
TVM构建系统详解:CMake与Makefile配置最佳实践
TVM构建系统详解:CMake与Makefile配置最佳实践 引言:TVM构建系统的核心挑战 深度学习编译器TVM(Tensor Virtual Machine)作为一个跨平台、多后端的开源项目,其构建系统面临着独特的复杂性。开发者需要在不同架构&#…...
vscode-drawio扩展依赖更新:安全高效地管理第三方库
vscode-drawio扩展依赖更新:安全高效地管理第三方库 【免费下载链接】vscode-drawio This unofficial extension integrates Draw.io (also known as diagrams.net) into VS Code. 项目地址: https://gitcode.com/gh_mirrors/vs/vscode-drawio vscode-drawio…...
PvZ Toolkit:植物大战僵尸终极修改器完全指南
PvZ Toolkit:植物大战僵尸终极修改器完全指南 【免费下载链接】pvztoolkit 植物大战僵尸 PC 版综合修改器 项目地址: https://gitcode.com/gh_mirrors/pv/pvztoolkit PvZ Toolkit是一款专为植物大战僵尸PC版设计的综合性游戏修改工具,通过内存读写…...
美军“转正”美科技公司AI系统,专家解读
来源:环球时报【环球时报报道 记者 刘扬】据路透社等外媒近日报道,五角大楼将把美国科技公司Palantir的人工智能(AI)系统Maven列为“正式在编项目”,使美军多军种将该公司的相关技术用于军事领域。五角大楼强调&#x…...
AHT20传感器数据漂移?STM32硬件I2C与软件模拟的稳定性对比测试
STM32硬件I2C与软件模拟I2C在AHT20传感器应用中的稳定性深度解析 工业级环境监测系统对温湿度数据的可靠性有着严苛要求。AHT20作为一款高精度温湿度传感器,其数据采集的稳定性直接关系到整个系统的可信度。本文将深入探讨STM32平台下硬件I2C与GPIO模拟I2C两种实现方…...
ComfyUI实战:如何加载基于Flux.1微调的LoRA模型并优化推理流程
最近在项目里用 ComfyUI 部署基于 Flux.1 微调的 LoRA 模型,踩了不少坑。从模型加载失败到推理时显存爆炸,问题层出不穷。经过一番折腾,总算梳理出一套比较稳定的流程,这里把实战经验记录下来,希望能帮到有同样需求的同…...
软件信创方案(Word)
第1章 需求分析1.1 核心项目需求自主可控、资源池、云平台建设、运维运营管理、安全系统五大核心需求第2章 云平台基础设施设计2.1 改造目标与定位2.2 设计原则2.3 总体架构设计含网络架构、云平台整体架构2.4 资源配置设计含网络、计算、数据库、存储资源池及云管模块设计第3章…...
JAVA重点基础、进阶知识及易错点总结(10)Map 接口(HashMap、LinkedHashMap、TreeMap)
🚀 Java 巩固进阶 第10天 主题:Map 接口深度解析 —— 键值对的高效艺术📅 进度概览:掌握 Java 中最灵活的数据结构。 💡 核心价值: 动态数据承载:SpringBoot 中接收前端动态参数 (Map<Stri…...
