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 <= 121 <= coins[i] <= 231 - 10 <= 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 ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬…...
2024 CSP-J 题解
2024 CSP-J题解 扑克牌 题目给出了一整套牌的定义,但是纯粹在扯淡,完全没有必要去判断给出的牌的花色和点数,我们用一个循环来依次读入每一张牌,如果这个牌在之前出现过,我们就让答案减一。这里建议用map、unorde…...
GPU 服务器厂家:中国加速计算服务器市场的前瞻洞察
科技的飞速发展,让 GPU 服务器在加速计算服务器领域的地位愈发凸显。中国加速计算服务器市场正展现出蓬勃的生机,而 GPU 服务器厂家则是这场科技盛宴中的关键角色。 从市场预测的趋势来看,2023 年起,中国加速计算服务器市场便已展…...
Hadoop集群修改yarn队列
1.修改默认的default队列参数 注意: 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功能时,GPIO引脚弄错了,P1写成P2,但还是配置成功,能得到电压数据。 首先一步步排查: 既然引脚弄错了,那引脚改为正确的引脚,能得到数据通过第一步判断,GPIO配置似乎是不起作…...
css-元素居中方式
<section class"wrapper"><div class"content">Content goes here</div> </section>1. 使用 Flexbox Flexbox 是一种现代的布局方法,可以轻松实现居中。 .wrapper {display: flex; /* 使用 Flexbox …...
redis内存打满了怎么办?
1、设置maxmemory的大小 我们需要给 Redis设置maxmemory的大小,如果不设置的话,它会受限于系统的物理内存和系统对内存的管理机制。 2、设置内存的淘汰策略 内存的淘汰策略分为 8 种,从淘汰范围来说分为从所有的key中淘汰和从设置过期时间…...
决策算法的技术分析
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言(1)第一层级:分层状态机、分层决策树的想法(三个臭皮匠胜过一个诸葛亮)基于场景的固定规则化的分层决策核心思想(2)第二层级:数据管理的方…...
【Python爬虫】获取汽车之家车型配置附代码(2024.10)
参考大哥,感谢大哥:https://blog.csdn.net/weixin_43498642/article/details/136896338 【任务目标】 工作需要想更方便地下载汽车之家某车系配置清单;(垃圾汽车之家不给下载导出表格,配置页叉掉了车系要出来还要重新…...
JVM 加载 class 文件的原理机制
JVM 加载 class 文件的原理机制 JVM(Java虚拟机)是一个可以执行Java字节码的虚拟机。它负责执行Java应用程序和应用程序的扩展,如Java库和框架。 文章目录 JVM 加载 class 文件的原理机制1. JVM1.1 类加载器1.2 魔数1.3 元空间 2. 类加载2.1 …...
NumPy学习第九课:字符串相关函数
前言 各位有没有注意到,NumPy从第八课开始其实基本上都是讲的是NumPy的函数,而且其实就是各种函数的调用,因为NumPy是一个很强大的函数库,这对我们以后再处理项目中遇到的问题时会有很大的帮助。我们将常用的函数进行一个列举&am…...
卷积神经网络(CNNs)在处理光谱特征的序列属性时表现不佳
卷积神经网络(CNNs)在处理光谱签名的序列属性时表现不佳,主要是由于其固有网络架构的局限性。具体原因如下: 局部感受野(Local Receptive Field): CNN 的核心操作是卷积,它利用局部感…...
【IC】MCU的Tick和晶振频率
Tick 是指 MCU 内部时钟的一个周期,通常表示为一个固定的时间间隔。每个 tick 代表一个时间单位,通常以毫秒(ms)或微秒(μs)为单位。Tick 通常由 MCU 的定时器或计时器生成,作为系统时钟的一部分…...
从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 启动流程
目录 写在前面 速通:做了什么: 分析I:分析2011年的startup文件所作 分析II:分析2017年的startup文件所作 Helps 2011 2017 Reference 写在前面 请各位看官看本篇笔记的时候首先了解一下计算机体系架构,了解基本…...
交换机:端口安全与访问控制指南
为了实现端口安全和访问控制,交换机通常通过以下几种机制和配置来保护网络,防止未经授权的访问和恶意攻击。 01-端口安全 定义及功能 端口安全功能允许管理员限制每个交换机端口可以学习的MAC地址数量。 通过绑定特定的MAC地址到交换机的某一端口上&a…...
【C++ | 数据结构】八大常用排序算法详解
1. 排序的稳定性 排序是我们生活中经常会面对的问题,小朋友站队的时候会按照从矮到高的顺序排列;老师查看上课出勤情况时,会按照学生的学号点名;高考录取时,会按照成绩总分降序依次录取等等。那么对于排序它是如何定义…...
Oracle 第7章:数据完整性约束
在Oracle数据库中,数据完整性是指确保存储在数据库中的数据的正确性和一致性。为了实现这一点,Oracle提供了多种机制来维护数据完整性,包括主键(Primary Key)、外键(Foreign Key)和唯一性约束&a…...
【核心】静态/动态全覆盖路径规划相关技术研究
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言一、明确覆盖式路径的目标二、静态/动态全覆盖路径规划相关技术研究(1)静态全覆盖路径规划方法一:波前WaveFront 覆盖算法方法二:图形学映射算…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版
1.题目描述 2.思路 当前的元素可以重复使用。 (1)确定回溯算法函数的参数和返回值(一般是void类型) (2)因为是用递归实现的,所以我们要确定终止条件 (3)单层搜索逻辑 二…...
leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
