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

LeetCode322:零钱兑换

题目链接:322. 零钱兑换 - 力扣(LeetCode)

代码如下

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){if(dp[j - coins[i]] != INT_MAX)  //这个也就是之前的都被初始化完毕,才能往后进行{dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if(dp[amount] == INT_MAX)   return -1;  //这个就是硬币书凑不出amount了,所以dp[amount]只能为INT_MAXreturn dp[amount];}
};

这个题目其实也就是相当于我们写前面那个零钱组合一样,但是之前的那个零钱组合是相求出组合数有多少个,而这个是找出能够组合的钱币然后输出最小的组成数,很明显,这个题目所说的amount也就是我们所要的背包容量,我们接下来第一步先确定dp[j]的含义,dp[j]也就是我们的背包最小容量,dp递推公式是dp[j] = min(dp[j], dp[j - coins[i] + 1])这里为什么是+1而不是加coins[i], 因为题目给的是,要求出的硬币数量,而不是要求出能装的背包大小,for循环里面的有一个判断条件,也就是if(dp[j - coins[i]] != INT_MAX),这个是为什么呢,因为我们需要找到当前dp数组是被初始化的,然后我们才能进行下一步赋值,如果这个数组没有被初始化了,也就是不满足这个背包问题了。

相关文章:

LeetCode322:零钱兑换

题目链接&#xff1a;322. 零钱兑换 - 力扣&#xff08;LeetCode&#xff09; 代码如下 class Solution { public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount 1, INT_MAX);dp[0] 0;for(int i 0; i < coins.size(); i){fo…...

速盾:高防 cdn 提供 cc 防护?

在当今网络环境中&#xff0c;网站面临着各种安全威胁&#xff0c;其中 CC&#xff08;Challenge Collapsar&#xff09;攻击是一种常见的分布式拒绝服务攻击方式。高防 CDN&#xff08;Content Delivery Network&#xff0c;内容分发网络&#xff09;作为一种有效的网络安全防…...

【大数据应用开发】2023年全国职业院校技能大赛赛题第10套

如有需要备赛资料和远程培训,可私博主,详细了解 目录 任务A:大数据平台搭建(容器环境)(15分) 任务B:离线数据处理(25分) 任务C:数据挖掘(10分) 任务D:数据采集与实时计算(20分) 任务E:数据可视化(15分) 任务F:综合分析(10分) 任务A:大数据平台搭…...

【源码部署】解决SpringBoot无法加载yml文件配置,总是使用8080端口方案

打开idea&#xff0c;file ->Project Structure 找到Modules &#xff0c;在右侧找到resource目录&#xff0c;是否指定了resource&#xff0c;点击对应文件夹会有提示...

2010年国赛高教杯数学建模B题上海世博会影响力的定量评估解题全过程文档及程序

2010年国赛高教杯数学建模 B题 上海世博会影响力的定量评估 2010年上海世博会是首次在中国举办的世界博览会。从1851年伦敦的“万国工业博览会”开始&#xff0c;世博会正日益成为各国人民交流历史文化、展示科技成果、体现合作精神、展望未来发展等的重要舞台。请你们选择感兴…...

使用nginx配置静态页面展示

文章目录 前言正文安装nginx配置 前言 目前有一系列html文件&#xff0c;比如sphinx通过make html输出的文件&#xff0c;需要通过ip远程访问&#xff0c;这就需要ngnix 主要内容参考&#xff1a;https://blog.csdn.net/qq_32460819/article/details/121131062 主要针对在do…...

[IOI2018] werewolf 狼人(Kruskal重构树 + 主席树)

https://www.luogu.com.cn/problem/P4899 首先&#xff0c;我们肯定要建两棵Kruskal重构树的&#xff0c;然后判两棵子树是否有相同编号节点 这是个经典问题&#xff0c;我们首先可以拍成dfs序&#xff0c;然后映射过去&#xff0c;然后相当于是判断一个区间是否有 [ l , r …...

snmpgetnext使用说明

1.snmpgetnext介绍 snmpgetnext命令是用来获取下一个节点的OID的值。 2.snmpgetnext安装 1.snmpgetnext安装 命令: yum -y install net-snmp net-snmp-utils [root@logstash ~]# yum -y install net-snmp net-snmp-utils Loaded plugins: fastestmirror Loading mirror …...

frameworks 之 触摸事件窗口查找

frameworks 之 触摸事件窗口查找 1. 初始化数据2. 查找窗口3. 分屏处理4. 检查对应的权限5.是否需要将事件传递给壁纸界面6. 成功处理 触摸流程中最重要的流程之一就是查找需要传递输入事件的窗口&#xff0c;并将触摸事件传递下去。 涉及到的类如下 frameworks/native/service…...

memset的用法

memset 是 C 语言标准库中的一个函数&#xff0c;用于将一块内存区域设置为特定的值。它的原型如下&#xff1a; c void *memset(void *s, int c, size_t n); - s 参数是要被填充的内存块的起始地址。 - c 参数是要填充的值。这个值会被转换为无符号字符&#xff0c;然后用来…...

阿里云国际站DDoS高防增值服务怎么样?

利用国外服务器建站的话&#xff0c;选择就具有多样性了&#xff0c;相较于我们常见的阿里云和腾讯云&#xff0c;国外的大厂商还有谷歌云&#xff0c;微软云&#xff0c;亚马逊云等&#xff0c;但是较之这些&#xff0c;同等产品进行比较的话&#xff0c;阿里云可以说当之无愧…...

open-cd中的changerformer网络结构分析

open-cd 目录 open-cd1.安装2.源码结构分析主干网络1.1 主干网络类2.neck2.Decoder3.测试模型6. changer主干网络 总结 该开源库基于&#xff1a; mmcv mmseg mmdet mmengine 1.安装 在安装过程中遇到的问题&#xff1a; 1.pytorch版本问题&#xff0c;open-cd采用的mmcv版本比…...

太速科技-426-基于XC7Z100+TMS320C6678的图像处理板卡

基于XC7Z100TMS320C6678的图像处理板卡 一、板卡概述 板卡基于独立的结构&#xff0c;实现ZYNQ XC7Z100DSP TMS320C6678的多路图像输入输出接口的综合图像处理&#xff0c;包含1路Camera link输入输出、1路HD-SDI输入输出、1路复合视频输入输出、2路光纤等视频接口&#xff0c;…...

asp.net Core 自定义中间件

内联中间件 中间件转移到类中 推荐中间件通过IApplicationBuilder 公开中间件 使用扩展方法 调用中间件 含有依赖项的 》》》中间件 参考资料...

掌握 C# 设计模式:从基础到依赖注入

设计模式是一种可以在开发中重复使用的解决方案&#xff0c;能够提高代码的可维护性、扩展性和复用性。C# 中常见的设计模式包括单例模式、工厂模式、观察者模式、策略模式等。本文将介绍这些常见的设计模式&#xff0c;并探讨 SOLID 原则和依赖注入&#xff08;Dependency Inj…...

根据json转HttpClient脚本

String json “{\n” " “paths”: {\n" " “/dev-api/system/subjectResult/exportUserList”: {\n" " “post”: {\n" " “tags”: [\n" " “bd-subject-result-controller”\n" " ],\n" " “summ…...

如何将LiDAR坐标系下的3D点投影到相机2D图像上

将激光雷达点云投影到相机图像上做数据层的前融合&#xff0c;或者把激光雷达坐标系下标注的物体点云的3d bbox投影到相机图像上画出来&#xff0c;都需要做点云3D点坐标到图像像素坐标的转换计算&#xff0c;也就是LiDAR 3D坐标转像素坐标。 看了网上一些文章都存在有错误或者…...

JAVA就业笔记6——第二阶段(3)

课程须知 A类知识&#xff1a;工作和面试常用&#xff0c;代码必须要手敲&#xff0c;需要掌握。 B类知识&#xff1a;面试会问道&#xff0c;工作不常用&#xff0c;代码不需要手敲&#xff0c;理解能正确表达即可。 C类知识&#xff1a;工作和面试不常用&#xff0c;代码不…...

02.04、分割链表

02.04、[中等] 分割链表 1、题目描述 给你一个链表的头节点 head 和一个特定值 x &#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 2、解题思路 本题要求将链表分隔…...

Excel 中根据患者的就诊时间标记病例为“初诊”或“复诊”

1. 假设&#xff1a; 患者表&#xff1a;包含患者的基本信息&#xff0c;如患者 ID 和患者姓名。 病例表&#xff1a;包含病例信息&#xff0c;如患者 ID、就诊时间和就诊状态。 2. 操作步骤&#xff1a; 合并数据&#xff1a; 确保病例表中有一列包含患者 ID&#xff0c;以…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...