零钱兑换 - LeetCode 热题 85
大家好!我是曾续缘🤪
今天是《LeetCode 热题 100》系列
发车第 85 天
动态规划第 5 题
❤️点赞 👍 收藏 ⭐再看,养成习惯
零钱兑换 给你一个整数数组
coins,表示不同面额的硬币;以及一个整数amount,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回
-1。你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins =[1, 2, 5], amount =11输出:3解释:11 = 5 + 5 + 1示例 2:
输入:coins =[2], amount =3输出:-1示例 3:
输入:coins = [1], amount = 0 输出:0提示:
难度:💖💖
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
解题方法
我们可以使用动态规划来解决这个问题。首先创建一个长度为 amount + 1 的数组 dp,其中 dp[i] 表示凑齐金额 i 所需要的最少硬币个数。初始化将 dp 数组所有元素值设为 amount + 1,这个值相当于无穷大,用来表示不可能凑齐该金额。
然后,我们从金额 1 开始遍历到 amount,对于每个金额 i,再遍历硬币数组 coins 中的每个硬币面额 coins[j]。如果当前硬币面额 coins[j] 小于等于当前金额 i,则更新 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1),即当前金额 i 所需的最少硬币个数为当前值和减去当前硬币面额后的金额所需硬币个数加一的较小值。
最终返回 dp[amount],如果其值大于 amount,表示无法凑齐该金额,返回 -1;否则返回 dp[amount]。
Code
public class Solution {public int coinChange(int[] coins, int amount) {// 初始化最大值为 amount + 1int max = amount + 1;// 创建 dp 数组,记录凑齐各个金额所需的最少硬币个数int[] dp = new int[amount + 1];// 将 dp 数组所有元素值设为 maxArrays.fill(dp, max);// 初始金额为 0 时,所需硬币个数为 0dp[0] = 0;// 遍历金额从 1 到 amountfor (int i = 1; i <= amount; i++) {// 遍历硬币数组for (int j = 0; j < coins.length; j++) {// 如果当前硬币面额小于等于当前金额if (coins[j] <= i) {// 更新最少硬币个数dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}// 返回最终结果,若大于 amount 则无法凑齐,返回 -1,否则返回 dp[amount]return dp[amount] > amount ? -1 : dp[amount];}
}相关文章:
零钱兑换 - LeetCode 热题 85
大家好!我是曾续缘🤪 今天是《LeetCode 热题 100》系列 发车第 85 天 动态规划第 5 题 ❤️点赞 👍 收藏 ⭐再看,养成习惯 零钱兑换 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount &…...
基于web的垃圾分类回收系统的设计
管理员账户功能包括:系统首页,个人中心,管理员管理,用户管理,公告管理,运输管理,基础数据管理 用户账户功能包括:系统首页,个人中心,运输管理,公告…...
优化你的WordPress网站:内链建设与Link Whisper Pro插件的利用
文章目录 内链的重要性WordPress SEO插件:Link Whisper Pro主要功能使用指南下载与安装 结语 在数字营销和网站管理领域,SEO内部优化是提升网站排名、增加流量和提高用户参与度的核心策略。在众多SEO技巧中,内链建设是构建良好网站结构和提升…...
spring中那些地方使用了反射
1、依赖注入(Dependency Injection) Spring Boot通过反射机制将bean注入到相应的属性或构造函数中。当我们在Spring Boot中使用如Autowired这样的注解时,Spring容器会利用反射机制找到相应的bean并注入到对应的属性或构造函数中。 2、Bean的…...
1 机器人软件开发学习所需通用技术栈(一)
机器人软件工程师技术路线(如有缺失,欢迎补充) 1. 机器人软件开发工程师技术路线 1.1 基础知识 C/C编程:掌握C/C语言基础,包括数据结构、算法、内存管理等。操作系统:了解Linux或Windows等操作系统的基本…...
Java(十二)——Comparable接口与Comparator接口
文章目录 Comparable与Comparator接口Comparable接口Comparator接口 Comparable与Comparator接口 我们可能会遇到这样的问题:怎么对一个对象数组进行排序? 比如对一个狗类对象数组进行排序,而想到这,我们又会有一个问题ÿ…...
Nvidia Jetson/Orin +FPGA+AI大算力边缘计算盒子:轨道交通监控系统
株洲中车时代电气股份有限公司(下称中车时代电气)是中国中车旗下股份制企业,其前身及母公司——中车株洲电力机车研究所有限公司创立于1959年。中车时代电气扎根株洲,走好两条钢轨,走出两条钢轨。中车时代电气秉承“双…...
笔记 | 软件工程01:从程序到软件
1 软件工程知识域 2 程序 2.1 何为程序及程序的质量要求 何为程序: 理解:软件工程可能就是在弥补OOP语言与自然语言之间还存在的鸿沟 2.1.1 程序质量的内在和外在体现 2.1.2 程序质量的语法和语义体现 2.2 编写代码的基本原则 2.3 程序质量保证方法 …...
废品回收小程序开发,助力商家拓展回收市场
随着互联网的快速发展,废品回收行业也走向了数字化发展,废品回收小程序成为了拓展市场的重要方式。在当下万亿元下的回收市场中,废品回收小程序的发展也能够发挥重要作用,提高市场回收效率,提高大众的回收意识…...
JVM类加载机制和双亲委派
类加载机制 java文件需要编译成字节码文件(.class文件),jvm是通过类加载机制,将.class文件加载进内存,经过验证连接->初始化直到使用该对象的过程就是类加载机制,当new对象的时候,jvm首先去常量池寻找该类的符号引用…...
【PyCharm】无法创建虚拟环境,提示:has no attribute CPython3macOsBrew
报错信息: AttributeError: module virtualenv.create.via_global_ref.builtin.cpython.mac_os has no attribute CPython3macOsBrew报错原因: 可能含有多个virtualenv,发生冲突了。 解决方法: 终端执行以下命令: p…...
华为OD刷题C卷 - 每日刷题 12(数组连续和,求最多可以派出多少支团队)
1、(数组连续和): 这段代码是解决“数组连续和”的问题。它提供了一个Java类Main,其中包含main方法和getResult方法,用于计算给定数组中有多少个连续区间的和大于等于给定值x。 main方法首先读取数组的长度n和阈值x&…...
2.1 初识Windows程序
Windows程序设计是一种面向对象的编程。Windows操作系统以数据结构的形式定义了大量预定义的对象作为操作系统的数据类型。Windows动态链接库提供了各种各样的API接口函数供Windows应用程序调用。一个Windows应用程序是运行在Windows操作系统之上的。这些API接口函数的调用所实…...
EDI系统的使用场景
EDI全称Electronic Data Interchange,中文名称是电子数据交换。EDI系统是专为企业间的电子数据传输而设计的,需要满足的基本功能包括:支持AS2、OFTP、SFTP等EDI传输协议,能够生成和解析符合X12、EDIFACT、VDA等EDI报文标准下的报文…...
韩国Neowine推出第三代强加密芯片ALPU-CV
推出第三代加密芯片;是ALPU系列中的高端IC;是一款高性能车规级加密芯片;其加密性更强、低耗电、体积小;使得防复制、防抄袭板子的加密性能大大提升,该芯片通过《AEC-Q100》认证,目前已经在国产前装车辆配件…...
golang结构与接口方法实现与交互使用示例
1.定义结构 // 结构定义 type VideoFrame struct {id inthead []bytelen int64data []byte } 2.实现结构方法 // 生成结构字段的get与set方法 // func (v *VideoFrame) Id() int {return v.id }func (v *VideoFrame) SetId(id int) {v.id id }func (v *VideoFrame) He…...
C# 判断字符串不等于空的示例
在C#中,要判断一个字符串是否不等于空(即它既不是null也不是空字符串""),方法有如下几种,如下。 方法1 使用逻辑运算符和string.IsNullOrEmpty方法 string myString "123"; // 假设要检查的字…...
直方图中最大的矩形
#include<iostream> #include<algorithm> using namespace std; const int N 100010; //l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界 int h[N], q[N], l[N], r[N]; typedef long long LL; int main() { int n; while(scanf("%d"…...
分布式锁redisson
1:pom.xml添加依赖 <dependency><groupId>org.redisson</groupId><artifactId>redisson-spring-boot-starter</artifactId><version>3.21.1</version> </dependency>2-1:方法一:读取默认ym…...
将小爱音箱接入 ChatGPT 和豆包ai改造成专属语音助手
这个GitHub项目,mi-gpt,旨在将小爱音箱和米家设备与ChatGPT和豆包集成,有效地将这些设备转变为个性化语音助手。以下是对其功能和设置的详细分析: 主要特点 角色扮演:该项目允许小爱适应不同的角色,如伴侣…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
