代码随想录 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 ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。…...
【图的应用二:最短路径】- 用 C 语言实现迪杰斯特拉算法和弗洛伊德算法
目录 一、最短路径 二、迪杰斯特拉算法 三、弗洛伊德算法 一、最短路径 假若要在计算机上建立一个交通咨询系统,则可以采用图的结构来表示实际的交通网络。如下图所示,图中顶点表示城市,边表示城市间的交通联系。 这个咨询系统可以回答旅…...
Qt之判断一个点是否在多边形内部(射线法)
算法思想: 以被测点Q为端点,向任意方向作射线(一般水平向右作射线),统计该射线与多边形的交点数。如果为奇数,Q在多边形内;如果为偶数,Q在多边形外。计数的时候会有一些特殊情况。这种方法适用于任意多边形,不需要考虑精度误差和多边形点给出的顺序,时间复杂度为O(n)…...
压力测试过程中内存溢出(堆溢出、栈溢出、持久代溢出)情况如何解决
在压力测试过程中,可能会遇到内存溢出的问题,其中常见的包括堆内存溢出、栈内存溢出和持久代溢出。解决这类问题需要首先理解各种内存溢出的原因和特点。 堆内存溢出:这种情况通常发生在稳定性压测一段时间后,系统报错࿰…...
【工业智能】音频信号相关场景
【工业智能】音频信号相关场景 DcaseDcase introduction:dcase2024有10个主题的任务: ASD硬件设备产品商 方法制造业应用场景 zenodo音频事件检测 与计算机视觉CV相对应,计算机听觉computer audition,简称CA。 Dcase 这里推荐一个…...
(PC+WAP)装修设计公司网站模板 家装公司网站源码下载
(PCWAP)装修设计公司网站模板 家装公司网站源码下载 PbootCMS内核开发的网站模板,该模板适用于装修设计、家装公司类等企业,当然其他行业也可以做,只需要把文字图片换成其他行业的即可; PCWAP,同一个后台,…...
使用opencv实现图像中几何图形检测
1 几何图形检测介绍 1.1 轮廓(contours) 什么是轮廓,简单说轮廓就是一些列点相连组成形状、它们拥有同样的颜色、轮廓发现在图像的对象分析、对象检测等方面是非常有用的工具,在OpenCV 中使用轮廓发现相关函数时候要求输入图像是二值图像,这…...
补题与周总结:leetcode第 376 场周赛
文章目录 复盘与一周总结2967. 使数组成为等数数组的最小代价(中位数贪心 回文数判断)2968. 执行操作使频率分数最大(中位数贪心 前缀和 滑窗) 复盘与一周总结 wa穿了第3题,赛时其实想到了思路:中位数贪心…...
js指纹库,可跟踪用户唯一性
fingerprintjs官网 资料: Browserleaks - Check your browser for privacy leaks...
Shell三剑客:awk(内部变量)
一、$0 :完整的输入记录 [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虚拟机(JVM)中,每个线程在执行一个方法时都会创建一个栈帧(Stack Frame),栈帧中包含了方法的运行时数据。栈帧通常包括局部变量表、操作数栈、动态链接、方法返回地址等部分。 动态链接 动态链接&a…...
Leetcode 55 跳跃游戏
题意理解: 非负整数数组 nums, 最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 需要跳到nums最后一个元素即为成功。 目标:是否能够跳到最后一个元素。 解题思路: 使用贪心算法来解题,需要理解…...
构建陪诊预约系统:技术实战指南
在医疗科技的飞速发展中,陪诊预约系统的应用为患者和陪诊人员提供了更为便捷和贴心的服务。本文将带领您通过技术实现,构建一个简单而实用的陪诊预约系统,以提升医疗服务的效率和用户体验。 技术栈选择 在开始之前,我们需要选择…...
windows和linux将文件删除至回收站【C++】【Go】语言实现
目录 C Windows平台 Linux平台 开平台,代码合并 Go 实现步骤 Go语言实现示例 go单独的windows版本实现 代码解释 C 在C中,将文件移动到回收站的实现在Linux和Windows平台上是不同的。首先,我会为你提供在Windows平台上实现的代码示例…...
10 Vue3中v-html指令的用法
概述 v-html主要是用来渲染富文本内容,比如评论信息,新闻信息,文章信息等。 v-html是一个特别不安全的指令,因为它会将文本以HTML的显示进行渲染,一旦文本里面包含一些恶意的js代码,可能会导致整个网页发…...
华为数通方向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,创建镜像文件前准备 # 使用基础镜像FROM alpine:latest# 设置工作目录WORKDIR /app# 复制应用程序文件到镜像中COPY . .# 暴露容器的端口 不会自动将容器的端口映射到宿主机上 docker run -d -p <宿主机端口>:7080 <镜像名称>EXPOSE 7080# 定义容器启…...
Centos 8.5 Oracle12c安装
由于多次安装踩坑,所以本次写了一份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中发现了一个被归类为关键的漏洞,该漏洞在8.5.4(Application Server Soft ware)以下。受影响的是组…...
s2-pro语音合成教程:支持数字/单位/英文缩写智能朗读技巧
s2-pro语音合成教程:支持数字/单位/英文缩写智能朗读技巧 1. 快速了解s2-pro语音合成 s2-pro是Fish Audio开源的专业级语音合成模型镜像,它能将文本转换为自然流畅的语音。这个工具特别适合需要语音播报、有声读物制作、视频配音等场景的用户。 与普通…...
League-Toolkit:提升英雄联盟游戏体验的开源工具集
League-Toolkit:提升英雄联盟游戏体验的开源工具集 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是基…...
进阶篇第5节:共享内存(三)——实战:优化矩阵乘法(Tiling技术)
第二篇进阶篇第5节:共享内存(三)——实战:优化矩阵乘法(Tiling技术) 从朴素到分块,从分块到极致——矩阵乘法的优化之路,就是CUDA性能优化的缩影 写在前面 矩阵乘法是CUDA优化中最经典的案例,没有之一。在筑基篇,我们实现了朴素版本和基础分块版本,性能从 252 GFLO…...
橄榄菜芝士焗三文鱼配脆米饼:潮汕咸香与海洋鲜美的跨界狂想
潮汕人家的厨房里,总有一罐橄榄菜。乌黑油亮,咸香醇厚,是白粥的最佳伴侣,也是蒸鱼炒菜的秘武器。而深海里的三文鱼,肥美丰腴,油脂均匀,是西餐的宠儿。当潮汕的咸香遇见西式的丰腴,再…...
2026论文降重神器盘点!毕业论文“AIGC痕迹”怎么破?
【CSDN技术引言:拒绝“开源背调”式的学术翻车】 哈喽各位同行和科研圈的战友们。最近后台私信快炸了,今年这届硕博生仿佛遭遇了“灭顶之灾”。某985高校前天出炉的抽检结果直接把大家看傻了:明明自己逐字逐句手敲的论文,知网查重…...
程序员转行学习 AI 大模型: 提示词工程 | 附精选学习资料
本文是程序员转行学习AI大模型的第12个核心知识点笔记,笔记后附精选的提示词工程学习资料。 当前阶段:还在学习知识点,由点及面,从 0 到 1 搭建 AI 大模型知识体系中。 系列更新,关注我,后续会持续记录分享…...
C# 操作XML
https://blog.csdn.net/2609_95039045/article/details/157469812?fromshareblogdetail&sharetypeblogdetail&sharerId157469812&sharereferPC&sharesourcem0_68206177&sharefromfrom_link 这个写的好 https://blog.csdn.net/lizhenxiqnmlgb/article/det…...
I-Lang SEO实战部署:用结构化协议让Google的AI爬虫读懂你的网页
前言: 我们用I-Lang的结构化方法论做SEO,一个全新的英文商业站,七天打进Google搜索第一页。这篇文章把具体方法公开。 一、前提:Google的爬虫已经是AI了 2024年之后,Google的搜索排名算法发生了根本性变化。Googlebot…...
PostgreSQL 冻结(Freeze)机制深度解析
PostgreSQL 冻结(Freeze)机制深度解析一、为什么需要冻结 1.1 事务 ID 的本质 PostgreSQL 用 32 位无符号整数表示事务 ID(XID),范围 0 ~ 2^32-1(约 42 亿)。 其中有三个特殊 XID:XI…...
效率直接起飞!盘点2026年全民喜爱的的AI论文写作工具
一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂的AI论文写作工具,实测提速效果惊人,覆盖选题、文献、写作、降重、排版全流程,让你高效搞定论文不再难。 一、全流程王者:一站式搞定论文全链路(一天定稿首选&…...
