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

dp专题10 目标和

本题链接:. - 力扣(LeetCode)

题目:

思路:

        根据这道题,可以通过暴力的方法进行取 + 号或者 - 号 两个操作,通过当刚好得到 target 的时候 答案 +1,但是通过长度是 20 ,操作状态为 2个,随后的回溯暴力递归,最坏的情况时间复杂度大约是 20^20^2 ,肯定会TLE了。

        这时候就用到了动态规划dp,这里我们可以知道有两个操作 +  -,我们分成两个子集,一些放正号子集 left,另一些放负号子集 righ。

最后得到 :  left + righ = sum                 其中 sum 为整个 nums 数组的总和

然后将两个子集合并:   left - righ = target    

根据这两个式子我们可以推导出              left = (sum + target) / 2

这时候我们又可以将其看作为 背包问题了,根据题目意思要求的是能够凑成 target的方法有多少种,相当于背包问题中能够刚好装满给背包容量的方案数是多少一样的。

只是这里需要计算背包容量   v 为  left 

代码详解如下:

inline int findTargetSumWays(vector<int>& nums, int target) 
{int sum = 0;	// 计算 nums 数组的总和for(int &i:nums) sum += i;// 分成两个子集,   一个是正号的子集 left , 一个是 负号的子集 righ// left + righ = sum// left - righ = target// left = (sum + target) / 2// 令 left 作为 背包容量,问刚好凑够 left 的子集有多少种方法// 其中 当 (sum + target) 不能被 2 整除 或者 当全部为 +号 或者 -号 的sum   小于 target,说明根本凑不齐int v = (sum + target) / 2;if(v * 2 != (sum + target) || abs(target) > sum) return 0;// dp[i] 中 i 含义为 : 装满 容量 i        dp[i] 含义为 装满 容量 i 的方法有多少种   int n = nums.size();vector<int>dp(n + 1000,0);/* 递推公式:  dp[i - num[i]] = dp[i] 即: 有  dp[target - num[i]]种方法 凑成 dp[target]  假设 num[i] = i  target = 5即:    1   dp[4] 种方法凑成 dp[5]									2   dp[3] 种方法凑成 dp[5]3   dp[2] 种方法凑成 dp[5]4   dp[1] 种方法凑成 dp[5]5   dp[0] 种方法凑成 dp[5]最后 dp[5] 中方法总共有: dp[0] + dp[1] + dp[2] + dp[3] + dp[4]最后公式为   dp[i] += dp[i - nums[i]]*/// dp 初始化, 0 凑成 0 的方法只有一种dp[0] = 1;for(int i = 0;i < n;++i){for(int j = v;j >= nums[i];--j){dp[j] += dp[j - nums[i]];}}return dp[v];
}

最后提交:

相关文章:

dp专题10 目标和

本题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 思路&#xff1a; 根据这道题&#xff0c;可以通过暴力的方法进行取 号或者 - 号 两个操作&#xff0c;通过当刚好得到 target 的时候 答案 1&#xff0c;但是通过长度是 20 &#xff0c;操…...

详解 docker 镜像制作的两种方式

概要 制作Docker镜像一般有2种方法&#xff1a; 通过Dockerfile&#xff0c;完成镜像的创建使用仓库中已有的镜像&#xff0c;安装自己使用的软件环境后完成新镜像创建 docker 常用命令 docker build: 用于构建 Docker 镜像。该命令可以从 Dockerfile 构建镜像&#xff0c;…...

selenium元素单击不稳定解决方法

selenium自动化测试过程中&#xff0c;经常会发现某一元素单击&#xff0c;很不稳定&#xff0c;有时候执行了点击没有反映。 以下总结两种解决方法&#xff1a;都是通过js注入的方式去点击。 1.F12查一看&#xff0c;要点击的按钮&#xff0c;或连接&#xff0c;有没有οncl…...

vue3中vite使用sass

引用&#xff1a;https://blog.csdn.net/weiliang_66/article/details/132469597 npm install sass -d配置vite.config.js: css: {preprocessorOptions: {scss: {additionalData:import "/assets/styles/main.scss";}}}创建对应的 main.sass...

centos 8.0 安装sysbench 1.0.17

序号步骤说明执行命令执行结果备注1 下载并解压sysbench-1.0.17.zip sysbench-1.0.17.zip2安装依赖文件 yum install automake libtool -y yum install /usr/include/libpq-fe.h 3安装sysbench cd sysbench-1.0.17 ./autogen.sh ./configure \ --prefix/sysbench \ --with-pgsq…...

LabVIEW开发分布式光纤油气管道泄漏检测及预警系统

LabVIEW开发分布式光纤油气管道泄漏检测及预警系统 随着油气工业的发展&#xff0c;管道泄漏成为一个严峻的安全问题。本文介绍了一种基于LabVIEW的分布式光纤油气管道泄漏检测及预警系统的设计思路和组成结构。系统包括硬件和软件两部分&#xff0c;其中硬件部分详细阐述了分…...

Go后端开发 -- Go Modules

Go后端开发 – Go Modules 文章目录 Go后端开发 -- Go Modules一、什么是Go Modules?二、GOPATH的工作模式1.GOPATH模式2.GOPATH模式的弊端 三、Go Modules模式创建项目1.go mod命令2.go mod环境变量3.使用Go Modules初始化项目4.修改模块的版本依赖关系 四、Go Modules下impo…...

基于det_keypoint_unite的ROS功能包(jetson部署)

文章目录 硬件软件FastDeploy编译CMakeLists.txt头文件源代码硬件 Jetson AGX Orin 64GB 软件 gcc/g++ >= 5.4(推荐8.2)cmake >= 3.10.0jetpack >= 4.6.1opencv=4.2.0FastDeploy编译 git clone https://github.com/PaddlePaddle/FastDeploy.git cd FastDeploy mkdi…...

TS 36.211 V12.0.0-下行(8)-调制和上变频

本文的内容主要涉及TS 36.211&#xff0c;版本是C00&#xff0c;也就是V12.0.0。...

基于SSM酒店后台管理系统【源码】【最详细运行文档】

基于SSM酒店后台管理系统【源码】【最详细运行文档】 功能简介技术描述运行准备♝项目运行访问项目 演示图✅源码获取 &#x1f4a1; 「分享」 大家好&#xff0c;最近几年在酒店后台管理系统非常流行&#xff0c;无论是上课的项目或者是一些毕设都会以酒店后台管理系统举例说…...

利用Python实现每日新闻早报推送

本文将介绍如何使用Python编写简单的逻辑&#xff0c;通过调用API接口实现每日新闻推送功能。 步骤&#xff1a; 导入所需的库&#xff1a; 在代码的开头&#xff0c;我们需要导入所需的库。通常&#xff0c;我们会使用requests库来发送HTTP请求&#xff0c;以获取新闻数据。 …...

图像分割-Grabcut法

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 本文的C#版本请访问&#xff1a;图像分割-Grabcut法(C#)-CSDN博客 GrabCut是一种基于图像分割的技术&#xff0c;它可以用于将图像…...

性能测试浅谈

早期的性能测试更关注后端服务的处理能力。 一个用户去访问一个页面的请求过程&#xff0c;如上图。 数据传输时间 当你从浏览器输入网址&#xff0c;敲下回车&#xff0c;开始... 真实的用户场景请不要忽视数据传输时间&#xff0c;想想你给远方的朋友写信&#xff0c;信件需…...

媒体运营常用的ChatGPT通用提示词模板

媒体平台选择&#xff1a;如何选择合适的媒体平台&#xff0c;确保内容的有效传播&#xff1f; 内容策划与创作&#xff1a;如何策划和创作高质量的内容&#xff0c;吸引和留住目标受众&#xff1f; 内容发布与推广&#xff1a;如何有效地发布和推广内容&#xff0c;提高内容…...

Java学习苦旅(二十一)——泛型

本篇博客将详细讲解Java中的泛型。 文章目录 泛型的定义语法示例 泛型类语法示例类型边界语法示例 类型擦除通配符语法示例上界语法示例 下界语法示例 裸类型泛型方法语法示例 泛型的限制结尾 泛型的定义 语法 class 泛型类名称<类型形参列表> {//这里可以使用类型参数…...

具备闭环思维的测试才更充分

测试工作的终极目标是为了保障产品的质量。如果用同一个维度衡量测试人员的业务水平&#xff0c;简单粗暴一些&#xff1a;那就是针对同一款产品&#xff0c;哪个测试人员发现的bug多&#xff0c;哪个测试人员的测试理论与实践水平相对来说还是高一些。 前两天组长在群里分析了…...

flask web学习之模板(一)

文章目录 一、模板基本用法1.1 定界符1.2 模板语法1.3 渲染模板 二、模板辅助工具2.1 上下文2.2 全局对象2.3 过滤器2.4 测试器2.5 模板环境对象 在动态web程序中&#xff0c;视图函数返回的HTML数据往往需要根据相应的变量&#xff08;比如查询参数&#xff09;动态生成。当HT…...

RedisInsight - Redis官方可视化工具

一、RedisInsight 简介 RedisInsight 是一个直观高效的 Redis GUI 管理工具&#xff0c;它可以对 Redis 的内存、连接数、命中率以及正常运行时间进行监控&#xff0c;并且可以在界面上使用 CLI 和连接的 Redis 进行交互&#xff08;RedisInsight 内置对 Redis 模块支持&#…...

Matlab定义函数计算斐波那契数列

以下是使用 MATLAB 定义函数计算并输出斐波那契数列前 200 个数的示例代码&#xff1a; function result fibonacci(n)if n < 1 || n > 200result NaN;elseif n 1 || n 2result 1;elseresult fibonacci(n-1) fibonacci(n-2);end endn 200; result fibonacci(n)…...

计算机网络面试题总结

总结自Network | JavaGuide(Java面试 学习指南) 什么是OSI7层模型&#xff1f; 什么是TCP/IP 四层模型&#xff1f; 为什么网络要分层&#xff1f; 应用层有哪些常见的协议&#xff1f; 传输层有哪些常见的协议&#xff1f; 网络层有哪些常见的协议&#xff1f; 从输入…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...