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

leetcode动态规划(十八)-零钱兑换II

题目

322.零钱兑换II

给你一个整数数组 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] <= 231 - 1
  • 0 <= amount <= 104

思路

1.确定dp数组以及下标的含义

dp[j]:凑足总额为j所需钱币的最少个数为dp[j]

2.确定递推公式

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;

其他下标对应的数值呢?

考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

所以下标非0的元素都是应该是最大值。

4.确定遍历顺序

本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数

所以本题并不强调集合是组合还是排列。

综上所述,遍历顺序为:coins(物品)放在外循环,target(背包)在内循环。且内循环正序。

5.举例推导dp数组

以输入:coins = [1, 2, 5], amount = 5为例

代码

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)dp =[float('inf')]*(amount+1)dp[0] = 0for i in range(n):for j in range(coins[i],amount+1):if dp[j- coins[i]] != float('inf'):dp[j] = min(dp[j-coins[i]]+1,dp[j])if dp[amount] == float('inf'):return -1return dp[amount]

相关文章:

leetcode动态规划(十八)-零钱兑换II

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

2024 CSP-J 题解

2024 CSP-J题解 扑克牌 ​ 题目给出了一整套牌的定义&#xff0c;但是纯粹在扯淡&#xff0c;完全没有必要去判断给出的牌的花色和点数&#xff0c;我们用一个循环来依次读入每一张牌&#xff0c;如果这个牌在之前出现过&#xff0c;我们就让答案减一。这里建议用map、unorde…...

GPU 服务器厂家:中国加速计算服务器市场的前瞻洞察

科技的飞速发展&#xff0c;让 GPU 服务器在加速计算服务器领域的地位愈发凸显。中国加速计算服务器市场正展现出蓬勃的生机&#xff0c;而 GPU 服务器厂家则是这场科技盛宴中的关键角色。 从市场预测的趋势来看&#xff0c;2023 年起&#xff0c;中国加速计算服务器市场便已展…...

Hadoop集群修改yarn队列

1.修改默认的default队列参数 注意&#xff1a; yarn.scheduler.capacity.root.队列名.capacity总和不能超过100 <property><name>yarn.scheduler.capacity.root.queues</name><value>default,hive,spark,flink</value><description>The…...

【GPIO】2.ADC配置错误,还是能得到电压数据

配置ADC功能时&#xff0c;GPIO引脚弄错了&#xff0c;P1写成P2&#xff0c;但还是配置成功&#xff0c;能得到电压数据。 首先一步步排查&#xff1a; 既然引脚弄错了&#xff0c;那引脚改为正确的引脚&#xff0c;能得到数据通过第一步判断&#xff0c;GPIO配置似乎是不起作…...

css-元素居中方式

<section class"wrapper"><div class"content">Content goes here</div> </section>1. 使用 Flexbox Flexbox 是一种现代的布局方法&#xff0c;可以轻松实现居中。 .wrapper {display: flex; /* 使用 Flexbox …...

redis内存打满了怎么办?

1、设置maxmemory的大小 我们需要给 Redis设置maxmemory的大小&#xff0c;如果不设置的话&#xff0c;它会受限于系统的物理内存和系统对内存的管理机制。 2、设置内存的淘汰策略 内存的淘汰策略分为 8 种&#xff0c;从淘汰范围来说分为从所有的key中淘汰和从设置过期时间…...

决策算法的技术分析

系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言(1)第一层级:分层状态机、分层决策树的想法(三个臭皮匠胜过一个诸葛亮)基于场景的固定规则化的分层决策核心思想(2)第二层级:数据管理的方…...

【Python爬虫】获取汽车之家车型配置附代码(2024.10)

参考大哥&#xff0c;感谢大哥&#xff1a;https://blog.csdn.net/weixin_43498642/article/details/136896338 【任务目标】 工作需要想更方便地下载汽车之家某车系配置清单&#xff1b;&#xff08;垃圾汽车之家不给下载导出表格&#xff0c;配置页叉掉了车系要出来还要重新…...

JVM 加载 class 文件的原理机制

JVM 加载 class 文件的原理机制 JVM&#xff08;Java虚拟机&#xff09;是一个可以执行Java字节码的虚拟机。它负责执行Java应用程序和应用程序的扩展&#xff0c;如Java库和框架。 文章目录 JVM 加载 class 文件的原理机制1. JVM1.1 类加载器1.2 魔数1.3 元空间 2. 类加载2.1 …...

NumPy学习第九课:字符串相关函数

前言 各位有没有注意到&#xff0c;NumPy从第八课开始其实基本上都是讲的是NumPy的函数&#xff0c;而且其实就是各种函数的调用&#xff0c;因为NumPy是一个很强大的函数库&#xff0c;这对我们以后再处理项目中遇到的问题时会有很大的帮助。我们将常用的函数进行一个列举&am…...

卷积神经网络(CNNs)在处理光谱特征的序列属性时表现不佳

卷积神经网络&#xff08;CNNs&#xff09;在处理光谱签名的序列属性时表现不佳&#xff0c;主要是由于其固有网络架构的局限性。具体原因如下&#xff1a; 局部感受野&#xff08;Local Receptive Field&#xff09;&#xff1a; CNN 的核心操作是卷积&#xff0c;它利用局部感…...

【IC】MCU的Tick和晶振频率

Tick 是指 MCU 内部时钟的一个周期&#xff0c;通常表示为一个固定的时间间隔。每个 tick 代表一个时间单位&#xff0c;通常以毫秒&#xff08;ms&#xff09;或微秒&#xff08;μs&#xff09;为单位。Tick 通常由 MCU 的定时器或计时器生成&#xff0c;作为系统时钟的一部分…...

从0到1学习node.js(npm)

文章目录 一、NPM的生产环境与开发环境二、全局安装三、npm安装指定版本的包四、删除包 五、用npm发布一个包六、修改和删除npm包1、修改2、删除 一、NPM的生产环境与开发环境 类型命令补充生产依赖npm i -S uniq-S 等效于 --save -S是默认选项npm i -save uniq包的信息保存在…...

【STM32 Blue Pill编程实例】-OLED显示DS18B20传感器数据

OLED显示DS18B20传感器数据 文章目录 OLED显示DS18B20传感器数据1、DS18B20介绍2、硬件准备及接线3、模块配置3.1 定时器配置3.2 DS18B20传感器配置3.3 OLED的I2C接口配置4、代码实现在本文中,我们将介绍如何将 DS18B20 温度传感器与 STM32 Blue Pill 开发板连接,并使用 HAL …...

STM32 从0开始系统学习3 启动流程

目录 写在前面 速通&#xff1a;做了什么&#xff1a; 分析I&#xff1a;分析2011年的startup文件所作 分析II&#xff1a;分析2017年的startup文件所作 Helps 2011 2017 Reference 写在前面 请各位看官看本篇笔记的时候首先了解一下计算机体系架构&#xff0c;了解基本…...

交换机:端口安全与访问控制指南

为了实现端口安全和访问控制&#xff0c;交换机通常通过以下几种机制和配置来保护网络&#xff0c;防止未经授权的访问和恶意攻击。 01-端口安全 定义及功能 端口安全功能允许管理员限制每个交换机端口可以学习的MAC地址数量。 通过绑定特定的MAC地址到交换机的某一端口上&a…...

【C++ | 数据结构】八大常用排序算法详解

1. 排序的稳定性 排序是我们生活中经常会面对的问题&#xff0c;小朋友站队的时候会按照从矮到高的顺序排列&#xff1b;老师查看上课出勤情况时&#xff0c;会按照学生的学号点名&#xff1b;高考录取时&#xff0c;会按照成绩总分降序依次录取等等。那么对于排序它是如何定义…...

Oracle 第7章:数据完整性约束

在Oracle数据库中&#xff0c;数据完整性是指确保存储在数据库中的数据的正确性和一致性。为了实现这一点&#xff0c;Oracle提供了多种机制来维护数据完整性&#xff0c;包括主键&#xff08;Primary Key&#xff09;、外键&#xff08;Foreign Key&#xff09;和唯一性约束&a…...

【核心】静态/动态全覆盖路径规划相关技术研究

系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言一、明确覆盖式路径的目标二、静态/动态全覆盖路径规划相关技术研究(1)静态全覆盖路径规划方法一:波前WaveFront 覆盖算法方法二:图形学映射算…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...