当前位置: 首页 > news >正文

Leetcode 102.目标和

给定一个正整数数组 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 <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

思路:

看到数字的范围,以及状态状态是可以从上一层转移的,所以考虑动态规划
当然也可以使用dfs(思路会更简单一些)

状态表示:
f[i][j]表示前i个数字,总和为k的方案数量
这里每个数字都是必须选的

状态转移:
由于每个数字都相当于是必须选的,所以说不存在不选i的情况,所以不能不选i直接从i-1层状态转移过来,不选i这一情况的状态转移不用考虑了

状态转移方程:

                    if(k-nums[i]+m>=0)f[i][k+m]+=f[i-1][k-nums[i]+m];if(k+nums[i]+m<=2*m)f[i][k+m]+=f[i-1][k+nums[i]+m];

注意初始化的时候应该+=1,因为为第一个数为0的时候直接赋值为1会丢失一种情况

代码:

class Solution {
public:int f[21][2100];int findTargetSumWays(vector<int>& nums, int target) {int n=nums.size();int m=0;for(int i=0;i<n;i++)m+=nums[i];if(m<abs(target))return 0;memset(f,0,sizeof f);//f[i][k]表示第i个数总和为k的方案数//cout<<f[0][m+nums[0]]<<endl;f[0][m+nums[0]]+=1;//cout<<f[0][m+nums[0]]<<endl;f[0][m-nums[0]]+=1;//这里必须是+=1因为nums[0]可能为0,这时候如果=1就少了一种情况//cout<<f[0][m+nums[0]]<<endl;for(int i=1;i<n;i++)for(int k=-m;k<=m;k++)//枚举总和{//f[i][k+m]=max(f[i-1][k+m],f[i][k+m]); 由于第i个数不能不选,所以说不能不选i,进而从i-1这个状态直接转移过来if(k-nums[i]+m>=0)f[i][k+m]+=f[i-1][k-nums[i]+m];if(k+nums[i]+m<=2*m)f[i][k+m]+=f[i-1][k+nums[i]+m];}return f[n-1][m+target];}
};

运行结果:

在这里插入图片描述

相关文章:

Leetcode 102.目标和

给定一个正整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘’ 或 ‘-’ &#xff0c;然后串联起所有整数&#xff0c;可以构造一个 表达式 &#xff1a; 例如&#xff0c;nums [2, 1] &#xff0c;可以在 2 之前添加 ‘’ &#xff0c;在 1 之前添加 ‘-’ &…...

LLM AI工具和Delphi名称的起源

LLM AI工具和Delphi名称的起源 使用ChatGPT&#xff0c;直接或通过微软工具&#xff0c;以及其他基于llm的引擎。我很欣赏他们提供好的总结和比较的能力&#xff0c;并且还编写了一些样板代码。与此同时&#xff0c;当你问一些重要的问题时&#xff0c;你会得到一些令人惊讶的好…...

打破数据分析壁垒:SPSS复习必备(十一)

一、方差分析 方差分析的应用条件如下&#xff1a; &#xff08;1&#xff09;独立&#xff0c;各组数据相互独立&#xff0c;互不相关&#xff1b; &#xff08;2&#xff09;正态&#xff1a;即各组数据符合正态分布&#xff1b; &#xff08;3&#xff09;方差齐性&…...

【十六】【QT开发应用】Menu菜单,contextMenuEvent,setContextMenuPolicy,addAction

在 Qt 框架中&#xff0c;QMenu 类用于创建和管理菜单。菜单是用户界面的一部分&#xff0c;可以包含多个选项或动作&#xff0c;用户可以选择这些选项来执行特定的功能。菜单通常显示在菜单栏、上下文菜单&#xff08;右键菜单&#xff09;或工具栏中。 基本用法 创建菜单对象…...

华为DCN技术:M-LAG

M-LAG&#xff08;Multichassis Link Aggregation Group&#xff09;即跨设备链路聚合组&#xff0c;是一种实现跨设备链路聚合的机制。M-LAG主要应用于普通以太网络、VXLAN和IP网络的双归接入&#xff0c;可以起到负载分担或备份保护的作用。相较于另一种常见的可靠性接入技术…...

k8s持久化之emptyDir使用

目录 概述实践代码 概述 理解emptyDir使用&#xff0c;是后续k8s持久化进阶&#xff0c;高阶使用的基础。 实践 代码 详细说明在代码中 # 缓存数据&#xff0c;可以让多个容器共享数据 # 删除 Pod 时&#xff0c;emptyDir 数据同步消失 # 定义 initContainer -> 下载数据…...

Java露营基地预约小程序预约下单系统源码

轻松开启户外探险之旅 &#x1f31f; 露营热潮来袭&#xff0c;你准备好了吗&#xff1f; 随着人们对户外生活的热爱日益增加&#xff0c;露营已成为许多人周末和假期的首选活动。但你是否曾因找不到合适的露营基地而烦恼&#xff1f;或是因为繁琐的预约流程而错失心仪的营地…...

七天速通javaSE:第四天 java方法

文章目录 前言一、什么是方法&#xff1f;二、方法的定义与调用1. 方法的定义2. 方法的调用3. 练习&#xff1a;定义比大小方法并调用 三、方法的重载四、递归五、可变参数拓展&#xff1a;命令行传递参数 前言 本章将学习java方法。 一、什么是方法&#xff1f; java方法是用…...

jupyter notebook的markdown语法不起作用

在这个界面编辑&#xff0c;发现markdown你编辑的是什么就是什么&#xff0c;不起作用&#xff0c;然而点一下&#xff1a; 右上角“Notebook转发”&#xff0c;就会单独跳出一个jupyter notebook的界面&#xff0c;此时就会奏效&#xff1a;...

Redis 学习笔记(2)

目录 1 Redis的持久化1.1 RDB持久化方案1.2 AOF持久化方案 2 Redis架构2.1 主从复制架构2.2 哨兵集群设计2.3 哨兵集群设计 3 Redis事务机制4 Redis过期策略与内存淘汰机制4.1 过期策略4.2 内存淘汰机制 5 Redis高频面试题4.1 缓存穿透4.2 缓存击穿4.3 缓存雪崩 1 Redis的持久化…...

快慢指针:删除有序数组中的重复项

题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 思路好想&#xff0c;代码实现不好想 class Solution {public int removeDuplicates(int[] nums) {int fast 1,slow 1;while(fast < nums.length){if(nums[fast] ! nums[fast-1]){nums[slow] nums[fast]…...

用户登录错误次数太多锁定账号

当用户登录验证码错误次数太多时&#xff0c;需要限制用户在10分钟之内不能再次登录。 限制方案&#xff1a; 1.通过Redis ZSet key可以设置为用户名&#xff0c;value可以设置为UUID&#xff0c;score设置为当前时间戳 每次用户登录时&#xff0c;通过 rangeByScore 查询对…...

tedsign vue3 web-端框架中封装一个验证码组件 以及对应node 接口逻辑说明

一个这样的组件 我直接上代码了 <template><t-loading size"small" :loading"loading" show-overlay><div class"container" click"refresh"><div v-if"svg" class"svg" v-html"svg&…...

探索Scala并发编程之巅:高效并行处理的艺术

标题&#xff1a;探索Scala并发编程之巅&#xff1a;高效并行处理的艺术 引言 在现代软件开发中&#xff0c;随着多核处理器的普及&#xff0c;编写能够充分利用硬件能力的并发程序变得至关重要。Scala&#xff0c;这门结合了面向对象和函数式编程特性的语言&#xff0c;提供…...

AudioLM: 音频生成的革命性模型

AudioLM: 音频生成的革命性模型 AudioLM是一种革命性的音频生成模型&#xff0c;它结合了深度学习和自然语言处理的先进技术&#xff0c;能够生成高质量、逼真的音频内容。本文将探讨AudioLM的基本原理、工作机制、应用场景以及对音频生成领域的影响和未来发展方向。 一、Aud…...

C++ Vector的模拟实现

vector的介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可以动态改变的&#xff0c;而…...

Kubernetes之Controller详解

本文尝试从Kubernetes Controller的种类、交互逻辑、最佳实践、伪代码示例及历史演进5个方面对其进行详细阐述&#xff0c;希望对您有所帮助&#xff01; 一、Kubernetes Controller种类 Kubernetes Controller Manager 是 Kubernetes 集群的核心组件之一&#xff0c;负责管理…...

openlayers性能优化——开启图层预加载、减少空白等待时间

使用切片图层时、地图拖拽会有空白图片&#xff0c;为了减少空白等待时间&#xff0c;我们可以开始图层预加载。 const map_top new Map({layers: [new TileLayer({preload:Infinity, //预加载source: new StadiaMaps({layer: "outdoors",}),}),],target: "ma…...

BlockingQueue详解(含动画演示)

目录 BlockingQueue详解0、BlockingQueue简介BlockingQueue接口中方法注释BlockingQueue的实现&#xff0c;总结计划 1、ArrayBlockingQueue简介2、ArrayBlockingQueue的继承体系3、ArrayBlockingQueue的构造方法①、 ArrayBlockingQueue(int capacity)②、ArrayBlockingQueue(…...

wordpress商用付费主题与免费主题的区别

WordPress免费主题与WordPress付费主题&#xff0c;都可以用&#xff0c;但存在非常大的差别。从直观的感受&#xff0c;简单地说就是&#xff0c;WordPress免费主题能用&#xff0c;WordPress付费主题好用。如果涉及到其它的方面&#xff0c;WordPress商用付费主题与免费主题之…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...