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

LeetCode 热题 100_零钱兑换（85_322_中等_C++）（动态规划）

news 来源：原创 2025/9/17 4:05:05

LeetCode 热题 100_零钱兑换（85_322）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（动态规划）：
  - 代码实现
  - - 代码实现（思路一（动态规划））：
    - 以思路一为例进行调试

题目描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

输入输出样例：

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

题解：

解题思路：

思路一（动态规划）：

1、通过题目的描述需解决凑成总金额所需的最少的硬币个数，且硬币可以重复使用，这样自然而然将问题转换为了完全背包问题（金币的数量为物品的个数，金额为物品的价值）。

2、具体思路如下：
① dp[j],dp数组的含义为：放满j容量的背包，最少的物品数量。
② dp[j]=min(dp[j],dp[j-nums[i]]+1) ，等号右侧 dp[ j ]代表不放物品 i ， dp[j-nums[i]]+1 代表放物品 j 。
③ dp[0]=0,因容量为 0 的背包可以放 0 件物品
④ 因取最小值，其他的dp数组的元素值为INT_MAX，数以这里需考虑溢出的情况dp[j-nums[i]]若为INT_MAX再加一则会溢出
⑤ 因可重复使用同一金额的硬币则遍历顺序为从左到右。

3、复杂度分析：
① 时间复杂度：O(Sn)，其中 S 是金额，n 是面额数（物品的价值）。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额（背包容量）。双重循环遍历物品和背包。

② 空间复杂度：O(S)。dp 所需的空间。

代码实现

代码实现（思路一（动态规划））：


class Solution{
public:// 定义 coinChange 函数，参数为硬币面值数组 coins 和目标金额 amountint coinChange(vector<int> &coins, int amount){// 初始化 dp 数组，大小为 amount + 1（从 0 到 amount），并将所有元素初始化为 INT_MAX// dp[i] 表示凑成金额 i 所需要的最少硬币数量vector<int> dp(amount + 1, INT_MAX);// dp[0] = 0，因为凑成金额 0 不需要任何硬币dp[0] = 0;// 外层循环遍历每种硬币（物品）for (int i = 0; i < coins.size(); i++){// 内层循环遍历从当前硬币面值到目标金额之间的所有金额（背包）for (int j = coins[i]; j <= amount; j++){// 防止数据溢出：只有当 dp[j - coins[i]] 不等于 INT_MAX 时，才进行更新// 这是因为如果 dp[j - coins[i]] 为 INT_MAX，表示无法凑成金额 j - coins[i]if (dp[j - coins[i]] != INT_MAX) {// 更新 dp[j]：表示使用当前硬币后，凑成金额 j 的最小硬币数dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}// 如果 dp[amount] 还是 INT_MAX，表示无法凑成目标金额，返回 -1// 否则返回 dp[amount]，即凑成目标金额所需要的最少硬币数量return dp[amount] == INT_MAX ? -1 : dp[amount];}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;class Solution{
public:// 定义 coinChange 函数，参数为硬币面值数组 coins 和目标金额 amountint coinChange(vector<int> &coins, int amount){// 初始化 dp 数组，大小为 amount + 1（从 0 到 amount），并将所有元素初始化为 INT_MAX// dp[i] 表示凑成金额 i 所需要的最少硬币数量vector<int> dp(amount + 1, INT_MAX);// dp[0] = 0，因为凑成金额 0 不需要任何硬币dp[0] = 0;// 外层循环遍历每种硬币（物品）for (int i = 0; i < coins.size(); i++){// 内层循环遍历从当前硬币面值到目标金额之间的所有金额（背包）for (int j = coins[i]; j <= amount; j++){// 防止数据溢出：只有当 dp[j - coins[i]] 不等于 INT_MAX 时，才进行更新// 这是因为如果 dp[j - coins[i]] 为 INT_MAX，表示无法凑成金额 j - coins[i]if (dp[j - coins[i]] != INT_MAX) {// 更新 dp[j]：表示使用当前硬币后，凑成金额 j 的最小硬币数dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}// 如果 dp[amount] 还是 INT_MAX，表示无法凑成目标金额，返回 -1// 否则返回 dp[amount]，即凑成目标金额所需要的最少硬币数量return dp[amount] == INT_MAX ? -1 : dp[amount];}
};int main(int argc, char const *argv[])
{// 给定硬币面值数组和目标金额vector<int> coins = {1, 2, 5};int amount = 11;// 创建 Solution 对象Solution s;// 调用 coinChange 函数并输出结果cout << s.coinChange(coins, amount);return 0;
}

LeetCode 热题 100_零钱兑换（85_322)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

LeetCode 热题 100_零钱兑换（85_322_中等_C++）（动态规划）

LeetCode 热题 100_零钱兑换（85_322） 题目描述：输入输出样例：题解：解题思路：思路一（动态规划）： 代码实现代码实现（思路一（动态规划）&a…...

编程日记 2025/9/17 4:05:05

Java——抽象方法抽象类接口详解及综合案例

1.抽象方法抽象类介绍抽象方法: 将共性的行为(方法)抽取到父类之后， 由于每一个子类执行的内容是不一样， 所以，在父类中不能确定具体的方法体。该方法就可以定义为抽象方法。抽象类: 如果一个类中存在抽象方法，那么该类就必须…...

编程日记 2025/9/16 0:52:18

国产芯片解析：LDR6501 Type-C接口OTG充电PD芯片详解

LDR6501 是一款专为 USB Type-C 设备设计的单C口DPR接口PD通信芯片，封装形式为 SOT23-6。此款芯片具有多项实用功能，在耳机转接器、领夹麦克风以及 OTG 转接头等应用中表现出色。应用领域 ‌耳机转接器‌：许多新型耳机采用 Type-C 接口&am…...

编程日记 2025/9/17 4:02:08

Payoneer(P卡）会关联吗？如何有效防止P卡关联？

随着跨境电商和全球支付需求的增加，Payoneer（简称P卡）成为了许多商家和个人进行国际支付和收款的重要工具。Payoneer是一种全球支付平台，支持用户跨国收款、汇款，并提供多种货币的账户支持。许多从事跨境电商的商家和…...

编程日记 2025/9/12 19:32:22

前端基础之《Vue（3）—计算属性》

一、computed选项 1、计算属性语法：在computed选项中，定义计算属性方法，在方法体使用声明式变量进行若干计算。 2、计算属性一定是个函数。一定有返回值。 3、计算属性的作用 （1）用于优化指令的表达式，…...

编程日记 2025/9/17 3:58:16

【Linux】Linux 权限：数字背后的神秘 “门禁卡” 系统

目录权限的基本概念Linux上用户的分类超级用户和普通用户用户之间的切换文件访问者的分类文件属性与访问权限Linux下的文件类型文件后缀在Linux中的作用文件自身的属性【⭐】文件访问者的三种权限【rwx】文件权限值的表示方法文件访问权限的相关设置方法chmod——设置文件的…...

编程日记 2025/9/16 6:32:31

Java中List方法的使用详解

目录一、List接口概述二、List常用方法（一）创建List对象（二）添加元素（三）删除元素（四）查找元素（五）遍历列表（六）列表的大小&#xff…...

编程日记 2025/9/17 3:59:32

多模态大语言模型arxiv论文略读（十一）

Can We Edit Multimodal Large Language Models? ➡️ 论文标题：Can We Edit Multimodal Large Language Models? ➡️ 论文作者：Siyuan Cheng, Bozhong Tian, Qingbin Liu, Xi Chen, Yongheng Wang, Huajun Chen, Ningyu Zhang ➡️ 研究机构: 浙江大…...

编程日记 2025/9/6 10:11:46

JS—防抖和节流：1分钟掌握防抖和节流

个人博客：haichenyi.com。感谢关注一. 目录一–目录二–防抖三–节流四–进阶应用五–总结二. 防抖（Debounce） 防抖（Debebounce）和节流（Throttle）都是前端开发中用于优化高频事件性能的两…...

编程日记 2025/9/9 13:42:09

MCP基础学习二：MCP服务搭建与配置

文章目录 MCP服务搭建与配置一，学习目标：二，学习内容：1. 如何搭建MCP服务端服务端初始化与配置MCP服务架构与数据流交互图核心实现注册服务功能服务器启动与API暴露 2. 本地应用与MCP服务的集成客户端SDK实现客户端应用实现功能演…...

编程日记 2025/9/17 4:05:03

MyBatis 操作数据库

目录什么是MyBatis? 注释 Mapper注释的介绍和使用 Select注释的介绍和使用 SpringBootTest注释的介绍和使用 Test注释的介绍的使用 MyBatis入门 1）准备工作 <1>创建工程 <2>数据准备 2）配置数据库连接字符串 3&#xff…...

编程日记 2025/9/6 21:37:03

蓉光：科技与自然的千年交响

故事背景故事发生在中国四川成都，这座千年古城在近未来完成蜕变，青城山的云雾与锦江的碧波间，智能建筑如雨后春笋般生长。全城建筑采用太阳能皮肤，街道流淌着数字化的都江堰水系，杜甫草堂的飞檐与机械芙蓉树共舞&…...

编程日记 2025/9/17 3:58:41

[C语言]gets和fgets函数区别及详解

一、gets 每当讨论 gets 函数时，大家不由自主地就会想起 1988 年的“互联网蠕虫”，它在 UNIX 操作系统的 finger 后台程序中使用一个 gets 调用作为它的攻击方式之一。很显然，对蠕虫病毒的实现来说， gets 函数的功劳不可小视。不…...

编程日记 2025/9/10 0:15:28

【场景应用3】audio_classification：音频分类的微调

1 引言本笔记展示了如何对多语种预训练的语音模型进行微调，以实现自动语音识别（Automatic Speech Recognition）。本笔记旨在使用SUPERB数据集中的关键词检测子集，并且可以使用任何来自模型库（Model Hub）的语音模型检查点，只要该模型有一个包含序列分类头（Sequence …...

编程日记 2025/9/14 10:09:28

【前端】【难点】前端富文本开发的核心难点总结与思路优化

前端富文本开发的核心难点总结富文本编辑器在前端开发中广泛应用于内容管理系统、文章发布、评论区等场景。其开发与集成存在较多复杂性，涵盖内容结构管理、交互体验、跨平台兼容性等方面，以下逐项分析。二、富文本开发的具体难点分析 （一…...

编程日记 2025/9/4 3:10:27

如何优雅使用 ReentrantLock 进行加解锁：避免常见坑点，提高代码可维护性

引言：锁的基本概念和问题在多线程编程中，为了确保多个线程在访问共享资源时不会发生冲突，我们通常需要使用锁来同步对资源的访问。Java 提供了不同的锁机制，其中 ReentrantLock 是一种最常用且功能强大的锁，它属于…...

编程日记 2025/9/12 13:25:28

帕金森患者行动迟缓，日常生活怎么破局？

帕金森病，是一种常见于中老年人的神经退行性疾病，正悄然改变着无数患者的生活轨迹。它初期症状隐匿，常以手抖为信号，起初可能只是在安静状态下，手部出现轻微且有节律的震颤，随着时间推移，震颤逐…...

编程日记 2025/9/16 4:06:20

7-openwrt-one通过web页面配置访客网络、无线中继等功能

前几个章节一直在介绍编译、分区之类的，都还没正常开始使用这个路由器的wifi。默认wifi是没有启动的，前面还是通过手动修改uci配置启动的，这个章节介绍下官方web页面的使用。特别是访客网络、无线中继 1、开启wifi，配置wifi基本信息我们使用有线连接路由器，通过192.168.…...

编程日记 2025/9/8 1:30:11

塑造现代互联网的力量：Berkeley在网络领域的影响与贡献

引言 “Berkeley” 这个名字在计算机网络和互联网领域中具有举足轻重的地位，许多关键的技术、协议和工具都与其紧密相关。它与加利福尼亚大学伯克利分校（UC Berkeley） 密切相关，该校在计算机科学与网络研究中做出了许多开创性的…...

编程日记 2025/9/13 16:45:13

大数据学习（105）-Hbase

🍋🍋大数据学习🍋🍋 🔥系列专栏： 👑哲学语录: 用力所能及，改变世界。 💖如果觉得博主的文章还不错的话，请点赞👍收藏⭐️留言📝支持一…...

编程日记 2025/9/16 7:15:09

c# 系列pdf转图片各种处理3--net3.1到net8 PDFtoImage

最近一直在做pdf渲染图片的问题，nuget PDFtoImage 支持3.1到net8 ，直接上代码 private static void DownloadFileAsync(string url, string localPath){using (HttpClient client new HttpClient()){client.DefaultRequestHeaders.Add("User-Agen…...

编程日记 2025/9/8 21:42:45

宁德时代25年春招笔试演绎数字推理SHL测评题库

宁德时代校招测评包含演绎推理数字推理两部分，请单击以下链接进行测评，详细操作指引请参见如下指引，请在测试前了解，大约用时60分钟。正式测评有两个部分:数字推理18分钟演绎推理18分钟，数字推理共10题，演绎…...

编程日记 2025/9/12 4:19:45

C# 看门狗策略实现

using System; using System.Threading;public class Watchdog {private Timer _timer;private volatile bool _isTaskAlive;private readonly object _lock new object();private const int CheckInterval 5000; // 5秒检测一次private const int TimeoutThreshold 10000; …...

编程日记 2025/9/9 22:31:54

聊透多线程编程-线程池-5.C# 线程池（ThreadPool）详解

1. 线程池的基本概念线程池的作用由于每创建一个线程都需要该线程分配一定的内存空间，因此创建大量线程会导致内存使用量迅速增加，并可能导致性能问题。线程池的主要目的是减少线程创建和销毁的开销，从而提高程序性能。线程池维护了…...

编程日记 2025/9/12 18:46:57

清华DeepSeek教程又双叒叕更新了！（共7份PDF下载）

清华团队的DeepSeek教程又双叒叕更新了，目前共计有7份DeepSeek的教程，分别是《DeepSeek从入门到精通》、《DeepSeek赋能职场》、《普通人如何抓住DeepSeek红利》、《DeepSeekDeepResearch：让科研像聊天一样简单》、《DeepSeek与AI幻觉》、《A…...

编程日记 2025/9/8 8:20:04

免费在线文档工具,在线PDF添加空白页,免费在任意位置插入空白页,多样化的文件处理

小白工具（https://www.xiaobaitool.net/files/pdf-add-page/ ）是一款免费的在线文档工具，专注于为用户提供便捷的 PDF 空白页添加服务。功能特点：该工具支持在 PDF 文件的任意位置插入单页或多页空白页，能满足用户不同…...

编程日记 2025/9/9 3:03:34

MATLAB在哪些特定领域比Python更有优势？

文章目录前言科学研究与工程计算数值计算信号处理控制系统设计教育领域易于学习和上手教学资源丰富快速原型开发集成开发环境便捷前言 MATLAB 在以下特定领域比 Python 更具优势： 科学研究与工程计算数值计算高效矩阵运算：MATLAB 以矩阵为基本数…...

编程日记 2025/9/5 7:11:28

CAN协议

CAN简介 TJA1050(高速CAN收发器) 5V供电界定符用来隔开各个数据这个时候就要用到采样了谁先谁后？？仲裁机制发送邮箱用来放帧的正常模式：正常收发静默模式：只收不发环回模式：不读，自己收环回静…...

编程日记 2025/9/15 10:55:30

MFC案例：用鼠标移动窗口图像的实验

当使用基于对话框的MFC项目窗口显示图像时，如窗口的尺寸小于图像的尺寸，在不做缩放的情况下按照原图尺寸在窗口显示，那么只能看到图像的局部，这时我们希望可以通过鼠标移动图像进而显示其它部分。今天就进行这个实验，编…...

编程日记 2025/9/11 6:52:54

Linux基础IO（五）之用户缓冲区

文章目录缓冲区FILE初步实现缓冲区缓冲区 FILE 因为IO相关函数与系统调用接口对应，并且库函数封装系统调用， 所以本质上，访问文件都是通过fd访问的。所以C库当中的FILE结构体内部，必定封装了fd。编写代码and查看现象&…...

编程日记 2025/9/14 0:17:44

【Scrapy】Scrapy教程12——中间件

中间件这部分算是一个高阶的Scrapy内容，即便不了解这部分也可以使用Scrapy，但是一些特殊情况使用中间件就比较方便处理了，比如修改请求和响应等。通过之前的工作原理图中，我们了解到Scrapy中有两个中间件，分别是下载器中间件和爬虫中间件，本节将一一讲解如何激活、编写自…...

编程日记 2025/9/11 7:17:44

C++学习之ORACLE①

目录 1.ORACLE数据库简介 2..ORACLE数据库安装 3..ORACLE体系结构 4..ORACLE基本概念 5..ORACLE基本元素 6..ORACLE数据库启动和关闭 7.SQLPLUS登录ORACLE数据库相关操作 8.SQLPLUS的基本操作 9.oracle中上课使用的方案 10.SQL语言分类 11.SQL中的select语句语法和注…...

编程日记 2025/9/8 8:07:45

vue---按钮防抖和节流----项目问题

一般来说前端都需要做按钮防抖避免一个时间被重复触发，首先可能会出现bug，消耗服务器性能，用户体验也不是很好。 1.防抖解决方法：main.js文件自定义指令 Vue.directive("preventReClick", {inserted(el, binding) {…...

编程日记 2025/9/6 23:20:27

【LunarVim】解决which-key 自定义键位注册不成功问题

问题描述 LunarVim将which-key设置放在一个keymaps.lua中，然后config.lua调用reload “user.keymaps”，键位没用注册成功，而直接写在config.lua中，就注册成功这暴露了LunarVim 插件和配置加载顺序的一些细节坑，下面解…...

编程日记 2025/9/16 4:09:30

湖北趣豆智能科技有限公司浅析XR技术对传统游戏的影响

在科技飞速发展的当下，XR（扩展现实）技术正以前所未有的态势重塑游戏行业格局。湖北趣豆智能科技有限公司凭借在XR技术与游乐设备融合领域的创新实践，对XR技术给传统游戏带来的影响有着深刻见解。沉浸体验升级，重塑游戏…...

编程日记 2025/9/9 3:20:21

[操作系统] 进程间通信：system V共享内存

文章目录内存共享示意图共享内存的管理代码shmget 函数原理先创建共享内存如何保证两个不同的进程拿到的是一块共享内存 shmctl 函数IPC_RMID参数 shmat函数无同步机制同步机制是什么模拟演示非同步效果如何提供保护机制 shmdt再谈描述共享内存的数据结构struct shmid_dsstruc…...

编程日记 2025/9/15 13:39:11

科技快讯 | 阿里云百炼MCP服务上线；英伟达官宣：CUDA 工具链将全面原生支持 Python

李飞飞团队最新AI报告：中美模型性能差距近乎持平 4月8日，斯坦福大学以人为本人工智能研究所发布《2025年人工智能指数报告》。报告显示，2023年AI性能显著提升，AI应用加速，投资增长，中美AI模型差距缩小。报告…...

编程日记 2025/9/11 1:15:17

踩雷，前端一直卡在获取token中

问题：一直卡在var token SecureStorage.Default.GetAsync("auth_token").Result; public VideoService(){_httpClient new HttpClient();var token SecureStorage.Default.GetAsync("auth_token");} 这是一个典型的同步等待异步操作导致的死…...

编程日记 2025/9/15 4:46:24

MATLAB双目标定

前言： 现在有许多双目摄像头在出厂时以及标定好，用户拿到手后可以直接使用，但也有些双目摄像头在出厂时并没有标定。因而这个时候就需要自己进行标定。本文主要介绍基于matlab工具箱的自动标定方式来对双目相机进行标定。 1、MATLAB工具箱标…...

编程日记 2025/9/1 7:23:03

4.10学习总结

完成两道算法题（感觉对贪心的思路很难去想到如何解） 完成stream流的学习，开始学习方法引用...

编程日记 2025/9/12 14:56:58

QML自定义组件

自定义组件是 QML 开发中的核心概念，它允许您创建可重用的 UI 元素和逻辑单元。以下是创建和使用自定义组件的完整方法。 1. 基本自定义组件创建创建单独组件文件 (推荐方式) qml // MyButton.qml（单独一个qml文件）import QtQuick 2.15R…...

编程日记 2025/9/6 22:06:18

多模态大语言模型arxiv论文略读（十）

Towards End-to-End Embodied Decision Making via Multi-modal Large Language Model: Explorations with GPT4-Vision and Beyond ➡️ 论文标题：Towards End-to-End Embodied Decision Making via Multi-modal Large Language Model: Explorations with GPT4-Vi…...

编程日记 2025/9/7 20:38:22

关于 Spring Boot + Vue 前后端开发的打包、测试、监控、预先编译和容器部署的详细说明，涵盖从开发到生产部署的全流程

以下是关于 Spring Boot Vue 前后端开发的打包、测试、监控、预先编译和容器部署的详细说明，涵盖从开发到生产部署的全流程： 1. 打包 1.1 后端（Spring Boot） 打包方式使用 Maven 或 Gradle 打包成可执行的 JAR/WAR 文件&…...

编程日记 2025/9/16 5:56:57

【Raqote】 1.1 路径填充ShaderMaskBlitter 结构体（blitter.rs）

ShaderMaskBlitter 结构体实现了 Blitter trait，用于带遮罩的着色器渲染。结构体定义 pub struct ShaderMaskBlitter<a> {pub x: i32, // 目标区域的起始x坐标pub y: i32, // 目标区域的起始y坐标pub shader: &a dyn Shader, //…...

编程日记 2025/9/14 4:00:05

如何用 esProc 实现 Oracle 和 MySQL 的混合运算

逻辑数仓可以实现多源混算，但需要配置视图、预处理数据，结构太沉重。duckdb 是轻量级的方案，但没有内置 Oracle 的 connector，自己开发难度又太高。同为轻量级方案，esProc 支持 JDBC 公共接口，可以实现任何…...

编程日记 2025/9/8 15:50:30

zabbix和prometheus选择那个监控呢

文章目录 Zabbix 介绍概述架构组成特点适用场景 Prometheus 介绍概述架构组成特点适用场景 Zabbix vs Prometheus 对比架构与组件Zabbix 架构Prometheus 架构监控要点与最佳实践告警与可视化ZabbixPrometheus Alertmanager Grafana 伸缩与高可用ZabbixPrometheus 运维成本与…...

编程日记 2025/9/12 5:18:42