当前位置: 首页 > 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商用付费主题与免费主题之…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...