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

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

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 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 系统…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...