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

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

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

(十)学生端搭建

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

三维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;确保相对路径.…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...