Leetcode 322. 零钱兑换(完全背包)
- Leetcode 322. 零钱兑换(完全背包)
- 题目
- 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
- 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
- 你可以认为每种硬币的数量是无限的。
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
- 解法
- 动态规划之完全背包:
- 定义一维数组 dp,其中 dp[i] 表示组成总金额 i 所需的最少硬币数
- 初始化 dp 数组,dp[0] 为 0,表示组成金额 0 需要 0 个硬币,dp[1…amount] 初始化为极大值,表示当前无法组成该总金额
- 遍历硬币数组 coins,对于每种面额的硬币,遍历总金额范围内可以添加该硬币的金额下标。即 dp[j] 不为极大值,说明可以组成 j + coins[i] 金额,此时转移方程为:dp[j + coins[i]] = Math.min(dp[j + coins[i]], dp[j] + 1)
- 遍历结束后,dp[amount] 如果仍为极大值,则无法组成,返回 -1;否则返回 dp[amount] 表示最少需要的硬币数
- PS:由于 amount 最多由 amount 个硬币组成,因此初始化极大值只要大于 amount 就可以
- 代码
/*** 动态规划之完全背包:* 定义一维数组 dp,其中 dp[i] 表示组成总金额 i 所需的最少硬币数* 初始化 dp 数组,dp[0] 为 0,表示组成金额 0 需要 0 个硬币,dp[1...amount] 初始化为极大值,表示当前无法组成该总金额* 遍历硬币数组 coins,对于每种面额的硬币,遍历总金额范围内可以添加该硬币的金额下标。即 dp[j] 不为极大值,说明可以组成 j + coins[i] 金额,此时转移方程为:dp[j + coins[i]] = Math.min(dp[j + coins[i]], dp[j] + 1)* 遍历结束后,dp[amount] 如果仍为极大值,则无法组成,返回 -1;否则返回 dp[amount] 表示最少需要的硬币数* PS:由于 amount 最多由 amount 个硬币组成,因此初始化极大值只要大于 amount 就可以*/private static int solution(int[] coins, int amount) {// 判空if (amount == 0) {return 0;}if (coins == null || coins.length <= 0) {return -1;}// 定义且初始化 dp 数组int[] dp = new int[amount + 1];Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);// 循环添加每一种硬币int coinsLen = coins.length;int dpLen = dp.length;for (int i = 0; i < coinsLen; i++) {for (int j = 0; j < dpLen - coins[i]; j++) {if (dp[j] < Integer.MAX_VALUE) {dp[j + coins[i]] = Math.min(dp[j + coins[i]], dp[j] + 1);}}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
相关文章:
Leetcode 322. 零钱兑换(完全背包)
Leetcode 322. 零钱兑换(完全背包)题目 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&…...
怎么恢复回收站?分享4个宝藏方法!
案例:怎么恢复回收站 【请问大家怎么恢复误删的文件呀?如果回收站被清空了,又应该怎么恢复呢?】 电脑回收站是我们存储被删除文件的地方。但是有时候,我们会不小心把一些重要的文件或者照片误删了。这时候࿰…...
大模型混战,最先实现“智慧涌现”的会是谁?
作者 | 曾响铃 文 | 响铃说 几秒钟写出了一篇欢迎词; 小说人物乱入现实,快速创作不重样的故事; 鼠标一点,一封英文工作沟通邮件撰写完成; 准确解出数学应用题,还给出解题步骤; 甚至还能理…...
Powerlink协议在嵌入式linux上的移植和主从站通信(电脑和linux板通信实验)
使用最新的openPOWERLINK 2.7.2源码,业余时间搞定了Powerlink协议在嵌入式linux上的移植和测试,并进行了下电脑和linux开发板之间的通信实验。添加了一个节点配置,跑通了源码中提供的主站和从站的两个demo。这里总结下移植过程分享给有需要的…...
快速理解基本的cookie、session 和 redis
一、Cookie 1、什么是Cookie 1、Cookie实际上是一小段的文本信息,是一种keyvalue形式的字符串。客户端请求服务器,如果服务器需要记录该用户状态,就使用response向客户端浏览器颁发一个Cookie。客户端会把Cookie保存起来。 2、当浏览器再请求…...
STANet代码复现出现的问题
1 IndexError: boolean index did not match indexed array along dimension 0; dimension is 4194304 but corresponding boolean dimension is 65536定位到导致错误的代码,是metric.py,Collect values for Confusion Matrix 收集混淆矩阵的值时出错 …...
Java 中String对象详解
Java语言中的String对象是一个非常常见的数据类型,大多数情况下我们都是在使用String对象来表示字符串类型的数据。Java中的String类是一个final class,它是不可被继承的。本文将对Java中的String对象进行详细全面的描述,包括以下几个方面&am…...
k8s nfs运行问题、etcd问题、calico网络问题
服务器重启后nfs运行问题导致服务不能正常重启 解决办法 在每个节点下使用如下命令进行查看nfs是否正常启动 systemctl status nfs 如果没有启动,则使用如下命令启动,保证三个节点下的nfs都正常启动 systemctl start nfs 再次查看nfs是否正常启动 syst…...
Qt--QString字符串类、QTimer定时器类
目录 1. QString 字符串类 dialog.cpp 2. 容器类 2.1 顺序容器 QList 示例代码: student.h student.cpp dialog.h dialog.cpp 运行结果: 2.2 关联容器 QMap 示例代码: dialog.h dialog.cpp 运行结果: 3. Qt类型 3.1 跨平台数据类型…...
2023.5.13>>Eclipse+exe4j打包Java项目及获取exe所在文件的路径
Eclipseexe4j打包Java项目及获取exe所在文件的路径 1、打包exe文件1.1 打jar包1.2 打包exe2、在程序中获取exe所在路径3、遇到问题4、JDK version和class file version(Class编译版本号)对应关系5、参考文章 1、打包exe文件 1.1 打jar包 右单击项目选择“Export…” 1.2…...
Centos系统的使用基本教程
Centos是一款流行的Linux操作系统,它基于Red Hat Enterprise Linux系统,是一款稳定、可靠、安全的操作系统。本文将介绍Centos系统的基本使用方法,包括安装、命令行操作、软件安装和系统管理等方面的内容。 安装Centos系统 Centos系统可以从…...
IDEA生成ER图、UML类图、时序图、流程图等的插件推荐或独立工具推荐
以下是几个常用的IDEA插件和独立工具,可以用于生成ER图、UML类图、时序图、流程图等: Visual Paradigm (独立工具) Visual Paradigm是一个强大的建模工具,可以生成UML类图、时序图、流程图等。它支持多种语言和框架,包括Java、Spr…...
Python心经(3)
这一节总结点demo和常用知识点 目录 有关字符串格式化打印的 lambda匿名函数,,将匿名函数作为参数传入 文件读写 生成器 python的装饰器 简单的网站代码: 有关三元运算 推导式: 新浪面试题: 有关面向对象里…...
单工,半双工,全双工通讯
对于点对点之间的通信,按照消息传送的方向与时间关系,通信方式可分为单工通信、半双工通信及全双工通信三种。 单工通信 单工通信(Simplex Communication)是指消息只能单方向传输的工作方式。 在单工通信中,通信的信…...
【2023-05-09】 设计模式(单例,工厂)
2023-05-09 设计模式(单例,工厂) 单例模式 顾名思义,就是整个系统对外提供的实例有且只有一个 特点: 1、单例类只有一个实例 2、必须是自己创建唯一实例 3、必须给所以对象提供这个实例 分类ÿ…...
批量任务导致页面卡死解决方案
需求背景 需要基于高德地图展示海量点位(大概几万个),点位样式要自定义(创建DOM),虽然使用了聚合点,但初始化时仍需要将几万个点位的DOM结构都创建出来。 这里补充一句,高德地图在2.…...
避免“文献综抄”,5种写作结构助你完成文献综述→
很多作者可能有过这样的体验:读了很多文献,但在写综述的时候总感觉不像是在写文献综述,更像在写文献总结 如果引用方面不注意,甚至会成为文献综抄。 那么,你可以参考下我们整理的以下资料哦~ 01 文献总结和文献综述的…...
Java异常和反射
JAVA 异常分类及处理 概念 } final Entry<K,V> getEntryUsingComparator(Object key) { K k (K) key; // 获取该 TreeMap 的 comparator Comparator<? super K> cpr comparator; if (cpr ! null) { // 从根节点开始 Entry<K,V> p …...
Accesss数据库的那点事
Accesss数据库的那点事 1.Access的简介 Access(全称为Microsoft Access)是一个关系型数据库管理系统(RDBMS)。它是由微软公司开发的数据库软件,用于创建、管理和操作数据库应用程序。 Access提供了一个可视化的开发环…...
网络基础学习:osi网络七层模型
osi网络七层模型 什么是OSI,什么是ISO?为什么ISO要提出OSI网络七层模型?OSI七层的划分以及具体内容第七层 应用层第六层 表示层第五层 会话层第四层 传输层第三层 网络层第二层 数据链路层第一层 物理层 每一层与设备的对应关系 什么是OSI,什…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
