Leetcode:322. 零钱兑换(C++)
目录
问题描述:
实现代码与解析:
动态规划(完全背包):
原理思路:
问题描述:
给你一个整数数组 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
实现代码与解析:
动态规划(完全背包):
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){if (dp[j - coins[i]] != INT_MAX){dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};
原理思路:
此题和Leetcode:474. 一和零(C++)_Cosmoshhhyyy的博客-CSDN博客很像,但是区别呢,就是此题求的是最小物品数,dp数组的含义就是装满背包用的最少硬币个数,对于dp数组的初始化,就是非零下标都取最大INT_MAX,因为我们后面要 dp[j] = min(dp[j], dp[j - coins[i]] + 1) 进行比较,如果都取 0 ,那么取 min 的时候就都取 0 了,显然是不对的,初始化为最大才能取到小值,当然 0 下标还是为 0 的,之后就是完全背包遍历了,最后如果dp数组还为初值,说明不能装满,则返回 -1。
相关文章:
Leetcode:322. 零钱兑换(C++)
目录 问题描述: 实现代码与解析: 动态规划(完全背包): 原理思路: 问题描述: 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金…...

C经典小游戏之扫雷
编译环境:VS022 目录 1.算法思路 2.代码模块 2.1 game.h 2.2 game.cpp 2.3 test.cpp 3.重点分析 4.金句省身 1.算法思路 主要采用二维数组进行实现,设置两个二维数组,一个打印结果,即为游戏界面显示的效果,一个用…...

第十节 使用设备树插件实现RGB 灯驱动
Linux4.4 以后引入了动态设备树(Dynamic DeviceTree),我们这里翻译为“设备树插件”。设备树插件可以理解为主设备树的“补丁”它动态的加载到系统中,并被内核识别。例如我们要在系统中增加RGB 驱动,那么我们可以针对R…...
【LeetCode】公交路线 [H](宽度优先遍历)
815. 公交路线 - 力扣(LeetCode) 一、题目 给你一个数组 routes ,表示一系列公交线路,其中每个 routes[i] 表示一条公交线路,第 i 辆公交车将会在上面循环行驶。 例如,路线 routes[0] [1, 5, 7] 表示第 …...

报表生成器 FastReport .Net 用户指南 2023(十):Band的属性
FastReport .Net是一款全功能的Windows Forms、ASP.NET和MVC报表分析解决方案,使用FastReport .NET可以创建独立于应用程序的.NET报表,同时FastReport .Net支持中文、英语等14种语言,可以让你的产品保证真正的国际性。 FastReport.NET官方版…...

DAMA数据管理知识体系指南之文档和内容管理
第10章 文档和内容管理 10.1 简介 文档和内容管理是对存储在关系数据库以外的信息的采集、存储、访问以及使用的控制活动。文档和内容管理的侧重点在完整性和访问控制上。因此,它与关系数据库的数据操作管理大致相同。由于多数非结构化数据与存储在结构化文件中的…...
C++入门:数据结构
C/C 数组允许定义可存储相同类型数据项的变量,但是结构是 C 中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。结构用于表示一条记录,假设您想要跟踪图书馆中书本的动态,您可能需要跟踪每本书的下列属性&#x…...

C语言实现烟花表白,内含源码!!
虽然现在看烟花有一定难度,但代码式烟花可以随时随地看! 烟花的代码很多,实际上是可以用 Python、HTML5 等语言写烟花,但今天主要想和大家分享用C语言写的烟花代码,非常细致和实用。 同学们一定要亲自敲一遍…...

虚拟机安装CentOS 7(带界面)
目录 一、虚拟机安装CentOS 7(带界面) 1、打开下好的VMware,点击创建虚拟机 2、下一步 3、点击下一步 4、选择Linux,ContOS7,点击下一步 5、修改虚拟机名称和路径 6、下一步 7、点击自定义硬件 8、设置虚拟机大…...

Java测试——selenium具体操作
selenium的前置准备工作可以参考我之前的博客:Java测试——selenium的安装与使用教程 这篇博客讲解一下selenium的常见操作 先创建driver ChromeDriver driver new ChromeDriver();输入网址 driver.get("https://www.baidu.com");常见操作 查找元素…...

电子器件系列32:逻辑与门芯片74LS11
一、编码规则 先看看这个代码的意思:74LS11 74是一个系列(74 表示为工作温度范围,74: 0 ~ 70度。) ls的意思就是工艺类型(Bipolar(双极)工艺) 11是代码 什么是74系列逻辑芯片? - 知乎 什么是…...

LeetCode-101. 对称二叉树
目录题目分析递归法题目来源 101. 对称二叉树 题目分析 首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一…...
使用intlinprog求解指派问题MATLAB代码分享
% 输入指派矩阵C [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];f C(:); %生成一个列向量,作为目标函数系数,matlab默认以列排序[m,n] size(C);Aeq zeros(2*n,n*n); %2*n个等式约束,n*n个变量for i 1:n %这里先生成的是后5个…...

Spark On YARN时指定Python版本
坑很多,直接上兼容性最佳的命令,将python包上传到hdfs或者file:/home/xx/(此处无多余的/) # client 模式 $SPARK_HOME/spark-submit \ --master yarn \ --deploy-mode client \ --num-executors 2 \ --conf "spark.yarn.dist.archives<Python包…...
[数据库]库的增删改查
●🧑个人主页:你帅你先说. ●📃欢迎点赞👍关注💡收藏💖 ●📖既选择了远方,便只顾风雨兼程。 ●🤟欢迎大家有问题随时私信我! ●🧐版权:本文由[你帅…...

Wine零知识学习1 —— 介绍
一、什么是Wine Wine是“Wine Is Not an Emulator” 的首字母缩写,是一个能够在多种POSIX-compliant操作系统(诸如Linux、macOS及BSD等)上运行 Windows 应用的兼容层。Wine不像虚拟机或者模拟器那样模仿内部的Windows逻辑,而是將…...

设计模式--建造者模式 builder
设计模式--建造者模式 builder)建造者模式简介建造者模式--小例子(电脑购买)1.产品类2.抽象构建者3.实体构建类4.指导者类5.客户端测试类小结建造者模式简介 建造者模式有四个角色,概念划分如下: Product : 产品类&a…...

终于周末啦,继续来总结一下Python的一些知识点啦
目录 Python概念梳理 常见概念梳理 Python经典判断题 判断题 选择题 Python概念梳理 常见概念梳理 Python中,不仅仅变量的值是可以变化的,类型也是可以随时变化的 1、Python的变量必须初始化否则提示 is not defined 2、if、while中定义的变量在…...

CUDA By Example(八)——流
文章目录页锁定主机内存可分页内存函数页锁定内存函数CUDA流使用单个CUDA流使用多个CUDA流GPU的工作调度机制高效地使用多个CUDA流遇到的问题(未解决)页锁定主机内存 在之前的各个示例中,都是通过 cudaMalloc() 在GPU上分配内存,以及通过标准的C库函数 …...

02- pandas 数据库 (数据库)
pandas 数据库重点: pandas 的主要数据结构: Series (一维数据)与 DataFrame (二维数据)。 pd.DataFrame(data np.random.randint(0,151,size (5,3)), # 生成pandas数据 index [Danial,Brandon,softpo,Ella,Cindy], # 行索引 …...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...

通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...

前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...