当前位置: 首页 > 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 覆盖算法方法二:图形学映射算…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...