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

代码随想录 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

解题思路
本题是完全背包问题,用dp[j]表示组合和为j的最少个数,可以确定递推公式为dp[j]=min(dp[j-coins[i]]+1, dp[j]). 初值dp[0]=0.最后返回dp[amount]。

代码实现

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-coins[i]]+1, dp[j]);}}}if (dp[amount]==INT_MAX) {return -1;}return dp[amount];}
};

相关文章:

代码随想录 322. 零钱兑换

题目 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。 你可以认为每种硬币的数量是无限的。…...

【图的应用二:最短路径】- 用 C 语言实现迪杰斯特拉算法和弗洛伊德算法

目录 一、最短路径 二、迪杰斯特拉算法 三、弗洛伊德算法 一、最短路径 假若要在计算机上建立一个交通咨询系统&#xff0c;则可以采用图的结构来表示实际的交通网络。如下图所示&#xff0c;图中顶点表示城市&#xff0c;边表示城市间的交通联系。 这个咨询系统可以回答旅…...

Qt之判断一个点是否在多边形内部(射线法)

算法思想: 以被测点Q为端点,向任意方向作射线(一般水平向右作射线),统计该射线与多边形的交点数。如果为奇数,Q在多边形内;如果为偶数,Q在多边形外。计数的时候会有一些特殊情况。这种方法适用于任意多边形,不需要考虑精度误差和多边形点给出的顺序,时间复杂度为O(n)…...

压力测试过程中内存溢出(堆溢出、栈溢出、持久代溢出)情况如何解决

在压力测试过程中&#xff0c;可能会遇到内存溢出的问题&#xff0c;其中常见的包括堆内存溢出、栈内存溢出和持久代溢出。解决这类问题需要首先理解各种内存溢出的原因和特点。 堆内存溢出&#xff1a;这种情况通常发生在稳定性压测一段时间后&#xff0c;系统报错&#xff0…...

【工业智能】音频信号相关场景

【工业智能】音频信号相关场景 DcaseDcase introduction&#xff1a;dcase2024有10个主题的任务&#xff1a; ASD硬件设备产品商 方法制造业应用场景 zenodo音频事件检测 与计算机视觉CV相对应&#xff0c;计算机听觉computer audition&#xff0c;简称CA。 Dcase 这里推荐一个…...

(PC+WAP)装修设计公司网站模板 家装公司网站源码下载

(PCWAP)装修设计公司网站模板 家装公司网站源码下载 PbootCMS内核开发的网站模板&#xff0c;该模板适用于装修设计、家装公司类等企业&#xff0c;当然其他行业也可以做&#xff0c;只需要把文字图片换成其他行业的即可&#xff1b; PCWAP&#xff0c;同一个后台&#xff0c…...

使用opencv实现图像中几何图形检测

1 几何图形检测介绍 1.1 轮廓(contours) 什么是轮廓&#xff0c;简单说轮廓就是一些列点相连组成形状、它们拥有同样的颜色、轮廓发现在图像的对象分析、对象检测等方面是非常有用的工具&#xff0c;在OpenCV 中使用轮廓发现相关函数时候要求输入图像是二值图像&#xff0c;这…...

补题与周总结:leetcode第 376 场周赛

文章目录 复盘与一周总结2967. 使数组成为等数数组的最小代价&#xff08;中位数贪心 回文数判断&#xff09;2968. 执行操作使频率分数最大&#xff08;中位数贪心 前缀和 滑窗&#xff09; 复盘与一周总结 wa穿了第3题&#xff0c;赛时其实想到了思路&#xff1a;中位数贪心…...

js指纹库,可跟踪用户唯一性

fingerprintjs官网 资料&#xff1a; Browserleaks - Check your browser for privacy leaks...

Shell三剑客:awk(内部变量)

一、$0 &#xff1a;完整的输入记录 [rootlocalhost ~]# awk -F: {print $0} passwd.txt root:x:0:0:root:/root:/bin/bash bin:x:1:1:bin:/bin:/sbin/nologin daemon:x:2:2:daemon:/sbin:/sbin/nologin adm:x:3:4:adm:/var/adm:/sbin/nologin lp:x:4:7:lp:/var/spool/lpd:/s…...

JVM中的虚拟机栈的动态链接部分存放到底是什么

在Java虚拟机&#xff08;JVM&#xff09;中&#xff0c;每个线程在执行一个方法时都会创建一个栈帧&#xff08;Stack Frame&#xff09;&#xff0c;栈帧中包含了方法的运行时数据。栈帧通常包括局部变量表、操作数栈、动态链接、方法返回地址等部分。 动态链接 动态链接&a…...

Leetcode 55 跳跃游戏

题意理解&#xff1a; 非负整数数组 nums, 最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 需要跳到nums最后一个元素即为成功。 目标&#xff1a;是否能够跳到最后一个元素。 解题思路&#xff1a; 使用贪心算法来解题&#xff0c;需要理解…...

构建陪诊预约系统:技术实战指南

在医疗科技的飞速发展中&#xff0c;陪诊预约系统的应用为患者和陪诊人员提供了更为便捷和贴心的服务。本文将带领您通过技术实现&#xff0c;构建一个简单而实用的陪诊预约系统&#xff0c;以提升医疗服务的效率和用户体验。 技术栈选择 在开始之前&#xff0c;我们需要选择…...

windows和linux将文件删除至回收站【C++】【Go】语言实现

目录 C Windows平台 Linux平台 开平台&#xff0c;代码合并 Go 实现步骤 Go语言实现示例 go单独的windows版本实现 代码解释 C 在C中&#xff0c;将文件移动到回收站的实现在Linux和Windows平台上是不同的。首先&#xff0c;我会为你提供在Windows平台上实现的代码示例…...

10 Vue3中v-html指令的用法

概述 v-html主要是用来渲染富文本内容&#xff0c;比如评论信息&#xff0c;新闻信息&#xff0c;文章信息等。 v-html是一个特别不安全的指令&#xff0c;因为它会将文本以HTML的显示进行渲染&#xff0c;一旦文本里面包含一些恶意的js代码&#xff0c;可能会导致整个网页发…...

华为数通方向HCIP-DataCom H12-831题库(多选题:181-200)

第181题 如图所示,R1、R2、R3、R4都部署为SPF区域0,链路的cost值如图中标识。R1、R2R3、R4的Loopback0通告入OSPF。R1、R2、R3与R4使用Loopback0作为连接接口,建立BGP对等体关系,其中R4为RR设备,R1、R2、R3是R4的客户端。当R4的直连地址172.20,1,4/32通告入BGP后,以下关R…...

DC-磁盘管理

2023年全国网络系统管理赛项真题 模块B-Windows解析 题目 在DC2上安装及配置软RAID 5。在安装好的DC2虚拟机中添加三块10G虚拟磁盘。组成RAID 5,磁盘分区命名为卷标H盘:Raid5。手动测试破坏一块磁盘,做RAID磁盘修复,确认RAID 5配置完毕。配置步骤 关闭虚拟机,添加3块10G磁…...

使用Docker运行镜像文件与设置端口

1&#xff0c;创建镜像文件前准备 # 使用基础镜像FROM alpine:latest# 设置工作目录WORKDIR /app# 复制应用程序文件到镜像中COPY . .# 暴露容器的端口 不会自动将容器的端口映射到宿主机上 docker run -d -p <宿主机端口>:7080 <镜像名称>EXPOSE 7080# 定义容器启…...

Centos 8.5 Oracle12c安装

由于多次安装踩坑&#xff0c;所以本次写了一份12c安装的完整版。可以直接使用。 一、安装数据库基本信息 名称 值 主机名 database 操作系统 CentOS Linux release 8.5.2111 Oracle用户名/密码 oracle Oracle 版本 12c Enterprise Edition Release 12.2.0.1.0 oracle…...

Apache Tomcat httpoxy 安全漏洞 CVE-2016-5388 已亲自复现

Apache Tomcat httpoxy 安全漏洞 CVE-2016-5388 已亲自复现 漏洞名称漏洞描述影响版本 漏洞复现环境搭建漏洞利用 修复建议总结 漏洞名称 漏洞描述 在Apache Tomcat中发现了一个被归类为关键的漏洞&#xff0c;该漏洞在8.5.4(Application Server Soft ware)以下。受影响的是组…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...