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

【面试经典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[icoin]+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题目来源解题思路方法一&#xff1a;动态规划 写在最后 Tag 【动态规划】【数组】 题目来源 322. 零钱兑换 解题思路 方法一&#xff1a;动态规划 定义状态 dp[i] 表示凑成总金额的最少硬币个数。 状态转移 从小到大枚举要凑成的金额 i&#xff0c;如果当前…...

什么是防火墙,部署防火墙有什么好处?

与我们的房屋没有围墙或界限墙一样&#xff0c;没有防护措施的计算机和网络将容易受到黑客的入侵&#xff0c;这将使我们的网络处于巨大的风险之中。因此&#xff0c;就像围墙保护我们的房屋一样&#xff0c;虚拟墙也可以保护和安全我们的设备&#xff0c;使入侵者无法轻易进入…...

学习鸿蒙基础(10)

目录 一、轮播组件 Swiper 二、列表-List 1、简单的List 2、嵌套的List 三、Tabs容器组件 1、系统自带tabs案例 2、自定义导航栏&#xff1a; 一、轮播组件 Swiper Entry Component struct PageSwiper {State message: string Hello Worldprivate SwCon: SwiperControl…...

阿里云对象存储OSS入门

阅读目录 一、阿里云OSS的使用 1、OSS是什么&#xff1f;2、OSS的使用 二、阿里云OSS的使用三、图床的搭建四&#xff1a;图床绑定阿里云OSS 编写不易&#xff0c;如果我的文章对你有帮助的话&#xff0c;麻烦小伙伴还帮忙点个赞再走&#xff01; 如果有小伙伴觉得写的啰嗦&a…...

[幻灯片]软件需求设计方法学全程实例剖析-03-业务用例图和业务序列图

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 pdf已上传至本号的CSDN资源&#xff0c;或到以下地址下载&#xff1a; http://umlchina.com/training/umlchina_03_bm.pdf...

ctfshow-web入门-xxe

什么是xxe&#xff1f; XXE&#xff0c;全称XML External Entity Injection&#xff0c;即XML外部实体注入。这是一种针对应用程序解析XML输入类型的攻击。当包含对外部实体的引用的XML输入被弱配置的XML解析器处理时&#xff0c;就会发生这种攻击。这种攻击通过构造恶意内容&…...

Docker数据卷挂载

一、容器与数据耦合的问题: 数据卷是虚拟的&#xff0c;不真实存在的&#xff0c;它指向文件中的文件夹 &#xff0c;属主机文件系统通过数据卷和容器数据进行联系&#xff0c;你改变我也改变。 解决办法&#xff1a; 对宿主机文件系统内的文件进行修改&#xff0c;会立刻反应…...

QT_day4:对话框

1、完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密码不匹配&…...

矢量数据库:连接人工智能应用程序的数据复杂性与可用性的桥梁

关注我的公众号&#xff1a;Halo咯咯 简介 矢量数据库是一种专门设计的数据库&#xff0c;专注于高效地存储、管理和操作矢量数据。与传统数据库处理标量值&#xff08;如数字、字符串、日期&#xff09;不同&#xff0c;矢量数据库针对的是那些表现为多维数据点的向量&#xf…...

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 原因&#xff1a;docker.sock不能创建 解决方式&#xff1a; rm -rf /var/run/docker.sock 然后重新启动docker Docker是一种相对使用较简单的容器&#xff0c;我们可以通过以下几种方式获取信息&…...

Qt 图形视图 /图形视图框架坐标系统的设计理念和使用方法

文章目录 概述Qt 坐标系统图形视图的渲染过程Item图形项坐标系Scene场景坐标系View视图坐标系map坐标映射场景坐标转项坐标视图坐标转图形项坐标图形项之间的坐标转换 其他 概述 The Graphics View Coordinate System 图形视图坐标系统是Qt图形视图框架的重要组成部分&#xf…...

视频号小店类目资质如何申请?新手看一遍就懂了!

我是电商珠珠 大家在视频号小店后台新增商品的时候&#xff0c;需要先完成类目资质的申请&#xff0c;通过后才可以上架相关商品。 而类目资质分为普通类目和特殊类目&#xff0c;如果你所上架的商品属于开放类目&#xff0c;那么就去按照普通类目资质去申请。 如果是定向准…...

整合SpringSecurity+JWT实现登录认证

一、关于 SpringSecurity 在 Spring Boot 出现之前&#xff0c;SpringSecurity 的使用场景是被另外一个安全管理框架 Shiro 牢牢霸占的&#xff0c;因为相对于 SpringSecurity 来说&#xff0c;SSM 中整合 Shiro 更加轻量级。Spring Boot 出现后&#xff0c;使这一情况情况大有…...

C# Onnx Yolov9 Detect 物体检测

目录 介绍 效果 项目 模型信息 代码 下载 C# Onnx Yolov9 Detect 物体检测 介绍 yolov9 github地址&#xff1a;https://github.com/WongKinYiu/yolov9 Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information…...

Flink SQL 基于Update流出现空值无法过滤问题

问题背景 问题描述 基于Flink-CDC &#xff0c;Flink SQL的实时计算作业在运行一段时间后&#xff0c;突然发现插入数据库的计算结果发生部分主键属性发生失败&#xff0c;导致后续计算结果无法插入&#xff0c; 超过失败次数失败的情况问题报错 Caused by: java.sql.BatchUp…...

git-怎样把连续的多个commit合并成一个?

Git怎样把连续的多个commit合并成一个&#xff1f; Git怎样把连续的多个commit合并成一个&#xff1f; 参考URL: https://www.jianshu.com/p/5b4054b5b29e 查看git日志 git log --graph比如下图的commit 历史&#xff0c;想要把bai “Second change” 和 “Third change” 这…...

2024年2月游戏手柄线上电商(京东天猫淘宝)综合热销排行榜

鲸参谋监测的线上电商&#xff08;京东天猫淘宝&#xff09;游戏手柄品牌销售数据已出炉&#xff01;2月游戏手柄销售数据呈现出强劲的增长势头。 根据鲸参谋数据显示&#xff0c;今年2月游戏手柄月销售量累计约43万件&#xff0c;同比去年上涨了78%&#xff1b;销售额累计达1…...

Sass5分钟速通基础语法

前言 近来在项目中使用sass,想着学习一下,但官方写的教程太冗杂,所以就有了本文速通Sass的基础语法 Sass 是 CSS 的一种预编译语言。它提供了 变量&#xff08;variables&#xff09;、嵌套规则&#xff08;nested rules&#xff09;、 混合&#xff08;mixins&#xff09; 等…...

百度蜘蛛池平台在线发外链-原理以及搭建教程

蜘蛛池平台是一款非常实用的SEO优化工具&#xff0c;它可以帮助网站管理员提高网站的排名和流量。百度蜘蛛池原理是基于百度搜索引擎的搜索算法&#xff0c;通过对网页的内容、结构、链接等方面进行分析和评估&#xff0c;从而判断网页的质量和重要性&#xff0c;从而对网页进行…...

Android_ android使用原生蓝牙协议_连接设备以后,给设备发送指令触发数据传输---Android原生开发工作笔记167

之前通过蓝牙连接设备的时候,直接就是连接上蓝牙以后,设备会自动发送数据,有数据的时候,会自动发送,但是,有一个设备就不会,奇怪了很久,设备启动了也连接上了,但是就是没有数据过来. 是因为,这个设备有几种模式是握力球,在设备连接到蓝牙以后,需要,给设备通过蓝牙发送一个指令…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...