【LeetCode】494.目标和
题目
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1],可以在2之前添加'+',在1之前添加'-',然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1:
输入:nums = [1,1,1,1,1], target = 3 输出:5 解释:一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
示例 2:
输入:nums = [1], target = 1 输出:1
提示:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
解答
源代码
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}if (sum - target < 0 || (sum - target) % 2 == 1) {return 0;}int len = nums.length, neg = (sum - target) / 2;int[][] dp = new int[len + 1][neg + 1];dp[0][0] = 1;for (int i = 1; i < len + 1; i++) {int num = nums[i - 1];for (int j = 0; j < neg + 1; j++) {dp[i][j] = dp[i - 1][j];if (j >= num) {dp[i][j] += dp[i - 1][j - num];}}}return dp[len][neg];}
}
总结
记数组的元素和为 sum,添加 - 号的元素之和为 neg,则其余添加 + 的元素之和为 sum−neg,得到的表达式的结果为:
(sum − neg) − neg = sum − 2 * neg = target 即 neg = (sum − target) / 2
由于数组 nums 中的元素都是非负整数,neg 也必须是非负整数,所以上式成立的前提是 sum − target 是非负偶数。若不符合该条件可直接返回 0。
若上式成立,问题转化成在数组 nums 中选取若干元素,使得这些元素之和等于 neg,计算选取元素的方案数。我们可以使用动态规划的方法求解。
定义二维数组 dp,其中 dp[i][j] 表示在数组 nums 的前 i 个数中选取元素,使得这些元素之和等于 j 的方案数。假设数组 nums 的长度为 n,则最终答案为 dp[n][neg]。
当没有任何元素可以选取时,元素和只能是 0,对应的方案数是 1,因此动态规划的边界条件是:
当j = 0时,dp[0][j] = 1;当j > 0时,dp[0][j] = 0;
当 1 ≤ i ≤ n 时,对于数组 nums 中的第 i 个元素 num(i 的计数从 1 开始),遍历 0 ≤ j ≤ neg,计算 dp[i][j] 的值:
如果 j < num,则不能选 num,此时有 dp[i][j] = dp[i − 1][j];
如果 j ≥ num,则如果不选 num,方案数是 dp[i−1][j],如果选 num,方案数是 dp[i − 1][j − num],此时有 dp[i][j]=dp[i − 1][j] + dp[i − 1][j − num]。
因此状态转移如下:
当j < nums[i]时,dp[i][j] = dp[i−1][j];当j >= nums[i]时, dp[i][j] = dp[i - 1][j] + dp[i − 1][j − nums[i]]。
最终得到 dp[n][neg] 的值即为答案。
相关文章:
【LeetCode】494.目标和
题目 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums [2, 1] ,可以在 2 之前添加 ,在 1 之前添加 - &#x…...
KaiwuDB 荣获哈佛商业评论 2023“高能韧性团队奖”
8月18日,《哈佛商业评论》中文版携手 FESCO 成功举办“第九届人才经济论坛”暨“2022-2023 高能团队奖颁奖典礼”。论坛秉承前沿的全球视野及权威的管理理念,发掘并展示本土企业组织管理的最佳实践,并重磅揭晓第二届“高能团队奖”评选结果。…...
删除ubuntu开始菜单中的图标
背景 本来是很好看干净的界面 更新谷歌浏览器后出现了Gmail,幻灯片,谷歌硬盘等跟谷歌相关的乱七八糟东西搞得界面就很丑 解决问题 删掉那个图标 输入命令 sudo nautilus /usr/share/applicationssudo nautilus ~/.local/share/applications可以…...
信息系统项目管理基础知识学习笔记 - IT 治理基础 - IT治理的驱动因素
信息系统项目管理基础知识学习笔记 - IT 治理基础 - IT治理的驱动因素 IT治理的驱动因素组织的IT战略驱动组织开展高质量IT治理因素IT治理的内涵IT 治理体系信息系统项目管理基础知识学习笔记 - IT 治理基础 - IT治理的驱动因素 IT治理的驱动因素 组织信息系统建设和运行需要…...
8月21-22日上课内容 第一章 MySQL数据库初始
本章结构 数据库的基本概念 概述(总览) 结构: 数据 表 数据库 数据库管理系统 数据库系统原理 数据 (Data) 描述事物的符号记录 包括数字,文字、图形、图像、声音、档案记录等以“记录”形式按统一的格式进行存储表 将不同…...
等级查询发布助手
考试成绩的发布是学校教学工作中的一项重要任务,传统的手工录入、统计和发布成绩的方式既耗时又容易出错。为了提高老师的工作效率和准确性,推荐老师们试一试易查分考试等级发布系统。 易查分是一个查询/发布发布平台 1. 快速高效:老师只需将…...
手搭手入门MyBatis-Plus
MyBatis-Plus Mybatis-Plus介绍 为简化开发而生 MyBatis-Plus(opens new window)(简称 MP)是一个 MyBatis(opens new window) 的增强工具,在 MyBatis 的基础上只做增强不做改变,为简化开发、提高效率而生。 特性 无侵入&#…...
AI 绘画Stable Diffusion 研究(十一)sd图生图功能详解-美女换装
免责声明: 本案例所用安装包免费提供,无任何盈利目的。 大家好,我是风雨无阻。 为了让大家更直观的了解图生图功能,明白图生图功能到底是干嘛的,能做什么事情?今天我们继续介绍图生图的实用案例-美女换装的制作。 对于…...
Servlet+JDBC实战开发书店项目讲解第14讲:订单管理功能
ServletJDBC实战开发书店项目讲解第14讲:订单管理功能 欢迎阅读本系列教程的第14讲!在本篇文章中,我们将深入讲解如何在书店项目中实现订单管理功能。通过这个实例,你将学习到如何使用Servlet和JDBC来处理后台管理的订单管理操作…...
基于Linux操作系统中的shell脚本
目录 前言 一、概述 1、什么是shell? 2、shell脚本的用途有哪些? 3、常见的shell有哪些? 4、学习shell应该从哪几个方面入手? 4.1、表达式 1)变量 2)运算符 4.2、语句 1)条件语句&am…...
8.22笔记
8.22笔记 8.22笔记一、Hive的HQL语法重点问题1.1 DDL1.1.1 Hive中数据表的分类问题1.1.2 特殊的数据类型 1.2 DML1.3 DQL1.3.1 查询语法和MySQL大部分都是一致的 1.4 讲了三个数据库的可视化工具1.4.1 navicat1.4.2 dbeaver1.4.3 chat2db 二、Hive中重点问题:Hive函…...
【以太网通信】RS232 串口转以太网
最近和 RK 研发同事在调试通信接口,排查与定位 RK3399 接收数据出错的问题。FPGA 与 RK3399 之间使用一路 RS232 串口进行通信,由于串口数据没有分包,不方便排查问题,想到可以开发一个 RS232 串口转以太网的工具,将串口…...
分享两道Java面试的算法上机题目(后续会持续补充更多)
所有题目参考答案均是小编自己想法,仅供参考,解法很多,大可不必局限,有更优解的大神无解,可评论或私聊博主指正! 题目1 找大串,给定一个字符串其中包含任意组连续字符,我们把超过3个…...
如何使用CSS实现一个平滑过渡效果?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 使用CSS实现平滑过渡效果⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚…...
网络常见设备
目录 1.网络常见设备 1.交换路由设备 2.网络安全设备 3.无线网络设备 4.网络设备生产厂商 1.网络常见设备 当用户通过电子邮件给远方的朋友送去祝福时,一定不会想到这封邮件在网络中将会经历怎样复杂的行程。就好比将一封真实的信件投到邮局后,无法了解…...
数据结构与算法:通往编程高地的必修课(文末送书)
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
python小脚本——批量将PDF文件转换成图片
语言:python 3 用法:选择PDF文件所在的目录,点击 确定 后,自动将该目录下的所有PDF转换成单个图片,图片名称为: pdf文件名.page_序号.jpg 如运行中报错,需要自行根据报错内容按照缺失的库 例如&#x…...
cUrl的介绍和基本使用
cURL 如果你在开发接口的时候,需要调试。那么cUrl将是你必备的技能。也许你用过postman,但这个未免太重量级了。curl将会是你最佳轻量级,调试接口的工具😀 1.Curl函数的基本选项✨ 1.1 --request和 -x —request 和 -X 指定与HTTP服务器通信…...
ONLYOFFICE协作空间服务器如何一键安装自托管私有化部署
ONLYOFFICE协作空间服务器如何一键安装自托管私有化部署 如何在 Ubuntu 上部署 ONLYOFFICE 协作空间社区版?https://blog.csdn.net/m0_68274698/article/details/132069372?ops_request_misc&request_id&biz_id102&utm_termonlyoffice%20%E5%8D%8F%E4…...
java分析公司名称:AI智能工具助力提取地名、品牌名、行业名
java分析公司名称:AI智能工具助力提取地名、品牌名、行业名 一、java智能提取地名 /*** 通过“武汉”补全省市区* throws Exception*/public void getPlace4() throws Exception{String r1 "武汉";String fileName2 "D:\\Personal\\Desktop\\txt…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
