当前位置: 首页 > 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], # 行索引 …...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

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 位数字。 输…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...