【面试经典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)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/491703.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

204基于matlab的图像融合

基于matlab的图像融合&#xff0c;包括三种方式&#xff0c;加权、PCA、IHS变换。比较三者融合后的图像差异。程序已调通&#xff0c;可直接运行。 204 matlab 图像融合 信息融合 - 小红书 (xiaohongshu.com)

便携式一体化气象站设备

TH-PQX7便携式一体化气象站设备是一种集多种气象监测仪器于一体的高科技装备&#xff0c;能够实现对温度、湿度、风速、风向、气压、降水量等关键气象要素的实时监测。该设备采用先进的传感器技术和数据处理技术&#xff0c;具有高精度、高可靠性、低功耗等特点&#xff0c;可广…

kubernetes-networkpolicies网络策略问题

kubernetes-networkpolicies网络策略问题 问题描述 重点重点重点&#xff0c;查看我的博客CKA考题&#xff0c;里面能找到解决方法 1.部署prometheus监控的时候&#xff0c;都部署成功&#xff0c;但是web访问503-504超时 2.添加ingress的时候也是访问不到&#xff0c;其他命…

matlab编译成jar包

1、输入deploytool命令 2、选择Library Compiler 3、配置打包 4、有效文件 5、java函数调用 package com.beescloud.frame.matlab;import com.mathworks.toolbox.javabuilder.MWException; import test.Class1;public class MatlabTest {public static void main(String[] arg…

我的创作纪念日 ---- 2024/3/26

前言 2024.3.26是我在CSDN成为创作者的第128天&#xff0c;也是我第一次真正在网上创作的第128天 当我还在日常创作时&#xff0c;突然发现我收到了一封信 我想我可以分享一下这段时间的感想以及收获 机缘 在CSDN的这段时间里&#xff0c;我学习到了很多知识&#xff0c;也…

Linux之时间子系统(四): tick 层模块(broadcast )

一、前言 在内核中&#xff0c;有cpuidle framework可以控制cpu的节电&#xff1a;当没有进程调度到该cpu上执行的时候&#xff0c;swapper进程粉墨登场&#xff0c;将该cpu会被推入到idle状态。当然CPU的idle状态有深有浅&#xff0c;当CPU睡的比较深入的时候&#xff0c;有可…

hadoop 查询hdfs资源信息的方式

hdfs dfsadmin -report &#xff3b;-live&#xff3d;&#xff3b;-dead&#xff3d;&#xff3b;-decommissioning&#xff3d;

跟张良均老师学大数据人工智能——数据挖掘集训营开营

集训营特色&#xff1a; 知识点深入浅出&#xff0c;实现以学促用 以业务内容为主线&#xff0c;数据挖掘技能嵌入 多行业项目实战&#xff0c;全面提升职业素养 全程线上辅导&#xff0c;助力熟练掌握技能 惊喜优惠&#xff1a; 限时“六折”&#xff01; 师傅带练 方向…

芝麻云节点服务器:零知识加密与跨用户兼得

海量大数据是指数据量特别大、数据类别非常大的数据集&#xff0c;而这样的数据集无法使用传统的数据库工具进行捕获、管理和处理。 数据量太大&#xff0c;没有地方存放。 服务器硬盘能存储多少数据肯定无法满足如此大量的数据存储需求。 因此&#xff0c;分布式存储系统应运而…

Git常用指令使用

摘要&#xff1a;之前代码管理都是借助于fork、sourceTree等图形工具&#xff0c;最近发现直接用命令也好用&#xff0c;就总结Git常用的指令 1、Git的介绍 1.1 git官网 安装: Git - Downloading Packagehttps://git-scm.com/download/mac Mac上安装&#xff0c;直接使…

【WEEK5】 【DAY2】文件上传下载【中文版】

2024.3.26 Tuesday 目录 10.文件的上传和下载10.1.准备工作10.2.基础配置10.2.1.新建名为springmvc-08-file的module10.2.2.新建controller文件夹&#xff0c;applicationContext.xml文件 10.3.文件上传10.3.1.在本模块的pom.xml中导入文件上传的jar包&#xff1a;commons-file…

虎课网C4D软件系列课程

教程介绍 讲解C4D从0基础到精通&#xff0c;课程涵盖C4D的多边形建模&#xff0c;材质灯光&#xff0c;运动图形&#xff0c;效果器&#xff0c;并有实例教学。 学习地址 百度网盘&#xff1a;https://pan.baidu.com/s/1R9zampaH-KWH7Q6ZcPTrQQ?pwdxhlw

Embedding模型提升效果的方法之一:Whitening和pooling

0. 前言 Embedding模型的主流框架基本上分为三类——基于bert结构的&#xff0c;基于GPT结构的和基于T5结构的&#xff0c;当然这些结构都是Transformer的变形。对于Embedding模型&#xff0c;使用bert结构目前看是最好的。有篇论文论文对基于bert的Embedding模型和基于GPT的E…

How to convert .py to .ipynb in Ubuntu 22.04

How to convert .py to .ipynb in Ubuntu 22.04 jupyter nbconvertp2j 最近看到大家在用jupyter notebook&#xff0c;我也试了一下&#xff0c;感觉还不错&#xff0c;不过&#xff0c;也遇到了一些问题&#xff0c;比方说&#xff0c;我有堆的.py文件&#xff0c;如果要一个一…

STM32 使用gcc编译介绍

文章目录 前言1. keil5下的默认编译工具链用的是哪个2. Arm编译工具链和GCC编译工具链有什么区别吗&#xff1f;3. Gcc交叉编译工具链的命名规范4. 怎么下载gcc-arm编译工具链参考资料 前言 我们在STM32上进行开发时&#xff0c;一般都是基于Keil5进行编译下载&#xff0c;Kei…

C++STL学习之unordered_map与unordered_set(底层Hash)

前言&#xff1a;我们前面已经学习论map和set&#xff0c;现在又冒出来一个unordered_map和unordered_set&#xff0c;这两个有啥差别吗&#xff1f;前面我们已经说过&#xff0c;map和set的底层是红黑树&#xff0c;那unordered_map和unordered_set的底层是什么呢&#xff1f;…

2024 解决 Failed to launch process [ElasticSearch]

操作系统&#xff1a;centos 7 (x86) sonarQube不能使⽤root账号进⾏启动&#xff0c;所以需要创建普通⽤户及其⽤户组 一、问题描述&#xff1a;使用root启动时&#xff0c;一直反馈 SonarQube is not running 问题原因&#xff1a;不能够使用root用户进行启动 解决方案…

Python(Socket) +Unreal(HTTP)

Python&#xff08;Socket&#xff09; Unreal&#xff08;HTTP&#xff09; python&#xff08;Socket&#xff09;:UE&#xff1a;Post请求并发送本机IP 上班咯&#xff0c;好久没记笔记了。。。 局域网 UE的apk&#xff0c;请求Python的Socket 跑起Socket &#xff0c;UE发 …

【Python机器学习系列】sklearn机器学习模型的保存---joblib法

这是我的第247篇原创文章。 一、引言 joblib包是由scikit-learn外带的&#xff0c;是一个用于将Python对象序列化为磁盘文件的库&#xff0c;专门用于大型数组&#xff0c;常用于保存机器学习模型。它可以高效地处理大型数据集和模型。对于大数据和大型机器学习模型&#xff0…

JavaScript高级(一)--V8引擎上

浏览器渲染的原理 主流浏览器及其内核 内核浏览器css前缀备注TridentIE4-IE11-ms最新的Edge已转向BlinkGecko火狐浏览器-mozWebkitsafari、旧版谷歌-webkitBlinkGoogle Chrome-webkitPrestoopera-o现在的opera转向了Blink 我们常说的浏览器内核指的就是浏览器的排版引擎&…