LeetCode322. 零钱兑换(2024冬季每日一题 28)
给你一个整数数组 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 < = c o i n s . l e n g t h < = 12 1 <= coins.length <= 12 1<=coins.length<=12
1 < = c o i n s [ i ] < = 2 31 − 1 1 <= coins[i] <= 2^{31} - 1 1<=coins[i]<=231−1
0 < = a m o u n t < = 1 0 4 0 <= amount <= 10^4 0<=amount<=104
思路:动态规划
- 定义 f[i] 为组成金额 i 所需最少的硬币数量
- 枚举 组成金额为 i 所需的硬币,最后一个硬币 j
- 如果最后一个金币是 j,则当前硬币数量 f[i] = f[i - coins[j]] + 1
- 所以有状态转移方程:f[i] = min(f[i], f[i - coins[j]] + 1)
class Solution {
public:int f[10010];int coinChange(vector<int>& coins, int amount) {memset(f, 0x3f, sizeof f);f[0] = 0;int n = coins.size();for(int i = 1; i <= amount; i++){for(int j = 0; j < n; j++){if(coins[j] <= i){f[i] = min(f[i], f[i - coins[j]] + 1);}}}return f[amount] > 1e4 ? -1: f[amount];}
};
相关文章:
LeetCode322. 零钱兑换(2024冬季每日一题 28)
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示…...
Unix、GNU、BSD 风格中 ps 参数的区别
注:本文为“不同风格中 ps 命令参数的区别”相关文章合辑。 未去重。 BSD 风格和 UNIX 风格中 ps 参数的区别 作者:Daniel Stori 译者:LCTT Name1e5s | 2017-06-17 10:53 One Last Question ps aux 以及 ps -elf 都是查看进程的方式&…...
单片机读写内部flash实现断电数据存储
在单片机编程中,读写内部Flash存储器是一种常见的方法来实现断电数据存储。这里以STM32系列单片机为例,展示如何通过HAL库进行简单的内部Flash读写操作。 以下是一个完整的示例代码,展示了如何擦除、写入和读取内部Flash中的数据。请注意&am…...
注意力机制介绍
注意力机制介绍 1.注意力机制由来,以及解决什么问题2.什么是注意力机制3.注意力机制分类及如何实现3.1 Soft Attention(常见):软注意3.1.1普通Encoder-Decoder框架3.1.2加入Attention的Encoder-Decoder框架3.1.3如何理解注意力概率分布3.1.4 Attention机制本质思想 3.2 Hard At…...
爬虫运行后数据如何存储?
爬虫运行后获取的数据可以存储在多种不同的存储系统中,具体选择取决于数据的规模、查询需求以及应用场景。以下是一些常见的数据存储方法: 1. 文件系统 对于小型项目或临时数据存储,可以直接将数据保存到本地文件中。常见的文件格式包括&…...
C# 自动自定义截图的内容
C# 自动自定义截图的内容 using System; using System.Drawing; using System.Runtime.InteropServices; class Program {[DllImport("user32.dll")]public static extern IntPtr GetDesktopWindow();[DllImport("user32.dll")]public static extern IntP…...
Java的Stream流:文件处理、排序与串并行流的全面指南
Java的Stream流:文件处理、排序与串并行流的全面指南 Java 8 引入了 Stream API,这是一个用于处理集合数据的强大工具,它提供了一种声明式的方式来进行聚合操作。Stream 不是一个数据结构,而是一种对数据进行操作的抽象ÿ…...
[Maven]下载安装、使用与简介
很多框架的下载使用的流程和思路是差不多的,这里以maven做详细介绍。 下载安装与配置变量 下载 首先,我们要使用maven,必须先下载它的相关文件。想要下载,我们可以直接搜索maven。找到它的官网。这里不绕弯子,直接给出…...
056 WXML+ WXSS+PHP+LW+校园配送商城微信小程序开发与设计 源码 文档 全套资料
校园配送微信小程序 1.项目描述2. 1.绪论3.项目技术与功能4.界面展示5.源码获取 1.项目描述 摘 要 近几年来,随着互联网和电子商务的快速发展和普及,改变了人们日常消费模式。尤其是移动互联网的相结合,使得人们日常生活中更多的是通过手机移…...
Python 在同一/或不同PPT文档之间复制幻灯片
复制幻灯片可以帮助我们更高效地完成工作,节省大量的制作时间。通过复制现有的幻灯片,可以快速创建新的演示文稿,而无需重新设计板式样式等。此外,复制幻灯片还可以帮助我们保持内容的一致性,使整个PPT演示文稿看起来更…...
C#生成CSR(CertificateSigningRequest)和密钥
使用C#原生生成CSR(CertificateSigningRequest)和密钥。 生成的私钥妥善保存,丢失无法找回。 调用 var contents X509Helper.SigningRequestHelper.CreateSigningRequest("yourdomain.com", ["*.yourdomain.com"], X509Helper.AsymmetricAl…...
Docker 安装 Oracle创建表空间并导入数据库
一、Docker 安装Oracle 1、检查docker 版本 2、docker 下载镜像 3、 docker启动容器 4、 进入容器内部 5、安装成功,使用客户端工具连接 二、创建数据库用户与表空间 1、查询数据库文件位置 2、创建表空间 3、创建用户 4、设置权限 三、导出数据库DMP …...
elementui table子级tree懒加载bug
1. 删除子级刷新列表子级依然显示 2.更新状态子级列表未刷新 3.编辑子级后刷新页面显示状态未变更 el-table 树表格load源码 首先,load可以执行,但是只剩一个子节点就有问题,那么就直接可以定位bug在load方法里: 文件路径&am…...
AI与低代码技术融合:如何加速企业智能化应用开发?
引言 随着全球数字化转型的步伐加快,企业在智能化应用开发方面面临着前所未有的挑战和机遇。传统的软件开发方式往往需要大量的技术人员、时间和资源,而在瞬息万变的市场环境中,这种模式显得效率低下且难以满足企业快速迭代和创新的需求。 与…...
【C#】新建窗体文件,Form、UserControl
从用途、功能性和架构方面进行描述。 1. 继承自 Form 的窗体(通常是窗口): 在 C# 中,Form 是用于创建应用程序的主窗口或对话框窗口的类。当您继承自 Form 时,您创建的是一个完整的窗口,可以显示内容、与…...
ansible学习笔记之02command模块与shell模块
目录 1、概述 2、模块介绍 2.1 command模块 2.2 shell模块 2.3 小结 3、实验 3.1 测试ls命令 3.2 测试环境变量 3.3 测试操作符">" 1、概述 本文介绍ansible的command模块与shell模块,并通过实验比对两个模块的异同。 2、模块介绍 2.1…...
在Docker中部署禅道,亲测可用
1、确保centos中已安装docker docker -v 2、启动docker systemctl start docker 3、可设置docker开机启动 systemctl enable docker.service 4、获取最新版禅道开源版镜像 docker pull idoop/zentao 5、运行镜像生成禅道容器【创建 /data/www /data/data 目录】 doc…...
C++(十二)
前言: 本文将进一步讲解C中,条件判断语句以及它是如何运行的以及内部逻辑。 一,if-else,if-else语句。 在if语句中,只能判断两个条件的变量,若想实现判断两个以上条件的变体,就需要使用if-else,if-else语…...
【数学建模】线性规划问题及Matlab求解
问题一 题目: 求解下列线性规划问题 解答: 先将题目中求最大值转化为求最小值,则有 我们就可以得到系数列向量: 我们对问题中所给出的不等式约束进行标准化则得到了 就有不等式约束条件下的变系数矩阵和常系数矩阵分别为: 等式…...
【JavaWeb后端学习笔记】Spring全局异常处理器
在程序运行时,不可避免的会出现异常。在三层开发架构中,当Mapper层出现异常、如果不进行处理会抛给Service层,如果Service层也不处理则会抛给Controller层,通常Controller层有许多接口,如果对每个接口单独处理异常&…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析
LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...
