当前位置: 首页 > 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;以…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

Linux操作系统共享Windows操作系统的文件

目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项&#xff0c;设置文件夹共享为总是启用&#xff0c;点击添加&#xff0c;可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download&#xff08;这是我共享的文件夹&#xff09;&…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...