当前位置: 首页 > 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 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...