【面试经典150 | 动态规划】零钱兑换
文章目录
- Tag
- 题目来源
- 解题思路
- 方法一:动态规划
- 写在最后
Tag
【动态规划】【数组】
题目来源
322. 零钱兑换
解题思路
方法一:动态规划
定义状态
dp[i] 表示凑成总金额的最少硬币个数。
状态转移
从小到大枚举要凑成的金额 i,如果当前的金额可以使用面额数组中的某个面额 coin 凑成总金额的一部分,则可以更新
d p [ i ] = m i n ( d p [ i ] , d p [ i − c o i n ] + 1 ) dp[i] = min(dp[i], dp[i - coin] + 1) dp[i]=min(dp[i],dp[i−coin]+1)
base case
dp[0] = 0,表示凑成总金额 0 的硬币数量为 0。
最后返回
dp[amount],表示凑成总金额 amount 的最少硬币个数。注意需要判断面额数组是否可以凑成指定的总金额。
实现代码
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; ++i) {for (const auto coin : coins) {if (coin <= i) {dp[i] = min(dp[i], dp[i-coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount]; }
};
复杂度分析
时间复杂度: O ( S n ) O(Sn) O(Sn), S S S 是题目给定的需要凑成的总金额数, n n n 是面额数。我们一共需要计算 O ( S ) O(S) O(S) 个状态,每个状态需要枚举 n n n 个面额进行状态转移,所以时间复杂度为 O ( S n ) O(Sn) O(Sn)。
空间复杂度: O ( S ) O(S) O(S)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
相关文章:
【面试经典150 | 动态规划】零钱兑换
文章目录 Tag题目来源解题思路方法一:动态规划 写在最后 Tag 【动态规划】【数组】 题目来源 322. 零钱兑换 解题思路 方法一:动态规划 定义状态 dp[i] 表示凑成总金额的最少硬币个数。 状态转移 从小到大枚举要凑成的金额 i,如果当前…...
什么是防火墙,部署防火墙有什么好处?
与我们的房屋没有围墙或界限墙一样,没有防护措施的计算机和网络将容易受到黑客的入侵,这将使我们的网络处于巨大的风险之中。因此,就像围墙保护我们的房屋一样,虚拟墙也可以保护和安全我们的设备,使入侵者无法轻易进入…...
学习鸿蒙基础(10)
目录 一、轮播组件 Swiper 二、列表-List 1、简单的List 2、嵌套的List 三、Tabs容器组件 1、系统自带tabs案例 2、自定义导航栏: 一、轮播组件 Swiper Entry Component struct PageSwiper {State message: string Hello Worldprivate SwCon: SwiperControl…...
阿里云对象存储OSS入门
阅读目录 一、阿里云OSS的使用 1、OSS是什么?2、OSS的使用 二、阿里云OSS的使用三、图床的搭建四:图床绑定阿里云OSS 编写不易,如果我的文章对你有帮助的话,麻烦小伙伴还帮忙点个赞再走! 如果有小伙伴觉得写的啰嗦&a…...
[幻灯片]软件需求设计方法学全程实例剖析-03-业务用例图和业务序列图
DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 pdf已上传至本号的CSDN资源,或到以下地址下载: http://umlchina.com/training/umlchina_03_bm.pdf...
ctfshow-web入门-xxe
什么是xxe? XXE,全称XML External Entity Injection,即XML外部实体注入。这是一种针对应用程序解析XML输入类型的攻击。当包含对外部实体的引用的XML输入被弱配置的XML解析器处理时,就会发生这种攻击。这种攻击通过构造恶意内容&…...
Docker数据卷挂载
一、容器与数据耦合的问题: 数据卷是虚拟的,不真实存在的,它指向文件中的文件夹 ,属主机文件系统通过数据卷和容器数据进行联系,你改变我也改变。 解决办法: 对宿主机文件系统内的文件进行修改,会立刻反应…...
QT_day4:对话框
1、完善对话框,点击登录对话框,如果账号和密码匹配,则弹出信息对话框,给出提示”登录成功“,提供一个Ok按钮,用户点击Ok后,关闭登录界面,跳转到其他界面 如果账号和密码不匹配&…...
矢量数据库:连接人工智能应用程序的数据复杂性与可用性的桥梁
关注我的公众号:Halo咯咯 简介 矢量数据库是一种专门设计的数据库,专注于高效地存储、管理和操作矢量数据。与传统数据库处理标量值(如数字、字符串、日期)不同,矢量数据库针对的是那些表现为多维数据点的向量…...
docker:can’t create unix socket /var/run/docker.sock: is a directory
docker:can’t create unix socket /var/run/docker.sock: is a directory 原因:docker.sock不能创建 解决方式: rm -rf /var/run/docker.sock 然后重新启动docker Docker是一种相对使用较简单的容器,我们可以通过以下几种方式获取信息&…...
Qt 图形视图 /图形视图框架坐标系统的设计理念和使用方法
文章目录 概述Qt 坐标系统图形视图的渲染过程Item图形项坐标系Scene场景坐标系View视图坐标系map坐标映射场景坐标转项坐标视图坐标转图形项坐标图形项之间的坐标转换 其他 概述 The Graphics View Coordinate System 图形视图坐标系统是Qt图形视图框架的重要组成部分…...
视频号小店类目资质如何申请?新手看一遍就懂了!
我是电商珠珠 大家在视频号小店后台新增商品的时候,需要先完成类目资质的申请,通过后才可以上架相关商品。 而类目资质分为普通类目和特殊类目,如果你所上架的商品属于开放类目,那么就去按照普通类目资质去申请。 如果是定向准…...
整合SpringSecurity+JWT实现登录认证
一、关于 SpringSecurity 在 Spring Boot 出现之前,SpringSecurity 的使用场景是被另外一个安全管理框架 Shiro 牢牢霸占的,因为相对于 SpringSecurity 来说,SSM 中整合 Shiro 更加轻量级。Spring Boot 出现后,使这一情况情况大有…...
C# Onnx Yolov9 Detect 物体检测
目录 介绍 效果 项目 模型信息 代码 下载 C# Onnx Yolov9 Detect 物体检测 介绍 yolov9 github地址:https://github.com/WongKinYiu/yolov9 Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information…...
Flink SQL 基于Update流出现空值无法过滤问题
问题背景 问题描述 基于Flink-CDC ,Flink SQL的实时计算作业在运行一段时间后,突然发现插入数据库的计算结果发生部分主键属性发生失败,导致后续计算结果无法插入, 超过失败次数失败的情况问题报错 Caused by: java.sql.BatchUp…...
git-怎样把连续的多个commit合并成一个?
Git怎样把连续的多个commit合并成一个? Git怎样把连续的多个commit合并成一个? 参考URL: https://www.jianshu.com/p/5b4054b5b29e 查看git日志 git log --graph比如下图的commit 历史,想要把bai “Second change” 和 “Third change” 这…...
2024年2月游戏手柄线上电商(京东天猫淘宝)综合热销排行榜
鲸参谋监测的线上电商(京东天猫淘宝)游戏手柄品牌销售数据已出炉!2月游戏手柄销售数据呈现出强劲的增长势头。 根据鲸参谋数据显示,今年2月游戏手柄月销售量累计约43万件,同比去年上涨了78%;销售额累计达1…...
Sass5分钟速通基础语法
前言 近来在项目中使用sass,想着学习一下,但官方写的教程太冗杂,所以就有了本文速通Sass的基础语法 Sass 是 CSS 的一种预编译语言。它提供了 变量(variables)、嵌套规则(nested rules)、 混合(mixins) 等…...
百度蜘蛛池平台在线发外链-原理以及搭建教程
蜘蛛池平台是一款非常实用的SEO优化工具,它可以帮助网站管理员提高网站的排名和流量。百度蜘蛛池原理是基于百度搜索引擎的搜索算法,通过对网页的内容、结构、链接等方面进行分析和评估,从而判断网页的质量和重要性,从而对网页进行…...
Android_ android使用原生蓝牙协议_连接设备以后,给设备发送指令触发数据传输---Android原生开发工作笔记167
之前通过蓝牙连接设备的时候,直接就是连接上蓝牙以后,设备会自动发送数据,有数据的时候,会自动发送,但是,有一个设备就不会,奇怪了很久,设备启动了也连接上了,但是就是没有数据过来. 是因为,这个设备有几种模式是握力球,在设备连接到蓝牙以后,需要,给设备通过蓝牙发送一个指令…...
终极指南:使用Legacy-iOS-Kit轻松降级、越狱和修复旧款iOS设备
终极指南:使用Legacy-iOS-Kit轻松降级、越狱和修复旧款iOS设备 【免费下载链接】Legacy-iOS-Kit An all-in-one tool to downgrade/restore, save SHSH blobs, and jailbreak legacy iOS devices 项目地址: https://gitcode.com/gh_mirrors/le/Legacy-iOS-Kit …...
Teensy41嵌入式FTP服务器库:轻量协议栈与多网络适配
1. 项目概述FTP_Server_Teensy41 是一款专为 Teensy 4.x 系列微控制器(特别是 Teensy 4.0 和 Teensy 4.1)深度定制的嵌入式 FTP 服务器库。它并非从零构建,而是基于 Jean-Michel Gallego 开发的成熟开源项目 Arduino-Ftp-Server 进行了系统性…...
Apache Sedona 使用教程
Apache Sedona 使用教程 项目介绍 Apache Sedona 是一个用于大规模空间数据处理的分布式计算系统。它基于 Apache Spark,提供了高效的空间数据处理能力,支持多种空间数据类型和操作。Sedona 旨在为大数据环境下的地理空间分析提供强大的支持,…...
Kali Linux 2026.1 发布 (2026 主题 BackTrack 模式) - 领先的渗透测试发行版
Kali Linux 2026.1 发布 (2026 主题 & BackTrack 模式) - 领先的渗透测试发行版 The most advanced Penetration Testing Distribution 请访问原文链接:https://sysin.org/blog/kali-linux/ 查看最新版。原创作品,转载请保留出处。 作者主页&…...
深度学习助力图像增强:多算法与PyTorch复现
深度学习图像低光照增强算法低照度增强3DLUT,DeepUPT,DeepLPF,RetinexNet,Zero-DCE,EnlightenGAN,RetinexFormer等 图像调色增强算法HDRNet,StarEnhancer,CSRNet等 水下增强算法UWGAN,UIEGAN等 pytorch架构复现,有代码和benchmark数据集在图像处理领域,针…...
CssToInlineStyles终极调试指南:解决10个常见错误与性能优化技巧 [特殊字符]
CssToInlineStyles终极调试指南:解决10个常见错误与性能优化技巧 🚀 【免费下载链接】CssToInlineStyles CssToInlineStyles is a class that enables you to convert HTML-pages/files into HTML-pages/files with inline styles. This is very usefull…...
道心网络安全学习笔记系列之好靶场的信息收集2
上节课找了一个图片的网址,继续挑战其它靶场,我们看下一题收集十个百度域名,这还不是顺手就来,但是贴吧不行,那还不简单,去访问百度网站,顺便输入一个搜索词,都不用看,前…...
英雄联盟智能助手League Akari:5个必用功能让你的游戏体验翻倍提升
英雄联盟智能助手League Akari:5个必用功能让你的游戏体验翻倍提升 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit Le…...
ChatGPT订阅接口开发实战:从零搭建到生产环境部署
ChatGPT订阅接口开发实战:从零搭建到生产环境部署 最近在做一个需要集成智能对话能力的项目,自然而然地想到了ChatGPT的订阅接口。本以为调用个API是分分钟的事,结果一脚踩进了坑里。403鉴权失败、消息顺序错乱、突如其来的配额限制……这些…...
【MySQL | 第一篇】 深入理解三大日志(undo Redo Bin)
目录 Undo Log日志 Redo Log日志 Redo Log与Bin Log的区别 Bin Log日志 三大日志全流程 Undo Log日志 一、核心定义 Undo Log 是MySQL InnoDB存储引擎特有的事务回滚日志,核心作用是记录事务执行前的数据版本,用于事务回滚、MVCC实现,是…...
