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

Leetcode:322. 零钱兑换(C++)

目录

问题描述:

实现代码与解析:

动态规划(完全背包):

原理思路:


问题描述:

        给你一个整数数组 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

实现代码与解析:

动态规划(完全背包):

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){if (dp[j - coins[i]] != INT_MAX){dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

原理思路:

        此题和Leetcode:474. 一和零(C++)_Cosmoshhhyyy的博客-CSDN博客很像,但是区别呢,就是此题求的是最小物品数,dp数组的含义就是装满背包用的最少硬币个数,对于dp数组的初始化,就是非零下标都取最大INT_MAX,因为我们后面要 dp[j] = min(dp[j], dp[j - coins[i]] + 1) 进行比较,如果都取 0 ,那么取 min 的时候就都取 0 了,显然是不对的,初始化为最大才能取到小值,当然  0 下标还是为 0 的,之后就是完全背包遍历了,最后如果dp数组还为初值,说明不能装满,则返回 -1。

相关文章:

Leetcode:322. 零钱兑换(C++)

目录 问题描述&#xff1a; 实现代码与解析&#xff1a; 动态规划&#xff08;完全背包&#xff09;&#xff1a; 原理思路&#xff1a; 问题描述&#xff1a; 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金…...

C经典小游戏之扫雷

编译环境&#xff1a;VS022 目录 1.算法思路 2.代码模块 2.1 game.h 2.2 game.cpp 2.3 test.cpp 3.重点分析 4.金句省身 1.算法思路 主要采用二维数组进行实现&#xff0c;设置两个二维数组&#xff0c;一个打印结果&#xff0c;即为游戏界面显示的效果&#xff0c;一个用…...

第十节 使用设备树插件实现RGB 灯驱动

Linux4.4 以后引入了动态设备树&#xff08;Dynamic DeviceTree&#xff09;&#xff0c;我们这里翻译为“设备树插件”。设备树插件可以理解为主设备树的“补丁”它动态的加载到系统中&#xff0c;并被内核识别。例如我们要在系统中增加RGB 驱动&#xff0c;那么我们可以针对R…...

【LeetCode】公交路线 [H](宽度优先遍历)

815. 公交路线 - 力扣&#xff08;LeetCode&#xff09; 一、题目 给你一个数组 routes &#xff0c;表示一系列公交线路&#xff0c;其中每个 routes[i] 表示一条公交线路&#xff0c;第 i 辆公交车将会在上面循环行驶。 例如&#xff0c;路线 routes[0] [1, 5, 7] 表示第 …...

报表生成器 FastReport .Net 用户指南 2023(十):Band的属性

FastReport .Net是一款全功能的Windows Forms、ASP.NET和MVC报表分析解决方案&#xff0c;使用FastReport .NET可以创建独立于应用程序的.NET报表&#xff0c;同时FastReport .Net支持中文、英语等14种语言&#xff0c;可以让你的产品保证真正的国际性。 FastReport.NET官方版…...

DAMA数据管理知识体系指南之文档和内容管理

第10章 文档和内容管理 10.1 简介 文档和内容管理是对存储在关系数据库以外的信息的采集、存储、访问以及使用的控制活动。文档和内容管理的侧重点在完整性和访问控制上。因此&#xff0c;它与关系数据库的数据操作管理大致相同。由于多数非结构化数据与存储在结构化文件中的…...

C++入门:数据结构

C/C 数组允许定义可存储相同类型数据项的变量&#xff0c;但是结构是 C 中另一种用户自定义的可用的数据类型&#xff0c;它允许您存储不同类型的数据项。结构用于表示一条记录&#xff0c;假设您想要跟踪图书馆中书本的动态&#xff0c;您可能需要跟踪每本书的下列属性&#x…...

C语言实现烟花表白,内含源码!!

虽然现在看烟花有一定难度&#xff0c;但代码式烟花可以随时随地看&#xff01; 烟花的代码很多&#xff0c;实际上是可以用 Python、HTML5 等语言写烟花&#xff0c;但今天主要想和大家分享用C语言写的烟花代码&#xff0c;非常细致和实用。 同学们一定要亲自敲一遍&#xf…...

虚拟机安装CentOS 7(带界面)

目录 一、虚拟机安装CentOS 7&#xff08;带界面&#xff09; 1、打开下好的VMware&#xff0c;点击创建虚拟机 2、下一步 3、点击下一步 4、选择Linux&#xff0c;ContOS7&#xff0c;点击下一步 5、修改虚拟机名称和路径 6、下一步 7、点击自定义硬件 8、设置虚拟机大…...

Java测试——selenium具体操作

selenium的前置准备工作可以参考我之前的博客&#xff1a;Java测试——selenium的安装与使用教程 这篇博客讲解一下selenium的常见操作 先创建driver ChromeDriver driver new ChromeDriver();输入网址 driver.get("https://www.baidu.com");常见操作 查找元素…...

电子器件系列32:逻辑与门芯片74LS11

一、编码规则 先看看这个代码的意思&#xff1a;74LS11 74是一个系列&#xff08;74 表示为工作温度范围&#xff0c;74: 0 ~ 70度。&#xff09; ls的意思就是工艺类型&#xff08;Bipolar(双极)工艺&#xff09; 11是代码 什么是74系列逻辑芯片&#xff1f; - 知乎 什么是…...

LeetCode-101. 对称二叉树

目录题目分析递归法题目来源 101. 对称二叉树 题目分析 首先想清楚&#xff0c;判断对称二叉树要比较的是哪两个节点&#xff0c;要比较的可不是左右节点&#xff01; 对于二叉树是否对称&#xff0c;要比较的是根节点的左子树与右子树是不是相互翻转的&#xff0c;理解这一…...

使用intlinprog求解指派问题MATLAB代码分享

% 输入指派矩阵C [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];f C(:); %生成一个列向量&#xff0c;作为目标函数系数&#xff0c;matlab默认以列排序[m,n] size(C);Aeq zeros(2*n,n*n); %2*n个等式约束&#xff0c;n*n个变量for i 1:n %这里先生成的是后5个…...

Spark On YARN时指定Python版本

坑很多&#xff0c;直接上兼容性最佳的命令&#xff0c;将python包上传到hdfs或者file:/home/xx/(此处无多余的/) # client 模式 $SPARK_HOME/spark-submit \ --master yarn \ --deploy-mode client \ --num-executors 2 \ --conf "spark.yarn.dist.archives<Python包…...

[数据库]库的增删改查

●&#x1f9d1;个人主页:你帅你先说. ●&#x1f4c3;欢迎点赞&#x1f44d;关注&#x1f4a1;收藏&#x1f496; ●&#x1f4d6;既选择了远方&#xff0c;便只顾风雨兼程。 ●&#x1f91f;欢迎大家有问题随时私信我&#xff01; ●&#x1f9d0;版权&#xff1a;本文由[你帅…...

Wine零知识学习1 —— 介绍

一、什么是Wine Wine是“Wine Is Not an Emulator” 的首字母缩写&#xff0c;是一个能够在多种POSIX-compliant操作系统&#xff08;诸如Linux、macOS及BSD等&#xff09;上运行 Windows 应用的兼容层。Wine不像虚拟机或者模拟器那样模仿内部的Windows逻辑&#xff0c;而是將…...

设计模式--建造者模式 builder

设计模式--建造者模式 builder&#xff09;建造者模式简介建造者模式--小例子&#xff08;电脑购买&#xff09;1.产品类2.抽象构建者3.实体构建类4.指导者类5.客户端测试类小结建造者模式简介 建造者模式有四个角色,概念划分如下&#xff1a; Product &#xff1a; 产品类&a…...

终于周末啦,继续来总结一下Python的一些知识点啦

目录 Python概念梳理 常见概念梳理 Python经典判断题 判断题 选择题 Python概念梳理 常见概念梳理 Python中&#xff0c;不仅仅变量的值是可以变化的&#xff0c;类型也是可以随时变化的 1、Python的变量必须初始化否则提示 is not defined 2、if、while中定义的变量在…...

CUDA By Example(八)——流

文章目录页锁定主机内存可分页内存函数页锁定内存函数CUDA流使用单个CUDA流使用多个CUDA流GPU的工作调度机制高效地使用多个CUDA流遇到的问题(未解决)页锁定主机内存 在之前的各个示例中&#xff0c;都是通过 cudaMalloc() 在GPU上分配内存&#xff0c;以及通过标准的C库函数 …...

02- pandas 数据库 (数据库)

pandas 数据库重点: pandas 的主要数据结构: Series (一维数据)与 DataFrame (二维数据)。 pd.DataFrame(data np.random.randint(0,151,size (5,3)), # 生成pandas数据 index [Danial,Brandon,softpo,Ella,Cindy], # 行索引 …...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

使用python进行图像处理—图像滤波(5)

图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值&#xff0c;以达到平滑&#xff08;去噪&#xff09;、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算&#xff0c;…...

DL00871-基于深度学习YOLOv11的盲人障碍物目标检测含完整数据集

基于深度学习YOLOv11的盲人障碍物目标检测&#xff1a;开启盲人出行新纪元 在全球范围内&#xff0c;盲人及视觉障碍者的出行问题一直是社会关注的重点。尽管技术不断进步&#xff0c;许多城市的无障碍设施依然未能满足盲人出行的实际需求。尤其是在复杂的城市环境中&#xff…...

可视化图解算法48:有效括号序列

牛客网 面试笔试 TOP101 | LeetCode 20. 有效的括号 1. 题目 描述 给出一个仅包含字符(,),{,},[和],的字符串&#xff0c;判断给出的字符串是否是合法的括号序列 括号必须以正确的顺序关闭&#xff0c;"()"和"()[]{}"都是合法的括号序列&…...

【Flask】:轻量级Python Web框架详解

什么是Flask&#xff1f; Flask是一个用Python编写的轻量级Web应用框架。它被称为"微框架"(microframework)&#xff0c;因为它核心简单但可扩展性强&#xff0c;不强制使用特定的项目结构或库。Flask由Armin Ronacher开发&#xff0c;基于Werkzeug WSGI工具包和Jin…...