LeetCode 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数组以及下标的含义
dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
确定递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],
那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;
确定遍历顺序
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
在代码中,if(dp[j - coins[i]] != INT_MAX)表示如果如果dp[j - coins[i]]是初始值则跳过
说明没有可以凑成j-conis[i]的结果
最后先判断dp[amount]是否为初始化的最大值,如果是,说明没有结果
class Solution {
public:int track(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);}}}return dp[amount];}
};int main() {vector<int> coins = { 1,2,5 };int amount = 11;Solution ss;cout<<ss.track(coins,amount)<<endl;return 0;
}
相关文章:
LeetCode 322 零钱兑换
题目: 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。你可以认为每种硬币的数量…...
面试篇SpringMVC是什么以及工作原理
1,什么是SpringMVC呢? 它是Spring的一种设计模式,一款框架。 2,MVC分别代表什么? M代表模型即model的缩写,指业务逻辑层模型。V代表视图即View的缩写,指视图层。C则是controller的缩写ÿ…...
jQuery-层级选择器
<!DOCTYPE HTML> <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetUTF-8"> <title>层级选择器</title> <style type"text/css"> …...
【Java数据结构】——第十节(下).选择排序与堆排序
作者简介:大家好,我是未央; 博客首页:未央.303 系列专栏:Java初阶数据结构 每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!! 文章目…...
45道SQL题目陆续更新
文章目录 学习视频配置环境第一天内连接 外连接第二天第三天 学习视频 学习视频 配置环境 四张表 配置四张表的sql语句 #创建发据库 create database frogdata charsetutf8;use frogdata;# 学生表 Student create table Student( SId varchar(10), Sname var…...
在线PS软件有哪些不错的推荐
许多新的UI设计合作伙伴非常关心在线ps工具的选择。现在市场上有各种各样的ps网页替代工具,数量众多,令人眼花缭乱。本文简要介绍了10个在线PS工具,我相信一定有一个适合你! 1.即时设计 即时设计是一款在线 UI 设计工具…...
Java实现天气预报功能
如果要实现类似百度天气、手机App这样的天气预报功能该如何实现?首先想到的是百度... 背景: 最近公司做了一个项目,天气预报的功能也做上去了,不仅有实时天气、未来7天预报的功能、还有气象预警的功能。 天气包括基本天气、白天夜…...
python循环语句
while循环 Python中,while循环只要在条件(表达式)为真的情况下,就会一直重复执行相应的循环代码块。 while语句的语法格式如下: while 条件表达式:代码块while语句执行的具体流程为:首先判断…...
多线程基础(一)线程基础信息、synchronized 锁概念
1. 基本概念: 程序: 程序是一些保存在磁盘上的指令的有序集合,是静态的。程序包括:内存资源、IO资源、信号处理等。(如:XX.exe) 进程: 进程是程序执行的过程,包括了动态…...
JAVA期末考内容知识点的梳理
作者的话 前言:这些都是很基本的,还有很多没有写出来,重点在于考试复习,包括后四章的内容 前面内容请参考JAVA阶段考内容知识点的梳理 一、集合、流 课堂总结1集合 集合概念: 保存和盛装数据的容器,将许多…...
为什么要使用Thrift与Protocol Buffers?
编码数据的格式 程序通常(至少)使用两种形式的数据: 在内存中,数据保存在对象、结构体、列表、数组、散列表、树等中。 这些数据结构针对 CPU 的高效访问和操作进行了优化(通常使用指针)。如果要将数据写…...
oa是什么意思?oa系统哪个好用?
一、oa是什么意思 oa(Office Automation办公自动化)是一种将智能化科技应用于企业管理中的应用系统。它可以通过电脑网络、互联网等技术手段,将企业的各种业务流程、各种业务数据进行集成和处理,将各种业务流程和各种业务数据统一…...
Linq和C# Lambda表达式
什么是Linq 简介 Linq (Language Integrated Query) 是一种语言集成的查询技术,可以在C#和其他.NET语言中使用。Linq允许我们使用一种类SQL的语言来查询数据,这使得代码更加简洁和易于阅读。Linq提供了一种通用的查询接口,可以用于查询各种…...
蓝桥:前端开发笔面必刷题——Day2 数组(三)
文章目录 📋前言🎯两数之和 II📚题目内容✅解答 🎯移除元素📚题目内容✅解答 🎯有序数组的平方📚题目内容✅解答 🎯三数之和📚题目内容✅解答 📝最后 &#x…...
人工智能专栏第四讲——人工智能的未来展望与机遇
目录 一、人工智能的未来展望 二、人工智能在各领域的应用 三、人工智能的机遇 四、总结...
Unity阴影(Shadow)、Shadowmap
Unity阴影(Shadow) 在Unity中,阴影(Shadow)是用于模拟场景中物体之间相互遮挡和光照效果的特性。阴影可以增加场景的真实感,并在视觉上提供深度和空间感。 Unity提供了几种阴影投射和接收的方法和技术&am…...
编程语言的四种错误处理方法,你知道几种?
错误处理是编程的一个基本要素。除非你写的是“hello world”,否则就必须处理代码中的错误。在本文中,我将讨论各种编程语言在处理错误时使用的最常见的四种方法,并分析它们的优缺点。 关注不同设计方案的语法、代码可读性、演变过程、运行效…...
ContOS7单机安装Hadoop
安装Hadoop 1,准备环节 因为Hadoop是由java编写的,所以需要Java的环境支持,作为开发者我们需要安装jdk。 安装jdk的教程http://t.csdn.cn/6qJKg 下载Hadoop的安装包 Hadoop官网:http://hadoop.apache.org/ Hadoop版本下载地…...
抓取动态网页的数据的具体操作方法
抓取动态网页的数据的具体操作方法 动态网页是指在用户交互过程中,网页内容不断更新和变化的网页。抓取动态网页的数据需要了解以下具体操作方法: 使用浏览器开发者工具:在浏览器中打开目标网页后,按下F12键,打开开发…...
Windows 和 Linux 环境下 ProtoBuf 的安装
文章目录 一、ProtoBuf 在 Windows 环境中的安装二、ProtoBuf 在 Linux 环境中的安装 ProtoBuf在GitHub上的下载地址 一、ProtoBuf 在 Windows 环境中的安装 首先选择自己要下载的版本,我选择的是v21.11: 点进去在最下面选择Windows的版本࿰…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
