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 四层模型? 为什么网络要分层? 应用层有哪些常见的协议? 传输层有哪些常见的协议? 网络层有哪些常见的协议? 从输入…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
