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

【LeetCode】322.零钱兑换

题目

给你一个整数数组 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 <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

解答

源代码

public class Solution {public int coinChange(int[] coins, int amount) {int max = amount + 1;int[] dp = new int[amount + 1];Arrays.fill(dp, max);dp[0] = 0;for (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);}}}return dp[amount] > amount ? -1 : dp[amount];}
}

总结

知道了要dp也总是不知道该怎么dp哎……

dp[i]表示金额 i 需要的最少硬币数,这时寻找硬币中比 i 小的硬币, i 减去这个硬币的金额数,对应金额数的dp再加上1就等于dp[i],比较出最小的dp[i]。

相关文章:

【LeetCode】322.零钱兑换

题目 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。 你可以认为每种硬币的数量是无限的…...

中电金信:国际结算系统的“王冠”,为什么十年都戴在“它”的头上

2001年&#xff0c;中国正式加入WTO&#xff0c;在此后的二十多年里&#xff0c;中国出口席卷全球&#xff0c;迅速成长为一个贸易大国。 作为跨国贸易不可或缺的一环&#xff0c;无论是商品交易、服务提供、资金分配还是国际借贷等&#xff0c;都需要通过银行办理的外汇收支业…...

java 企业工程管理系统软件源码+Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis em

​ 鸿鹄工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离构建工程项目管理系统 1. 项目背景 一、随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大。为了提高工程管理效率、减轻劳动强度、提高信息处理速度和准确性&#xff0c;公司对内…...

fine-tuning(微调)的理解

fine-tuning 介绍 什么情况下使用微调 微调指导事项 不同数据集下使用微调 涉及到的其他知识 学习率&#xff08;learning-rate&#xff09; 卷积神经网络的核心 迁移学习与微调 什么是迁移学习 为什么要迁移学习 详细解释 自己的理解&#xff08;不知道对不对&#xff09; 介绍…...

深入理解设计模式面经

1 讲讲工厂方法模式&#xff0c; 1.1 给我一个java的demo 工厂方法模式是一种创建型设计模式&#xff0c;它提供了一个接口用于创建对象&#xff0c;但允许子类修改将要创建的对象类型。这种模式抽象了对象的创建过程&#xff0c;使得代码可以在不知道创建的对象具体类的情况…...

STM32单片机蓝牙APP宠物自动喂食器定时语音提醒喂食系统设计

实践制作DIY- GC00162---蓝牙APP宠物自动喂食器 一、功能说明&#xff1a; 基于STM32单片机设计---蓝牙APP宠物自动喂食器 二、功能说明&#xff1a; STM32F103C系列最小系统板LCD1602显示器DS1302时钟模块5个按键语音播报模块ULN2003步进电机模块LED灯板HC-05蓝牙模块&#x…...

武汉凯迪正大—串联谐振在电力系统中应用的优点:

变频串联谐振耐压试验装置在电力系统中应用的优点 1、所需电源容量大大减小。串联谐振电源是利用谐振电抗器和被试品电容谐振产生高电压和大电流的&#xff0c;在整个系统中&#xff0c;电源只需要提供系统中有功消耗的部分&#xff0c;因此&#xff0c;试验所需的电源功率只有…...

Git仓库、分支的区别

https://blog.csdn.net/weixin_30315905/article/details/94954617 git 仓库、分支的区别 首先&#xff0c;要明白仓库的概念 仓库可以理解为repository&#xff0c; 就是存放代码的地方&#xff0c;—— 其实是一个比较笼统的概念&#xff0c;不管里面的内容&#xff0c;总之…...

C#生成随机验证码

以下是一个简单的C#验证码示例&#xff1a; private void GenerateCaptcha() {// 生成随机字符串string chars "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";Random random new Random();string captchaString new string(Enumerable.Repe…...

如何使用C++来找出编码88表示的字符?指出至少两种方法。

在C中&#xff0c;可以使用整型值来表示字符编码&#xff0c;其中ASCII码是最常见的字符编码方案。要找出编码为88的字符&#xff0c;可以使用以下两种方法&#xff1a; 方法一&#xff1a;使用类型转换&#xff08;显式类型转换或隐式类型转换&#xff09;将整型值转换为字符…...

Kafka:springboot集成kafka收发消息

kafka环境搭建参考Kafka&#xff1a;安装和配置_moreCalm的博客-CSDN博客 1、springboot中引入kafka依赖 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><…...

本质矩阵E、基本矩阵F、单应矩阵H

1. E (归一化坐标对进行计算) t ^ R 为3*3的矩阵, 因为R,t共有6个自由度&#xff0c;又因为单目尺度等价性&#xff0c;所以实际上E矩阵共有5个自由度。因此至少需要5个点对来求解。 2. 基本矩阵F:根据两帧间匹配的像素点对儿计算 3*3且自由度为7的矩阵kF也为基础矩阵&#x…...

Oracle database Linux自建环境备份至远端服务器自定义保留天数

环境准备 linux下安装oracle 请看 oracle12c单节点部署 系统版本: CentOS 7 软件版本&#xff1a; Oracle12c 备份策略与实现方法 此次备份依赖Oracle自带命令exp与linux下crontab命令&#xff08;定时任务&#xff09; exp Oracle中exp命令是一个用于导出数据库数据和对象的…...

SpringBoot异步任务(2)|(线程池使用)

SpringBoot异步任务&#xff08;2&#xff09;|&#xff08;线程池使用&#xff09; 文章目录 SpringBoot异步任务&#xff08;2&#xff09;|&#xff08;线程池使用&#xff09;[TOC] 前言一、使用场景二、springboot添加异步任务1.配置线程池2.线程池的使用 总结 章节 第一章…...

解决Windows:Call to undefined function exif_imagetype()

很明显,是php安装时没有打开某些扩展,以致不能执行exif_imagetype()这个方法,因此需要打开。 网上很多人说需要打开下面这两个扩展: extension=php_exif.dll extension=php_mbstring.dll 但只说对了一半,我一开始也按照网上文章说的打开这两个扩展,但是还是同样错误。…...

【Spring】Spring AOP 初识及实现原理解析

博主简介&#xff1a;想进大厂的打工人博主主页&#xff1a;xyk:所属专栏: JavaEE进阶 目录 文章目录 一、初识AOP 1.1 什么是AOP&#xff1f; 1.2 AOP的组成 1.2.1 切面&#xff08;Aspect&#xff09; 1.2.2 切点&#xff08;Pointcut&#xff09; 1.2.3 连接点&…...

【Express.js】集成Redis

集成Redis 本节我们介绍在 express.js 中集成 redis. Redis是一个高性能的key-value内存数据库&#xff0c;支持事务、队列、持久化等特性&#xff0c;常用于高并发性能场景。 准备工作 创建一个 express.js 项目&#xff08;本文基于evp-express-cli&#xff09;在开发环境…...

StringBuilder创建的对象如何清空

要清空一个StringBuilder对象&#xff0c;可以使用其实例方法setLength(int newLength)来实现。将newLength参数设置为0&#xff0c;就可以将StringBuilder的内容清空。以下是一个示例代码&#xff1a; StringBuilder sb new StringBuilder(); // 添加一些内容到StringBuilde…...

mybatis-plus实现mysql自定义IKeyGenerator

1. IKeyGenerator主键生成 内置实现类&#xff0c;缺少mysql&#xff0c;因为mysql不支持序列&#xff0c;只能通过表模拟序列 H2KeyGenerator PostgreKeyGenerator KingbaseKeyGenerator 人大金仓的KES数据库 DB2KeyGenerator OracleKeyGenerator2. 新建表模拟序列 CREATE T…...

山西电力市场日前价格预测【2023-08-11】

日前价格预测 预测明日&#xff08;2023-08-11&#xff09;山西电力市场全天平均日前电价为367.15元/MWh。其中&#xff0c;最高日前电价为408.91元/MWh&#xff0c;预计出现在20: 00。最低日前电价为343.90元/MWh&#xff0c;预计出现在02: 30。 价差方向预测 1&#xff1a; 实…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

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

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

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

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

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...