leetcode 494. 目标和

2023.8.14

        一杯茶,一包烟,一道dp做一天...

        ps:nums[i]均大于等于0。本题先转化为0-1背包问题:将数组元素分成两堆:一堆为正号,另一堆为负号。设正号堆的和为x,则负号堆的和为sum-x。(sum为数组元素总和)。               于是:x-(sum-x) =target ,可以推出 x = (target+sum)/2 。x必须为偶数,为奇数直接返回0。

        于是此时背包的大小相当于x,物品为数组nums。 dp[i]的含义为:装满大小为 i 的背包的 方法种数。  具体代码如下:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
        {
            sum += nums[i];
        }
        if((sum + target) % 2 == 1) return 0;
        int capacity = (sum + target)/2;
        if(capacity < 0) return 0;
        vector<int> dp(capacity + 1);
        dp[0] = 1;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=capacity; j>=nums[i]; j--)
            {
                //第一项是不使用nums[i]时装满背包的方法种数,第二项是使用nums[i]时装满背包的方法种数。
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[capacity];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/73279.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python系统学习1-7-字典

一、字典 1、概念及内存图 列表&#xff1a;由一系列变量组成的可变序列容器字典&#xff1a;由一系列键值对组成的可变散列容器字典优势&#xff1a;利用&#xff08;内存&#xff09;空间&#xff0c;换取&#xff08;CPU查找&#xff09;时间 键key 必须唯一且为不…

登录验证码实现

Hutool代码改造 Hutool 有参考文档&#xff1b;很多工具类&#xff1b;把一些功能都封装好&#xff1b;都不用你自己去写&#xff1b;直接调用它的工具类 它这里会详细告诉你引入方式Hutool <dependency><groupId>cn.hutool</groupId><artifactId>hu…

陪诊小程序开发|陪诊陪护小程序让看病不再难

陪诊小程序通过与医疗机构的合作&#xff0c;整合了医疗资源&#xff0c;让用户能够更加方便地获得专业医疗服务。用户不再需要面对繁琐的挂号排队&#xff0c;只需通过小程序预约服务&#xff0c;便能够享受到合适的医疗资源。这使得用户的就医过程变得简单高效&#xff0c;并…

分布式应用:Zabbix监控Tomcat

目录 一、理论 1.Zabbix监控Tomcat 二、实验 1.Zabbix监控Tomcat 三、问题 1.获取软件包失败 2.tomcat 配置 JMX remote monitor不生效 3.Zabbix客户端日志报错 一、理论 1.Zabbix监控Tomcat &#xff08;1&#xff09;环境 zabbix服务端&#xff1a;192.168.204.214 …

<Vite>HMR实现原理

什么是HMR&#xff1f; HMR&#xff08;Hot Module Replacement&#xff09;是一种开发工具&#xff0c;也就是热更新。用于在应用程序运行时替换、添加或删除模块&#xff0c;而无需完全重新加载整个页面或重新启动应用程序。这可以极大地提高开发效率和调试体验。 HMR的优势 …

【uniapp】微信小程序,取视频第一帧,前提是 图片是在 阿里云的oss上

上传视频等&#xff0c;默认为黑色&#xff0c;无法用视频的第一帧作为封面&#xff0c;以及视频的video为原生组件&#xff0c;层级很高无法覆盖问题&#xff0c;虽然有cover-view&#xff0c;但很多场景还是不灵活 实现的前提条件是 图片是在 阿里云的oss上 自己服务器是…

在线Word怎么转换成PDF?Word无法转换成PDF文档原因分析

不同的文件格式使用方法是不一样的&#xff0c;而且也需要使用不同的工具才可以打开编辑内容&#xff0c;针对不同的场合用户们难免会用到各种各样的文件格式&#xff0c;要想在不修改内容的前提下提高工作效率&#xff0c;那就需要用到文件格式转换&#xff0c;那么在线Word怎…

Springboot 实践(1)MyEclipse2019创建maven工程

项目讲解步骤&#xff0c;基于本机已经正确安装Java 1.8.0及MyEclipse2019的基础之上&#xff0c;Java及MyEclipse的安装&#xff0c;请参考其他相关文档&#xff0c;Springboot 实践文稿不再赘述。项目创建讲解马上开始。 一、首先打开MyEclipse2019&#xff0c;进入工作空间选…

bash: make: command not found

make之后报错信息如下&#xff1a;cd 对应的文件路径后 make 发现报错&#xff1a;bash: make: command not found 这个原因可能是没有安装make工具,也可能是安装了make之后,没有将make的文件路径添加到系统环境变量中 有没有安装make,可以使用Search Everything搜索是否有make…

【实战项目】c++实现基于reactor的高并发服务器

基于Reactor的高并发服务器&#xff0c;分为反应堆模型&#xff0c;多线程&#xff0c;I/O模型&#xff0c;服务器&#xff0c;Http请求和响应五部分 ​全局 反应堆模型 Channel 描述了文件描述符以及读写事件&#xff0c;以及对应的读写销毁回调函数&#xff0c;对应存储ar…

最强自动化测试框架Playwright(18)- 执行js脚本

page.evaluate&#xff08;&#xff09; API 可以在网页上下文中运行 JavaScript 函数&#xff0c;并将结果带回 Playwright 环境。 href page.evaluate(() > document.location.href) 如果结果是 Promise 或函数是异步的&#xff0c;则计算将自动等待&#xff0c;直到解析…

IDEA如何调试Stream API

Stream API现在在实际开发中应用非常广泛&#xff0c;经常会遇到需要调试Stream API的场景&#xff0c;这篇文章主要讲解如何使用IDEA调试Stream Testpublic void test(){Stream.of(10, 20, 30, 40, 50).mapToInt(e->e*10).filter(e->e>200).forEach(System.out::pri…

第八章 CUDA内存应用与性能优化篇(上篇)

cuda教程目录 第一章 指针篇 第二章 CUDA原理篇 第三章 CUDA编译器环境配置篇 第四章 kernel函数基础篇 第五章 kernel索引(index)篇 第六章 kenel矩阵计算实战篇 第七章 kenel实战强化篇 第八章 CUDA内存应用与性能优化篇 第九章 CUDA原子(atomic)实战篇 第十章 CUDA流(strea…

0基础学C#笔记09:希尔排序法

文章目录 前言一、希尔排序的思想二、使用步骤总结 前言 希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序&#xff0c;如果数组的最大值刚好是在第一位&#xff0c;要将它挪到正确的位置就需要 n - 1 次移动。也就是说&#xff0c;原数组的一个元素如果距离它…

优维低代码实践:自定义模板

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…

此文详解,数据仓库管理建设的经验

目前由于数据分散在不同的存储环境或数据库中&#xff0c;对于新业务需求的开发需要人工先从不同的数据库中同步、集中、合并等处理&#xff0c;造成资源和人力的浪费。同时&#xff0c;目前的系统架构&#xff0c;无法为未来数据驱动业务创新的理念提供友好的支撑。需要建设新…

如何构建一个 NodeJS 影院微服务并使用 Docker 部署

文章目录 前言什么是微服务&#xff1f;构建电影目录微服务构建微服务从 NodeJS 连接到 MongoDB 数据库总结 前言 如何构建一个 NodeJS 影院微服务并使用 Docker 部署。在这个系列中&#xff0c;将构建一个 NodeJS 微服务&#xff0c;并使用 Docker Swarm 集群进行部署。 以下…

d3dcompiler43.dll缺失怎么修复?dll缺失解决方法分享

在使用电脑过程中&#xff0c;我们有时会遇到一些系统文件的问题&#xff0c;其中一个常见的问题是d3dcompiler43.dll文件的损坏或丢失。当这个文件出现问题时&#xff0c;可能会导致应用程序无法正常运行或图形渲染出现异常。最近我也遇到了这个问题&#xff0c;以下是我修复d…

安达发APS|生产计划排产软件助力加工制造业智能化转型

随着全球经济一体化的不断深入&#xff0c;市场竞争日益激烈&#xff0c;加工制造企业面临着巨大的生存压力。在这种情况下&#xff0c;企业对于生产计划的精细化管理需求日益迫切。为了适应这一市场需求&#xff0c;安达发推出了专门针对加工企业的APS生产计划排产软件&#x…

机器学习实战5-KMeans聚类算法

文章目录 概述KMeansKMeans参数&接口n_clusters质心inertia模型评估指标轮廓系数Calinski-Harabaz Index 重要参数init & random_state & n_init&#xff1a;初始质心怎么放好?重要参数max_iter & tol&#xff1a;让迭代停下来重要属性与重要接口 概述 聚类 …