【算法|动态规划No.20】leetcode416. 分割等和子集
个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
点击直接跳转到该题目
目录
- 1️⃣题目描述
- 2️⃣题目解析
- 3️⃣解题代码
1️⃣题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
注意:
1 <= nums.length <= 2001 <= nums[i] <= 100
2️⃣题目解析
状态表示:
dp[i][j]:从前i个数中进行挑选,能够凑成j这个数。
状态转移方程:
- 如果不挑选第i个数则:
dp[i][j] = dp[i - 1][j] - 如果挑选第i个数
且j >= nums[i],则dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
3️⃣解题代码
class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size(), sum = 0;for(auto x : nums) sum += x;if(sum % 2 == 1) return false;vector<vector<bool>> dp(n + 1,vector<bool>(sum / 2 + 1));for(int i = 0;i <= n;i++) dp[i][0] = true;for(int i = 1;i <= n;i++){for(int j = 1;j <= sum / 2;j++){dp[i][j] = dp[i - 1][j];if(j >= nums[i - 1]) dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];}}return dp[n][sum / 2];}
};
最后就通过啦!!!

相关文章:
【算法|动态规划No.20】leetcode416. 分割等和子集
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望…...
深入解析C语言中的strstr函数
目录 一,strstr函数简介 二,strstr函数实现原理 三,strstr函数的用法 四,strstr函数的注意事项 五,strstr函数的模拟实现 一,strstr函数简介 strstr函数是在一个字符串中查找另一个字符串的第一次出现&…...
HDLbits: Fsm serial
根据题意设计了四个状态,写出代码如下: module top_module(input clk,input in,input reset, // Synchronous resetoutput done ); parameter IDLE 3b000, START 3b001, DATA 3b010, STOP 3b100, bit_counter_end 4d7;reg [2:0] state,next_sta…...
LuaJit交叉编译移植到ARM Linux
简述 Lua与LuaJit的主要区别在于LuaJIT是基于JIT(Just-In-Time)技术开发的,可以实现动态编译和执行代码,从而提高了程序的运行效率。而Lua是基于解释器技术开发的,不能像LuaJIT那样进行代码的即时编译和执行。因此&…...
【RocketMQ系列一】初识RocketMQ
您好,我是码农飞哥(wei158556),感谢您阅读本文,欢迎一键三连哦。 💪🏻 1. Python基础专栏,基础知识一网打尽,9.9元买不了吃亏,买不了上当。 Python从入门到精…...
【06】基础知识:React组件实例三大核心属性 - ref
一、 ref 了解 理解 组件内的标签可以定义 ref 属性来标识自己 使用 1、字符串形式的 ref 定义:<input ref"input"/> 获取:this.refs.input2、回调形式的 ref 定义:<input ref{currentNode > this.input curren…...
Bootstrap-媒体类型
加上媒体查询之后,只有在特定的设备之下才能起作用!!!...
spring Cloud笔记--服务治理Eureka
服务治理:Eureka 服务治理 主要用来实现各个微服务实例的自动化注册与发现 服务注册: 服务治理框架中,通常会构建一个注册中心,每个服务单元向注册中心登记自己提供的服务,将主机与端口号,版本号&#x…...
pdf压缩文件怎么压缩最小?pdf压缩方法汇总
PDF是一种常见的文件格式,通常用于电子文档和印刷品,由于PDF文件通常包含大量的元数据、字体、图像和其他元素,因此它们的大小可能会非常大。 为了解决这个问题,我们可以使用一些PDF压缩工具来帮助我们,以便我们能够更…...
Golang学习记录:基础篇练习(一)
Golang学习记录:基础篇练习(一) 1、九九乘法表2、水仙花数3、斐波那契数列4、编写一个函数,求100以内的质数5、统计字符串里面的字母、数字、空格以及其他字符的个数6、二维数组对角线的和7、冒泡排序算法8、选择排序算法9、二分查…...
sql注入(7), python 实现盲注爆破数据库名, 表名, 列名
python 实现盲注 该python脚本根据之前介绍的盲注原理实现, 对于发送的注入请求没有做等待间隔, 可能给目标服务器造成一定 压力, 所以仅限于本地测试使用. import requests, time# 时间型盲注 def time_blind(base_url, cookie):for length in range(1, 20): # 测试数据库名…...
2021年12月 Python(二级)真题解析#中国电子学会#全国青少年软件编程等级考试
Python编程(1~6级)全部真题・点这里 C/C编程(1~8级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 执行以下程序 a[33,55,22,77] a.sort() for i in a:print(i)运行…...
卡尔曼家族从零解剖-(01)预备知识点
讲解关于slam一系列文章汇总链接:史上最全slam从零开始,针对于本栏目讲解的 卡尔曼家族从零解剖 链接 :卡尔曼家族从零解剖-(00)目录最新无死角讲解:https://blog.csdn.net/weixin_43013761/article/details/133846882 文末正下方中心提供了本人 联系…...
技术分享| 二进制部署MySQL
一、介绍 MySQL是一个关系型数据库管理系统,由瑞典MySQL AB 公司开发,属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一,在 WEB 应用方面,MySQL是最好的 RDBMS (Relational Database Management System&#x…...
3.1 模板测试与深度测试(Stencil Test Z Test)
一、模板测试(Stencil Test) 模板测试可以实现的一些效果图 1.是什么 ①从渲染管线出发:模板测试是在逐片源操作阶段,透明测试之后,深度测试之前的位置。 ②从书面概念上理解 说到模板测试,就要先说道模…...
一些常见的必须会的谭浩强基本代码大全也是常考的应试是没问题的
//1. 1£¡+2£¡+3£¡+...20! /* #include <stdio.h> int main() {int i;long sum=0,k=1;for(i=1;i<=20;i++){k*=i;sum+=k;}printf("%d",sum); } *///方法2 /* #include <stdio.h> int main() {int i,j;long sum=0,k;for(i…...
C语言天花板——指针(进阶1)
接上次的指针初阶(http://t.csdnimg.cn/oox5s),这次我们继续的探寻指针的奥秘,发车咯!!!🚗🚗🚗 一、字符指针 可以看到我们将指针p给打印出来,就是…...
二、深度测试(Z Test)
1.是什么 ①从渲染管线出发 ②书面上理解 所谓深度测试,就是针对当前对象在屏幕上(更准确的说是frame buffer)对应的像素点,讲对象自身的深度值与当前该像素点缓存的深度值进行比较,如果通过了,本对象再改…...
Vue_Bug VUE-ADMIN-TEMPLATE-MASTER electron build后无法登录
Bug描述: VUE-ADMIN-TEMPLATE-MASTER 项目在经过 electron 的 build 命令后,无法登录 问题原因: 大部分vue 前段项目 会使用 js-cookie 这个库 来操作浏览器的cookie 然而这个库 在electron下 会无法使用 (最坑的是还没报错&…...
睡衣内衣服装商城小程序的作用是什么
服装行业一直都是市场很重要的组成部分,每个人都需要,且根据品牌、样式作用等可以细分很多类目,其中睡衣内衣也有不小的市场规模,从业商家多、市场需求度高。 但同时睡衣内衣经营痛点也比较明显。 当今消费者习惯于线上消费&…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

