当前位置: 首页 > 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

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

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

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

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