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 目标和
本题链接:. - 力扣(LeetCode) 题目: 思路: 根据这道题,可以通过暴力的方法进行取 号或者 - 号 两个操作,通过当刚好得到 target 的时候 答案 1,但是通过长度是 20 ,操…...
详解 docker 镜像制作的两种方式
概要 制作Docker镜像一般有2种方法: 通过Dockerfile,完成镜像的创建使用仓库中已有的镜像,安装自己使用的软件环境后完成新镜像创建 docker 常用命令 docker build: 用于构建 Docker 镜像。该命令可以从 Dockerfile 构建镜像,…...
selenium元素单击不稳定解决方法
selenium自动化测试过程中,经常会发现某一元素单击,很不稳定,有时候执行了点击没有反映。 以下总结两种解决方法:都是通过js注入的方式去点击。 1.F12查一看,要点击的按钮,或连接,有没有οncl…...
vue3中vite使用sass
引用: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开发分布式光纤油气管道泄漏检测及预警系统 随着油气工业的发展,管道泄漏成为一个严峻的安全问题。本文介绍了一种基于LabVIEW的分布式光纤油气管道泄漏检测及预警系统的设计思路和组成结构。系统包括硬件和软件两部分,其中硬件部分详细阐述了分…...

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,版本是C00,也就是V12.0.0。...

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

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

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

性能测试浅谈
早期的性能测试更关注后端服务的处理能力。 一个用户去访问一个页面的请求过程,如上图。 数据传输时间 当你从浏览器输入网址,敲下回车,开始... 真实的用户场景请不要忽视数据传输时间,想想你给远方的朋友写信,信件需…...
媒体运营常用的ChatGPT通用提示词模板
媒体平台选择:如何选择合适的媒体平台,确保内容的有效传播? 内容策划与创作:如何策划和创作高质量的内容,吸引和留住目标受众? 内容发布与推广:如何有效地发布和推广内容,提高内容…...
Java学习苦旅(二十一)——泛型
本篇博客将详细讲解Java中的泛型。 文章目录 泛型的定义语法示例 泛型类语法示例类型边界语法示例 类型擦除通配符语法示例上界语法示例 下界语法示例 裸类型泛型方法语法示例 泛型的限制结尾 泛型的定义 语法 class 泛型类名称<类型形参列表> {//这里可以使用类型参数…...
具备闭环思维的测试才更充分
测试工作的终极目标是为了保障产品的质量。如果用同一个维度衡量测试人员的业务水平,简单粗暴一些:那就是针对同一款产品,哪个测试人员发现的bug多,哪个测试人员的测试理论与实践水平相对来说还是高一些。 前两天组长在群里分析了…...
flask web学习之模板(一)
文章目录 一、模板基本用法1.1 定界符1.2 模板语法1.3 渲染模板 二、模板辅助工具2.1 上下文2.2 全局对象2.3 过滤器2.4 测试器2.5 模板环境对象 在动态web程序中,视图函数返回的HTML数据往往需要根据相应的变量(比如查询参数)动态生成。当HT…...

RedisInsight - Redis官方可视化工具
一、RedisInsight 简介 RedisInsight 是一个直观高效的 Redis GUI 管理工具,它可以对 Redis 的内存、连接数、命中率以及正常运行时间进行监控,并且可以在界面上使用 CLI 和连接的 Redis 进行交互(RedisInsight 内置对 Redis 模块支持&#…...
Matlab定义函数计算斐波那契数列
以下是使用 MATLAB 定义函数计算并输出斐波那契数列前 200 个数的示例代码: 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层模型? 什么是TCP/IP 四层模型? 为什么网络要分层? 应用层有哪些常见的协议? 传输层有哪些常见的协议? 网络层有哪些常见的协议? 从输入…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用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集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

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

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)
Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...