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

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...