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 四层模型? 为什么网络要分层? 应用层有哪些常见的协议? 传输层有哪些常见的协议? 网络层有哪些常见的协议? 从输入…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 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"…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...