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

Leetcode 322. 零钱兑换(完全背包)

  • Leetcode 322. 零钱兑换(完全背包)
  • 题目
    • 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
    • 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
    • 你可以认为每种硬币的数量是无限的。
    • 1 <= coins.length <= 12
    • 1 <= coins[i] <= 2^31 - 1
    • 0 <= amount <= 10^4
  • 解法
    • 动态规划之完全背包:
    • 定义一维数组 dp,其中 dp[i] 表示组成总金额 i 所需的最少硬币数
    • 初始化 dp 数组,dp[0] 为 0,表示组成金额 0 需要 0 个硬币,dp[1…amount] 初始化为极大值,表示当前无法组成该总金额
    • 遍历硬币数组 coins,对于每种面额的硬币,遍历总金额范围内可以添加该硬币的金额下标。即 dp[j] 不为极大值,说明可以组成 j + coins[i] 金额,此时转移方程为:dp[j + coins[i]] = Math.min(dp[j + coins[i]], dp[j] + 1)
    • 遍历结束后,dp[amount] 如果仍为极大值,则无法组成,返回 -1;否则返回 dp[amount] 表示最少需要的硬币数
    • PS:由于 amount 最多由 amount 个硬币组成,因此初始化极大值只要大于 amount 就可以
  • 代码
    /*** 动态规划之完全背包:* 定义一维数组 dp,其中 dp[i] 表示组成总金额 i 所需的最少硬币数* 初始化 dp 数组,dp[0] 为 0,表示组成金额 0 需要 0 个硬币,dp[1...amount] 初始化为极大值,表示当前无法组成该总金额* 遍历硬币数组 coins,对于每种面额的硬币,遍历总金额范围内可以添加该硬币的金额下标。即 dp[j] 不为极大值,说明可以组成 j + coins[i] 金额,此时转移方程为:dp[j + coins[i]] = Math.min(dp[j + coins[i]], dp[j] + 1)* 遍历结束后,dp[amount] 如果仍为极大值,则无法组成,返回 -1;否则返回 dp[amount] 表示最少需要的硬币数* PS:由于 amount 最多由 amount 个硬币组成,因此初始化极大值只要大于 amount 就可以*/private static int solution(int[] coins, int amount) {// 判空if (amount == 0) {return 0;}if (coins == null || coins.length <= 0) {return -1;}// 定义且初始化 dp 数组int[] dp = new int[amount + 1];Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);// 循环添加每一种硬币int coinsLen = coins.length;int dpLen = dp.length;for (int i = 0; i < coinsLen; i++) {for (int j = 0; j < dpLen - coins[i]; j++) {if (dp[j] < Integer.MAX_VALUE) {dp[j + coins[i]] = Math.min(dp[j + coins[i]], dp[j] + 1);}}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}

相关文章:

Leetcode 322. 零钱兑换(完全背包)

Leetcode 322. 零钱兑换&#xff08;完全背包&#xff09;题目 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&…...

怎么恢复回收站?分享4个宝藏方法!

案例&#xff1a;怎么恢复回收站 【请问大家怎么恢复误删的文件呀&#xff1f;如果回收站被清空了&#xff0c;又应该怎么恢复呢&#xff1f;】 电脑回收站是我们存储被删除文件的地方。但是有时候&#xff0c;我们会不小心把一些重要的文件或者照片误删了。这时候&#xff0…...

大模型混战,最先实现“智慧涌现”的会是谁?

作者 | 曾响铃 文 | 响铃说 几秒钟写出了一篇欢迎词&#xff1b; 小说人物乱入现实&#xff0c;快速创作不重样的故事&#xff1b; 鼠标一点&#xff0c;一封英文工作沟通邮件撰写完成&#xff1b; 准确解出数学应用题&#xff0c;还给出解题步骤&#xff1b; 甚至还能理…...

Powerlink协议在嵌入式linux上的移植和主从站通信(电脑和linux板通信实验)

使用最新的openPOWERLINK 2.7.2源码&#xff0c;业余时间搞定了Powerlink协议在嵌入式linux上的移植和测试&#xff0c;并进行了下电脑和linux开发板之间的通信实验。添加了一个节点配置&#xff0c;跑通了源码中提供的主站和从站的两个demo。这里总结下移植过程分享给有需要的…...

快速理解基本的cookie、session 和 redis

一、Cookie 1、什么是Cookie 1、Cookie实际上是一小段的文本信息&#xff0c;是一种keyvalue形式的字符串。客户端请求服务器&#xff0c;如果服务器需要记录该用户状态&#xff0c;就使用response向客户端浏览器颁发一个Cookie。客户端会把Cookie保存起来。 2、当浏览器再请求…...

STANet代码复现出现的问题

1 IndexError: boolean index did not match indexed array along dimension 0; dimension is 4194304 but corresponding boolean dimension is 65536定位到导致错误的代码&#xff0c;是metric.py&#xff0c;Collect values for Confusion Matrix 收集混淆矩阵的值时出错 …...

Java 中String对象详解

Java语言中的String对象是一个非常常见的数据类型&#xff0c;大多数情况下我们都是在使用String对象来表示字符串类型的数据。Java中的String类是一个final class&#xff0c;它是不可被继承的。本文将对Java中的String对象进行详细全面的描述&#xff0c;包括以下几个方面&am…...

k8s nfs运行问题、etcd问题、calico网络问题

服务器重启后nfs运行问题导致服务不能正常重启 解决办法 在每个节点下使用如下命令进行查看nfs是否正常启动 systemctl status nfs 如果没有启动&#xff0c;则使用如下命令启动&#xff0c;保证三个节点下的nfs都正常启动 systemctl start nfs 再次查看nfs是否正常启动 syst…...

Qt--QString字符串类、QTimer定时器类

目录 1. QString 字符串类 dialog.cpp 2. 容器类 2.1 顺序容器 QList 示例代码&#xff1a; student.h student.cpp dialog.h dialog.cpp 运行结果&#xff1a; 2.2 关联容器 QMap 示例代码&#xff1a; dialog.h dialog.cpp 运行结果&#xff1a; 3. Qt类型 3.1 跨平台数据类型…...

2023.5.13>>Eclipse+exe4j打包Java项目及获取exe所在文件的路径

Eclipseexe4j打包Java项目及获取exe所在文件的路径 1、打包exe文件1.1 打jar包1.2 打包exe2、在程序中获取exe所在路径3、遇到问题4、JDK version和class file version(Class编译版本号)对应关系5、参考文章 1、打包exe文件 1.1 打jar包 右单击项目选择“Export…” 1.2…...

Centos系统的使用基本教程

Centos是一款流行的Linux操作系统&#xff0c;它基于Red Hat Enterprise Linux系统&#xff0c;是一款稳定、可靠、安全的操作系统。本文将介绍Centos系统的基本使用方法&#xff0c;包括安装、命令行操作、软件安装和系统管理等方面的内容。 安装Centos系统 Centos系统可以从…...

IDEA生成ER图、UML类图、时序图、流程图等的插件推荐或独立工具推荐

以下是几个常用的IDEA插件和独立工具&#xff0c;可以用于生成ER图、UML类图、时序图、流程图等&#xff1a; Visual Paradigm (独立工具) Visual Paradigm是一个强大的建模工具&#xff0c;可以生成UML类图、时序图、流程图等。它支持多种语言和框架&#xff0c;包括Java、Spr…...

Python心经(3)

这一节总结点demo和常用知识点 目录 有关字符串格式化打印的 lambda匿名函数&#xff0c;&#xff0c;将匿名函数作为参数传入 文件读写 生成器 python的装饰器 简单的网站代码&#xff1a; 有关三元运算 推导式&#xff1a; 新浪面试题&#xff1a; 有关面向对象里…...

单工,半双工,全双工通讯

对于点对点之间的通信&#xff0c;按照消息传送的方向与时间关系&#xff0c;通信方式可分为单工通信、半双工通信及全双工通信三种。 单工通信 单工通信&#xff08;Simplex Communication&#xff09;是指消息只能单方向传输的工作方式。 在单工通信中&#xff0c;通信的信…...

【2023-05-09】 设计模式(单例,工厂)

2023-05-09 设计模式&#xff08;单例&#xff0c;工厂&#xff09; 单例模式 顾名思义&#xff0c;就是整个系统对外提供的实例有且只有一个 特点&#xff1a; ​ 1、单例类只有一个实例 ​ 2、必须是自己创建唯一实例 ​ 3、必须给所以对象提供这个实例 分类&#xff…...

批量任务导致页面卡死解决方案

需求背景 需要基于高德地图展示海量点位&#xff08;大概几万个&#xff09;&#xff0c;点位样式要自定义&#xff08;创建DOM&#xff09;&#xff0c;虽然使用了聚合点&#xff0c;但初始化时仍需要将几万个点位的DOM结构都创建出来。 这里补充一句&#xff0c;高德地图在2.…...

避免“文献综抄”,5种写作结构助你完成文献综述→

很多作者可能有过这样的体验&#xff1a;读了很多文献&#xff0c;但在写综述的时候总感觉不像是在写文献综述&#xff0c;更像在写文献总结 如果引用方面不注意&#xff0c;甚至会成为文献综抄。 那么&#xff0c;你可以参考下我们整理的以下资料哦~ 01 文献总结和文献综述的…...

Java异常和反射

JAVA 异常分类及处理 概念 } final Entry<K,V> getEntryUsingComparator(Object key) { K k (K) key; // 获取该 TreeMap 的 comparator Comparator<? super K> cpr comparator; if (cpr ! null) { // 从根节点开始 Entry<K,V> p …...

Accesss数据库的那点事

Accesss数据库的那点事 1.Access的简介 Access&#xff08;全称为Microsoft Access&#xff09;是一个关系型数据库管理系统&#xff08;RDBMS&#xff09;。它是由微软公司开发的数据库软件&#xff0c;用于创建、管理和操作数据库应用程序。 Access提供了一个可视化的开发环…...

网络基础学习:osi网络七层模型

osi网络七层模型 什么是OSI&#xff0c;什么是ISO?为什么ISO要提出OSI网络七层模型&#xff1f;OSI七层的划分以及具体内容第七层 应用层第六层 表示层第五层 会话层第四层 传输层第三层 网络层第二层 数据链路层第一层 物理层 每一层与设备的对应关系 什么是OSI&#xff0c;什…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

七、数据库的完整性

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

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

Tauri2学习笔记

教程地址&#xff1a;https://www.bilibili.com/video/BV1Ca411N7mF?spm_id_from333.788.player.switch&vd_source707ec8983cc32e6e065d5496a7f79ee6 官方指引&#xff1a;https://tauri.app/zh-cn/start/ 目前Tauri2的教程视频不多&#xff0c;我按照Tauri1的教程来学习&…...

简单介绍C++中 string与wstring

在C中&#xff0c;string和wstring是两种用于处理不同字符编码的字符串类型&#xff0c;分别基于char和wchar_t字符类型。以下是它们的详细说明和对比&#xff1a; 1. 基础定义 string 类型&#xff1a;std::string 字符类型&#xff1a;char&#xff08;通常为8位&#xff09…...

MLP实战二:MLP 实现图像数字多分类

任务 实战&#xff08;二&#xff09;&#xff1a;MLP 实现图像多分类 基于 mnist 数据集&#xff0c;建立 mlp 模型&#xff0c;实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入&#xff0c;可视化图形数字&#xff1b; 2、完成数据预处理&#xff1a;图像数据维度转换与…...