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

经典动态规划题目leetcode322. 零钱兑换

题目链接:https://leetcode.cn/problems/coin-change/description/

给你一个整数数组 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] <= 231 - 1
0 <= amount <= 104

AC代码

#include <iostream>
#include <vector>using namespace std;int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1);dp[0] = 0;for (int coin : coins) {for (int i = coin; i <= amount; ++i) {dp[i] = min(dp[i], dp[i - coin] + 1);}}return dp[amount] > amount ? -1 : dp[amount];
}int main() {vector<int> coins = {1, 2, 5};int amount = 11;cout << coinChange(coins, amount) << endl;return 0;
}

代码解释
这个C++程序首先定义了一个动态规划数组dp,其中dp[i]表示兑换i元所需的最少硬币数量。初始化时,dp[0]被设置为0,其他位置被设置为一个很大的数(这里设置为amount + 1)。

然后,程序遍历每个硬币,对于每个硬币,程序遍历从该硬币面值到amount的所有金额,更新dp数组。具体来说,对于每个金额i,程序比较兑换i元所需的最少硬币数量和兑换i - coin元所需的最少硬币数量加上1(即使用当前硬币),取两者中的最小值。

最后,程序返回dp[amount],即兑换amount元所需的最少硬币数量。如果dp[amount]大于amount,则表示无法兑换,返回-1。

相关文章:

经典动态规划题目leetcode322. 零钱兑换

题目链接&#xff1a;https://leetcode.cn/problems/coin-change/description/ 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合…...

python 使用curl_cffi 绕过jax3指纹-Cloudflare 5s盾

现在越来越多的网站已经能够通过JA3或者其他指纹信息&#xff0c;来识别你是不是爬虫了。传统的方式比如换UA&#xff0c;加代理是没有任何意义了&#xff0c;所以这个时候我们就需要使用到curl_cffi 了。 1.TLS 指纹是啥&#xff1f; 在绝大多数的网站都已经使用了 HTTPS&am…...

Python3学习笔记39-passlib

passlib处理密码哈希的python包,支持很多哈希算法和工具 bcrypt 安装 pip install passlib[bcrypt] 会安装passlib包和bcrypt两个包 密码哈希与校验 from passlib.context import CryptContext# 创建CryptContext对象&#xff0c;指定加密算法 pwd_context CryptContext…...

Matlab 机器人工具箱 动力学

文章目录 R.dynR.fdynR.accelR.rneR.gravloadR.inertiaR.coriolisR.payload官网:Robotics Toolbox - Peter Corke R.dyn 查看动力学参数 mdl_puma560; p560.dyn;%查看puma560机械臂所有连杆的动力学参数 p560.dyn(2);%查看puma560机械臂第二连杆的动力学参数 p560.links(2)…...

Android ShellUtils手机管理器

1. Android ShellUtils手机管理器 Android Shell工具类&#xff0c;可用于检查系统root权限&#xff0c;并在shell或root用户下执行shell命令。如&#xff1a; checkRootPermission() 检查root权限 。execCommand(String[] commands, boolean isRoot, boolean isNeedResultMsg)…...

《梦幻西游》本人收集的34个单机版游戏,有详细的视频架设教程,值得收藏

梦幻西游这款游戏&#xff0c;很多人玩&#xff0c;喜欢研究的赶快下载吧。精心收集的34个版本。不容易啊。里面有详细的视频架设教程&#xff0c;可以外网呢。 《梦幻西游》本人收集的34个单机版游戏&#xff0c;有详细的视频架设教程&#xff0c;值得收藏 下载地址&#xff1…...

吴恩达机器学习全课程笔记第六篇

目录 前言 P96-P100 使用多个决策树 随机森林算法 XGBoost 什么时候使用决策树 P101-P107 聚类 K-means 初始化K-means 选择聚类的个数 P108-P113 异常检测算法 开发和评估异常检测系统 异常检测vs监督学习 选择要使用的特征 前言 这是吴恩达机器学习笔记的第…...

ue4.27 发现 getRandomReachedLocation 返回 false

把这个玩意儿删掉&#xff0c;重启工程&#xff0c;即可 如果还不行 保证运动物体在 volum 内部&#xff0c;也就是绿色范围内确保 project setting 里面的 navigation system 中 auto create navigation data 是打开的(看到过博客说关掉&#xff0c;不知道为啥) 如果还不行&…...

【C++ AVL树】

文章目录 AVL树AVL树的概念AVL树节点的定义AVL树的插入AVL树的旋转右单旋左单旋左右双旋右左双旋 代码实现 总结 AVL树 AVL树的概念 二叉搜索树在顺序有序或接近有序的情况下&#xff0c;而插入搜索树将退化为单叉树&#xff0c;此时查找的时间复杂度为O(n)&#xff0c;效率低…...

记录一次架构优化处理性能从3千->3万

0.背景 优化Kafka消费入Es&#xff0c;适配600台设备上报数据&#xff0c;吞吐量到达2万每秒 1.环境配置 2.压测工具 3.未优化之前的消费逻辑 4.优化之后的消费流程 5.多线程多ESclient 6.修改ES配置&#xff0c;增加kafka分区&#xff0c;增加线程&#xff0c;提升吞吐量 7.…...

c++二进制位运算使用方法

文章主要内容&#xff1a; C 中的位运算符主要用于对整数类型的数据进行位操作&#xff0c;包括按位与&#xff08;&&#xff09;、按位或&#xff08;|&#xff09;、按位异或&#xff08;^&#xff09;、取反&#xff08;~&#xff09;、左移&#xff08;<<&#…...

TypeScript之JSON点语法调用

场景 当我们想要通过将JSON中的属性名赋值给一个变量,并且通过点语法实现字段调用.常规的String变量保存会出现下述问题,就可以通过String[][]实现动态调用字段. let parentJSON{"name":"liupeng"}let a:String;Object.keys(parentJSON).forEach(key >…...

手撕Java集合之简易版Deque(LinkedList)

在目前&#xff0c;许多互联网公司的面试已经要求能手撕集合源码&#xff0c;集合源码本身算是源码里比较简单的一部分&#xff0c;但是要在面试极短的10来分钟内快速写出一个简易版的源码还是比较麻烦的&#xff0c;很容易出现各种小问题。所以在平时就要注重这方面的联系。 以…...

MySQL知识点归纳总结(二)

10、MVCC实现原理&#xff1f; 事务ID&#xff08;Transaction ID&#xff09;&#xff1a;每个事务在执行时都会被分配一个唯一的事务ID&#xff0c;用于标识该事务的开始时间顺序。事务ID是一个递增的整数&#xff0c;随着每个新事务的开始而递增。 Undo日志&#xff08;Un…...

vue:实现顶部消息横向滚动通知

前言 系统顶部展示一个横向滚动的消息通知&#xff0c;就是消息内容从右往左一直滚动。 效果如下&#xff1a; 代码 使用 <template><div class"notic-bar"><img :src"notic" class"notice-img" /><div class"noti…...

[笔记] wsl 禁用配置 win系统环境变量+代理

wsl 配置禁用 win系统环境变量 进入 wsl 的 /etc/wsl.conf 目录&#xff0c;增加以下配置&#xff1a; [interop] enabledfalse appendWindowsPathfalse然后退出wsl&#xff0c;并且执行关闭正在运行的 wsl&#xff0c;执行命令 wsl --shutdown 最后重新进入wsl 即可。 参考…...

Mysql标量子查询

目录 子查询标量子查询数据准备 子查询 SQL语句中嵌套select语句&#xff0c;称为嵌套查询&#xff0c;又称子查询。 SELECT * FROM t1 WHERE column1 ( SELECT column1 FROM t2 ... );子查询外部的语句可以是insert / update / delete / select 的任何一个&…...

深入了解Java虚拟机(JVM)

Java虚拟机&#xff08;JVM&#xff09;是Java程序运行的核心组件&#xff0c;它负责解释执行Java字节码&#xff0c;并在各种平台上执行。JVM的设计使得Java具有跨平台性&#xff0c;开发人员只需编写一次代码&#xff0c;就可以在任何支持Java的系统上运行。我们刚开始学习Ja…...

Image Fusion via Vision-Language Model【文献阅读】

阅读目录 文献阅读AbstractIntroduction3. Method3.1. Problem Overview3.2. Fusion via Vision-Language Model 4. Vision-Language Fusion Datasets5. Experiment5.1Infrared and Visible Image Fusion 6. Conclusion个人总结 文献阅读 原文下载&#xff1a;https://arxiv.or…...

探索Manticore Search:开源全文搜索引擎的强大功能

在当今信息爆炸的时代&#xff0c;数据的快速检索变得至关重要。无论是在电子商务网站、新闻门户还是企业内部文档&#xff0c;高效的搜索引擎都是确保用户满意度和工作效率的关键因素之一。而在搜索引擎领域&#xff0c;Manticore Search 作为一款开源的全文搜索引擎&#xff…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...