leetcode热题100.分割等和子集(动态规划)

分割等和子集

Problem: 416. 分割等和子集

思路

我选择使用动态规划的方法来解题。我们需要判断是否可以将数组分割成两个子集,使得这两个子集的和相等。这个问题可以转化为在数组中找到一个子集,使得其和等于数组总和的一半。

解题过程

  1. 首先,我们计算数组的总和 total。如果 total 是奇数,那么我们无法将其分成两个和相等的子集,因此直接返回 False
  2. 接下来,我们将目标和 target 定为 total // 2
  3. 初始化一个二维布尔数组 dp,其中 dp[i][j] 表示前 i 个元素是否可以组成和为 j 的子集。
  4. 设置初始条件:dp[i][0]True,因为和为 0 的子集总是可以通过不选取任何元素来实现。
  5. 遍历数组,更新 dp 数组:
    • 如果当前元素 nums[i] 小于等于目标和 j,则 dp[i][j] 可以由两种情况得到:不包含当前元素(即 dp[i-1][j])或包含当前元素(即 dp[i-1][j-nums[i]])。
    • 如果当前元素 nums[i] 大于目标和 j,则 dp[i][j] 只能由不包含当前元素的情况得到,即 dp[i-1][j]
  6. 最后,检查 dp[n-1][target] 的值,判断是否可以将数组分割成两个和相等的子集。

复杂度

  • 时间复杂度:$O(n \cdot target)$,其中 n 是数组的长度,target 是数组总和的一半。
  • 空间复杂度: $O(n \cdot target)$,因为使用了一个二维数组 dp

Code

from typing import Listclass Solution:def canPartition(self, nums: List[int]) -> bool:n = len(nums)if n < 2:return Falsetotal = sum(nums)if total & 1:return Falsetarget = total // 2if max(nums) > target:return Falsedp = [[False] * (target + 1) for _ in range(n)]for i in range(n):dp[i][0] = Truedp[0][nums[0]] = Truefor i in range(1, n):for j in range(1, target + 1):if j >= nums[i]:dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]else:dp[i][j] = dp[i-1][j]return dp[n-1][target]

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【Django】网上蛋糕商城后台-商品管理

1.商品管理功能 当管理员点击商品管理时&#xff0c;发送服务器请求 path(admin/goods_list/, viewsAdmin.goods_list), # 处理商品列表请求 def goods_list(request):try:type request.GET["type"]except:type 0try:ym request.GET["ym"]except:ym …

5大常用的回归测试工具介绍

回归测试工具介绍 以下是一些可用于创建和执行回归测试的工具。但是&#xff0c;在决定使用哪些产品之前&#xff0c;应彻底研究每种产品的要求。 Selenium Selenium 是一个开源 Web 自动化测试工具&#xff0c;用于测试网站和 Web 应用程序。它被认为是用于Web 应用程序测试的…

路径规划 | 基于DQN深度强化学习算法的路径规划(Matlab)

目录 效果一览基本介绍程序设计参考文献 效果一览 基本介绍 DQN路径规划算法 基于深度强化学习算法的路径规划 matlab2023b 栅格环境&#xff0c;走迷宫&#xff0c;可以通过窗口界面方便观察交互过程&#xff0c;代码注释详尽。 程序设计 完整源码和数据私信博主回复基于DQN深…

【Linux信号】信号的保存、信号在内核中的表示、信号集操作函数、sigprocmask、sigpending

目录 信号在内核中的表示信号阻塞的理解 sigset_t 信号集操作函数 sigprocmask sigpending sigprocmask和sigpending都是系统调用 我们先来了解一下关于信号的一些常见概念&#xff1a; 实际执行 信号的处理动作 称为信号递达。 信号从产生到递达的之间的状态称为信号未决…

场外个股期权交割日是每个月几号?怎么参与场外个股期权?

今天带你了解场外个股期权交割日是每个月几号&#xff1f;怎么参与场外个股期权&#xff1f;在进行期权交易之前&#xff0c;投资者需要选择一个可靠的期权交易平台。 个股场外期权交易是指在股票交易所以外的场所进行的期权交易。期权是一种约定&#xff0c;根据该约定&#…

Docker网络模式和Cgroup资源限制

目录 1、Docker网络 &#xff08;1&#xff09;Docker网络实现原理 查看容器的输出和日志信息 2、Docker 的网络模式 查看docker列表 &#xff08;1&#xff09;网络模式详解 1&#xff09;host模式 2&#xff09;container模式 3&#xff09;none模式 4&#xff09;br…

小程序-3(页面导航+页面事件+生命周期+WXS)

目录 1.页面导航 声明式导航 导航到tabBar页面 导航到非tabBar页面 后退导航 编程式导航 后退导航 导航传参 声明式导航传参 编程式导航传参 在onload中接收导航参数 2.页面事件 下拉刷新 停止下拉刷新的效果 ​编辑 上拉触底 配置上拉触底距离 上拉触底的节…

spring security源码追踪理解(一)

一、前言 近期看了spring security相关的介绍&#xff0c;再加上项目所用若依框架的底层安全模块也是spring security&#xff0c;所以想从源码的角度加深下对该安全模块的理解&#xff08;看源码之前&#xff0c;我们要先有个意识&#xff0c;那就是spring security安全模块主…

一文-深入了解Ansible常见模块、安装和部署

1 Ansible 介绍 Ansible是一个配置管理系统configuration management system, python 语言是运维人员必须会的语言, ansible 是一个基于python 开发的&#xff08;集合了众多运维工具 puppet、cfengine、chef、func、fabric的优点&#xff09;自动化运维工具, 其功能实现基于ss…

Linux中nohup(no hang up)不挂起,用于在系统后台不挂断地运行命令,即使退出终端也不会影响程序的运行。

nohup的英文全称是 no hang up&#xff0c;即“不挂起”。这个命令在Linux或Unix系统中非常有用&#xff0c;主要用于在系统后台不挂断地运行命令&#xff0c;即使退出终端也不会影响程序的运行。默认情况下&#xff08;非重定向时&#xff09;&#xff0c;nohup会将输出写入一…

美国银行:高息下的稳健

“四大银行”财报悉数登场&#xff0c;折射美国经济忧虑。 今天我们来聊——美国银行 上周五摩根大通、富国银行和花旗银行发布了二季度财报&#xff0c;结果不及预期&#xff0c;股价都是一个走法&#xff0c;跌。反倒是姗姗来迟的美国银行Q2业绩超预期&#xff0c;大涨超5%。…

统计学13——时间序列分析

目录 知识结构 ​编辑内容精读 1.时间序列及其分开类 2.描述性分析 3.时间序列预测 3.1预测过程 3.2平稳时间序列 3.3趋势型序列 3.4复合型序列 名词解释 知识结构 内容精读 1.时间序列及其分开类 时间序列顾名思义就是按时间顺序观察排列而成的序列&#xff0c;根…

苍穹外卖图片不显示

上传图片到自己的阿里云oss中&#xff0c;然后对应链接放到数据库中 显示成功

Linux——开机重启、用户登录注销、用户管理、运行级别、帮助指令

目录 关机&重启命令 用户登录&注销 用户管理 用户的添加和删除 查询用户信息指令 切换用户 查看当前登录用户 用户组 用户和组相关的文件 运行级别 基本介绍 设置默认运行级别 ​编辑​编辑 找回root密码 帮助指令 关机&重启命令 用户登录&注销…

Linux工具篇:gdb(调试工具)+ makefile(自动化构建工具)

目录 前言&#xff1a; Linux调试器-gdb使用&#xff1a; Linux项目自动化构建工具-make/Makefile&#xff1a; 问题&#xff1a; 为什么makefile对最新的可执行程序&#xff0c;默认不想不想重新形成呢&#xff1f; make是如何知道到我的程序需要被编译的呢&#xff1f; …

监控系统怎样做?

监控类型自底向上分为资源监控、服务监控和业务监控。希望打造公司级的监控系统最好的时机是系统规划时&#xff0c;如果把监控设计往后放&#xff0c;将会面临一个巨大的难题&#xff1a;推行和现有不兼容的规范。 三种监控类型 资源监控 这个相对简单&#xff0c;随着k8s的兴…

【个人笔记】685. 冗余连接 II 的解释(并查集)

一棵树有n个点和n条边&#xff0c;返回一条能删除的边&#xff0c;使得剩下的图是有 n 个节点的有根树。 解释&#xff1a; 注意不冗余的有根树的特性&#xff01;**根节点入度为0&#xff0c;其余结点只有一个入度&#xff01;**所以冗余的两种情况如下&#xff1a; &#xff…

芯片基础 | Verilog仿真平台及数字逻辑仿真(上)

被测试器件DUT是一个二选一多路器,测试程序(testbench)提供测试激励及验证机制 Testbench使用行为级描述,DUT采用门级描述 下面将给出Testbench的描述、DUT的描述及如何进行混合仿真(行为级+门级) DUT (Device Under Test) module mux2_1(//Port declarations 端口声明outp…

Linux常见配置

linux 常见配置 一、配置固定IP, 主机名映射二、配置环境变量三、vim配置四、ssh配置 一、配置固定IP, 主机名映射 1、修改主机名 hostnamectl set-hostname xxx2、Centos配置固定IP 使用vim编辑/etc/sysconfig/network-scripts/ifcfg-ens33文件&#xff0c;填入下图信息 …

AI伦理之舟:航行于隐私、公正与真实的海域

&#x1f308;所属专栏&#xff1a;【其它】✨作者主页&#xff1a; Mr.Zwq✔️个人简介&#xff1a;一个正在努力学技术的Python领域创作者&#xff0c;擅长爬虫&#xff0c;逆向&#xff0c;全栈方向&#xff0c;专注基础和实战分享&#xff0c;欢迎咨询&#xff01; 您的点…