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

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 零钱兑换

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

面试篇SpringMVC是什么以及工作原理

1&#xff0c;什么是SpringMVC呢&#xff1f; 它是Spring的一种设计模式&#xff0c;一款框架。 2&#xff0c;MVC分别代表什么&#xff1f; M代表模型即model的缩写&#xff0c;指业务逻辑层模型。V代表视图即View的缩写&#xff0c;指视图层。C则是controller的缩写&#xff…...

jQuery-层级选择器

<!DOCTYPE HTML> <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetUTF-8"> <title>层级选择器</title> <style type"text/css"> …...

【Java数据结构】——第十节(下).选择排序与堆排序

作者简介&#xff1a;大家好&#xff0c;我是未央&#xff1b; 博客首页&#xff1a;未央.303 系列专栏&#xff1a;Java初阶数据结构 每日一句&#xff1a;人的一生&#xff0c;可以有所作为的时机只有一次&#xff0c;那就是现在&#xff01;&#xff01;&#xff01; 文章目…...

45道SQL题目陆续更新

文章目录 学习视频配置环境第一天内连接 外连接第二天第三天 学习视频 学习视频 配置环境 四张表 配置四张表的sql语句 #创建发据库 create database frogdata charsetutf8&#xff1b;use frogdata;# 学生表 Student create table Student( SId varchar(10), Sname var…...

在线PS软件有哪些不错的推荐

许多新的UI设计合作伙伴非常关心在线ps工具的选择。现在市场上有各种各样的ps网页替代工具&#xff0c;数量众多&#xff0c;令人眼花缭乱。本文简要介绍了10个在线PS工具&#xff0c;我相信一定有一个适合你&#xff01; 1.即时设计 即时设计是一款在线 UI 设计工具&#xf…...

Java实现天气预报功能

如果要实现类似百度天气、手机App这样的天气预报功能该如何实现&#xff1f;首先想到的是百度... 背景&#xff1a; 最近公司做了一个项目&#xff0c;天气预报的功能也做上去了&#xff0c;不仅有实时天气、未来7天预报的功能、还有气象预警的功能。 天气包括基本天气、白天夜…...

python循环语句

while循环 Python中&#xff0c;while循环只要在条件&#xff08;表达式&#xff09;为真的情况下&#xff0c;就会一直重复执行相应的循环代码块。 while语句的语法格式如下&#xff1a; while 条件表达式&#xff1a;代码块while语句执行的具体流程为&#xff1a;首先判断…...

多线程基础(一)线程基础信息、synchronized 锁概念

1. 基本概念&#xff1a; 程序&#xff1a; 程序是一些保存在磁盘上的指令的有序集合&#xff0c;是静态的。程序包括&#xff1a;内存资源、IO资源、信号处理等。&#xff08;如&#xff1a;XX.exe&#xff09; 进程&#xff1a; 进程是程序执行的过程&#xff0c;包括了动态…...

JAVA期末考内容知识点的梳理

作者的话 前言&#xff1a;这些都是很基本的&#xff0c;还有很多没有写出来&#xff0c;重点在于考试复习&#xff0c;包括后四章的内容 前面内容请参考JAVA阶段考内容知识点的梳理 一、集合、流 课堂总结1集合 集合概念&#xff1a; 保存和盛装数据的容器&#xff0c;将许多…...

为什么要使用Thrift与Protocol Buffers?

编码数据的格式 程序通常&#xff08;至少&#xff09;使用两种形式的数据&#xff1a; 在内存中&#xff0c;数据保存在对象、结构体、列表、数组、散列表、树等中。 这些数据结构针对 CPU 的高效访问和操作进行了优化&#xff08;通常使用指针&#xff09;。如果要将数据写…...

oa是什么意思?oa系统哪个好用?

一、oa是什么意思 oa&#xff08;Office Automation办公自动化&#xff09;是一种将智能化科技应用于企业管理中的应用系统。它可以通过电脑网络、互联网等技术手段&#xff0c;将企业的各种业务流程、各种业务数据进行集成和处理&#xff0c;将各种业务流程和各种业务数据统一…...

Linq和C# Lambda表达式

什么是Linq 简介 Linq (Language Integrated Query) 是一种语言集成的查询技术&#xff0c;可以在C#和其他.NET语言中使用。Linq允许我们使用一种类SQL的语言来查询数据&#xff0c;这使得代码更加简洁和易于阅读。Linq提供了一种通用的查询接口&#xff0c;可以用于查询各种…...

蓝桥:前端开发笔面必刷题——Day2 数组(三)

文章目录 &#x1f4cb;前言&#x1f3af;两数之和 II&#x1f4da;题目内容✅解答 &#x1f3af;移除元素&#x1f4da;题目内容✅解答 &#x1f3af;有序数组的平方&#x1f4da;题目内容✅解答 &#x1f3af;三数之和&#x1f4da;题目内容✅解答 &#x1f4dd;最后 &#x…...

人工智能专栏第四讲——人工智能的未来展望与机遇

目录 一、人工智能的未来展望 二、人工智能在各领域的应用 三、人工智能的机遇 四、总结...

Unity阴影(Shadow)、Shadowmap

Unity阴影&#xff08;Shadow&#xff09; 在Unity中&#xff0c;阴影&#xff08;Shadow&#xff09;是用于模拟场景中物体之间相互遮挡和光照效果的特性。阴影可以增加场景的真实感&#xff0c;并在视觉上提供深度和空间感。 Unity提供了几种阴影投射和接收的方法和技术&am…...

编程语言的四种错误处理方法,你知道几种?

错误处理是编程的一个基本要素。除非你写的是“hello world”&#xff0c;否则就必须处理代码中的错误。在本文中&#xff0c;我将讨论各种编程语言在处理错误时使用的最常见的四种方法&#xff0c;并分析它们的优缺点。 关注不同设计方案的语法、代码可读性、演变过程、运行效…...

ContOS7单机安装Hadoop

安装Hadoop 1&#xff0c;准备环节 因为Hadoop是由java编写的&#xff0c;所以需要Java的环境支持&#xff0c;作为开发者我们需要安装jdk。 安装jdk的教程http://t.csdn.cn/6qJKg 下载Hadoop的安装包 Hadoop官网&#xff1a;http://hadoop.apache.org/ Hadoop版本下载地…...

抓取动态网页的数据的具体操作方法

抓取动态网页的数据的具体操作方法 动态网页是指在用户交互过程中&#xff0c;网页内容不断更新和变化的网页。抓取动态网页的数据需要了解以下具体操作方法&#xff1a; 使用浏览器开发者工具&#xff1a;在浏览器中打开目标网页后&#xff0c;按下F12键&#xff0c;打开开发…...

Windows 和 Linux 环境下 ProtoBuf 的安装

文章目录 一、ProtoBuf 在 Windows 环境中的安装二、ProtoBuf 在 Linux 环境中的安装 ProtoBuf在GitHub上的下载地址 一、ProtoBuf 在 Windows 环境中的安装 首先选择自己要下载的版本&#xff0c;我选择的是v21.11&#xff1a; 点进去在最下面选择Windows的版本&#xff0…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...