【算法|动态规划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 <= 200
  • 1 <= 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];}
};

最后就通过啦!!!

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/159463.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

软件开源快速开发框架:降本增效,助力流程化办公!

随着时代的进步和社会的发展&#xff0c;应用软件开源快速开发框架的优势特点&#xff0c;可以让不少客户朋友顺利实现流程化办公&#xff0c;朝着数字化方向迈进。流辰信息是专业研发低代码技术平台的服务商&#xff0c;一直在低代码平台领域深耕细作&#xff0c;努力钻研&…

海思平台SS528V100编译 linux kernel tun.c eth_get_headlen 编译 出错的问题

osdrv目录下 make kernel 会去opensource目录下解压linux内核压缩包 同时打上很多补丁 如上图 查看Makefile 如下 有打补丁的命令 然后 然后我们的应用程序用到一个特性 需要打开tun/tab这两个属性 打开之后编译内核出错 查到最后发现 没打补丁之前的文件 没问题 …

论文阅读:Offboard 3D Object Detection from Point Cloud Sequences

目录 概要 Motivation 整体架构流程 技术细节 3D Auto Labeling Pipeline The static object auto labeling model The dynamic object auto labeling model 小结 论文地址&#xff1a;[2103.05073] Offboard 3D Object Detection from Point Cloud Sequences (arxiv.o…

Springboot-MyBatisPlue入门

一 创建项目&#xff0c;选择spring boot 初始化&#xff0c;配置相关信息 第五步创建实体类 二 快速开发实体类的jar包--lombok <dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><version>1.18.12<…

OpenCV完美实现两张图片的全景拼接(详细教程)

目录 1&#xff0c;主要步骤 1.1 导入需要的包和模块&#xff0c;并读取两张待拼接的图片&#xff0c;这里我们假设它们为 left.jpg 和 right.jpg。 1.2 创建SIFT检测器 1.3 创建一个基于 FLANN 的匹配器 1.4 筛选过程删除掉一些不合适的匹配点&#xff0c;只保留最好的…

Hadoop3教程(十二):MapReduce中Shuffle机制的概述

文章目录 &#xff08;95&#xff09; Shuffle机制什么是shuffle&#xff1f;Map阶段Reduce阶段 参考文献 &#xff08;95&#xff09; Shuffle机制 面试的重点 什么是shuffle&#xff1f; Map方法之后&#xff0c;Reduce方法之前的这段数据处理过程&#xff0c;就叫做shuff…

利用ChatGPT练习口语

目录 ChatGPT 这两天发布了一个激动人心的新功能&#xff0c;App端&#xff08;包括iOS和Android&#xff09;开始支持语音对话以及图片识别功能。 这两个功能一如既往的优先开放给Plus用户使用&#xff0c;现在将App更新到最新版本&#xff0c;就能体验。 为什么说激动人心&a…

解决 vscode使用Prettier格式化js文件报错:Cannot find module ‘./parser-babylon‘

报错如下&#xff1a; ["ERROR" - 11:48:58] Error formatting document. ["ERROR" - 11:48:58] Cannot find module ./parser-babylon Require stack: - d:\VueCode\VueProject\myqqmusic\node_modules\prettier\index.js - c:\Users\Administrator.SKY-2…

ROS键盘遥控机器人,通过参数服务器指定速度

1、引言 在上节的驱动机器人&#xff0c;我们知道是cmd_vel话题发布一串Twist类型消息来控制&#xff0c;我们可以输入如下命令查看这个Twist的详细信息&#xff1a;rosmsg show geometry_msgs/Twist geometry_msgs/Vector3 linear float64 x float64 y float64 z geome…

1-图像读取

skimage import skimage from skimage import io, color# 读取灰度图&#xff0c;能做到16bit无损 img io.imread(CT-220s_681.tif) # 直接就是numpy类型&#xff0c;dtype根据图片格式决定,np默认float64格式 print(img.shape, type(img), img.dtype) print(img)# 读取彩色…

IDEA spring-boot项目启动,无法加载或找到启动类问题解决

问题描述&#xff1a;找不到或无法加载主类 xxx.xxx.xxx.Classname 解决方案&#xff1a; 1.检查启动设置&#xff1a; 启动类所在包运行环境&#xff08;一般选择默认即可&#xff09;设置完成即可进行运行测试 2.如果第一步没有解决问题&#xff0c;试着第二步&#xff1a…

广州华锐互动:炼钢工厂VR仿真实训系统

随着科技的发展&#xff0c;我们的教育体系和职业培训方法也在迅速变化。其中&#xff0c;虚拟现实&#xff08;VR&#xff09;技术的出现为我们提供了一种全新的学习和培训方式。特别是在需要高度专业技能和安全性的领域&#xff0c;如钢铁冶炼。本文将探讨如何使用VR进行钢铁…

机器人控制算法——两轮差速驱动运动模型

1.Introduction 本文主要介绍针对于两轮差速模型的逆运动学数学推导。因为在机器人控制领域&#xff0c;决策规划控制层给执行器输出的控制指令v(车辆前进速度)和w(角速度)&#xff0c;因此&#xff0c;我们比较关心&#xff0c;当底层两个驱动电机接收到此信息&#xff0c;如何…

Rust 基础

文章目录 一、变量1.1 不可变变量/可变变量/常量1.2 变量的可覆盖性 二、数据类型2.1 数据类型 & 编译器自动推导机制2.2 标量与复合 三、函数3.1 普通函数3.2 匿名函数/闭包3.3 函数指针3.4 高阶函数3.5 函数部分完整代码&#xff1a; 一、变量 1.1 不可变变量/可变变量/…

自定义安装Redhat8.6镜像:

目录 一、创建虚拟机 二、选择需要安装的镜像 三、选择正确的操作系统和版本 四、更改虚拟机名称和位置 五、配置处理器和内核数量以及内存 配置规则&#xff1a; 六、网络类型、I/O控制类型、磁盘类型使用推荐 即可 网络类型&#xff1a; I/O控制类型: 磁盘类型: 七…

报道 | 2023-2024年1月国际运筹优化会议汇总

2023年10月、11月、12月召开会议汇总&#xff1a; 2023 International Conference on Optimization and Applications (ICOA) Location: Abu Dhabi, United Arab Emirates Important dates: Conference: October 05-06, 2023 Details: https://lct.ac.ae/en/icoa/ 2023 INF…

21GA-ELM,遗传算法优化ELM预测,并和优化前后以及真实数值进行对比,确定结果,基于MATLAB平台,程序已经调通,可以直接运行,需要直接拍下。

GA-ELM&#xff0c;遗传算法优化ELM预测&#xff0c;并和优化前后以及真实数值进行对比&#xff0c;确定结果&#xff0c;基于MATLAB平台&#xff0c;程序已经调通&#xff0c;可以直接运行&#xff0c;需要直接拍下。 21matlab时间序列预测极限学习遗传优化算 (xiaohongshu.co…

【算法|前缀和系列No.1】牛客网 DP34 【模板】前缀和

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【牛客网刷题】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希…

如何从 Pod 内访问 Kubernetes 集群的 API

Kubernetes API 是您检查和管理集群操作的途径。您可以使用Kubectl CLI、工具(例如curl)或流行编程语言的官方集成库来使用 API 。 该 API 也可供集群内的应用程序使用。Kubernetes Pod 会自动获得对 API 的访问权限,并且可以使用提供的服务帐户进行身份验证。您可以通过使…

19 | 如何搞清楚事务、连接池的关系?正确配置是怎样的

事务的基本原理 在学习 Spring 的事务之前&#xff0c;你首先要了解数据库的事务原理&#xff0c;我们以 MySQL 5.7 为例&#xff0c;讲解一下数据库事务的基础知识。 我们都知道 当 MySQL 使用 InnoDB 数据库引擎的时候&#xff0c;数据库是对事务有支持的。而事务最主要的作…