【LeetCode】【算法】322. 零钱兑换

LeetCode 322. 零钱兑换

题目

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回-1。
你可以认为每种硬币的数量是无限的。
示例:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

思路

思路:动态规划,dp[]数组表示组成金额i需要的最少硬币个数

  1. 数组初始化:Arrays.fill(dp, amount + 1); 相当于给一个最大值,便于后面比较得到最少硬币枚数。dp[0]=0,组成金额0只需要0枚硬币
  2. 嵌套循环:
    I. 第一个循环for(int i=1; i<amount+1; i++)从金额1~金额i,最少的硬币数量
    II. 第二个循环for (int coin:coins),假设使用该面额的硬币,能否组成目标金额。里面的条件是if(coin <= i),因为如果coin>i那么这枚硬币肯定用不上
    在if语句中,dp[i]=Math.min(dp[i-coin]+1,dp[i]),这个递推式的意思是说:如果使用coin的话,此时硬币数量就=1+金额(i-coin)的最少硬币数量,看看dp[i]本身和dp[i-coin]+1哪个更小。
  3. return dp[amount] > amount ? -1 : dp[amount]; 也就是如果dp[amount]没有变化,那就表示没有解,否则返回解

结果

class Solution {public int coinChange(int[] coins, int amount) {if (amount == 0) return 0;// 贪心 -> 不可行,因为最优解未必通过贪心结果组成。如果贪心最大面值的硬币,结果可能是由部分小硬币组成的(因为大硬币无法组成目标面额)int[] dp = new int[amount + 1]; // 动态规划数组表示组成目标金额需要几枚硬币// 初始化dp数组Arrays.fill(dp, amount + 1);dp[0] = 0; // 如果组成金额0需要0枚硬币for (int i = 1; i < amount + 1; i++) {for (int coin : coins) { // 每个面额下的硬币if (coin <= i){ // 如果硬币面额 < 当前所需组成的amount// 要么使用coin:此时硬币数量=1+(目标amount-指定面额)硬币数量// 要么不用coin:此时硬币数量=目标amount硬币数量dp[i] = Math.min(dp[i - coin] + 1, dp[i]);}}}return dp[amount] > amount ? -1 : dp[amount];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/464936.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

任务中心全新升级,新增分享接口文档功能,MeterSphere开源持续测试工具v3.4版本发布

2024年11月5日&#xff0c;MeterSphere开源持续测试工具正式发布v3.4版本。 在这一版本中&#xff0c;系统设置方面&#xff0c;任务中心支持实时查看系统即时任务与系统后台任务&#xff1b;接口测试方面&#xff0c;新增接口文档分享功能、接口场景导入导出功能&#xff0c;…

CUDA下载和安装

CUDA下载和安装 前言下载安装后续添加参考链接 前言 由于我需要运行的代码与我当前的CUDA版本不兼容,所以我现在需要进行CUDA的更新,下载一个低版本的CUDA以匹配我的Pytorch 下载 CUDA下载地址:CUDA下载链接 选择适合自己的版本 由于我是要运行一个开源项目,我选择对应的CU…

Multimodal Reasoning with Multimodal Knowledge Graph

摘要 大型语言模型&#xff08;llm&#xff09;的多模态推理常常存在幻觉和llm中存在缺陷或过时的知识。一些方法试图通过使用文本知识图来缓解这些问题&#xff0c;但其单一的知识形态限制了全面的跨模态理解。本文提出了多模态推理与多模态知识图&#xff08;MR-MKG&#xf…

Git代码托管(三)可视化工具操作(1)

常见的可视化操作工具有 一、官方网页 如码云、gitlab&#xff0c;自带了常见的git操作。 以码云为例&#xff1a; 1、创建分支&#xff1a; 进入分支目录&#xff0c;点击 新建分支 按钮&#xff0c; 在弹出框中输入新分支名称&#xff0c;点击确定即可一键创建分支&…

go中Println和Printf的区别

Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 go中Println和Printf的区别 package mainimport ( "fmt" )//TIP To run your code, right-click the c…

项目审核系统 ---(连接数据库---项目模拟)

本章主要是查询方法和修改方法 编写查询方法&#xff0c;查询所有项目审核信息并返回查询结果&#xff0c;需实现分页功能&#xff0c;注意必要的异常处理。编写查询方法&#xff0c;根据项目编号查询指定项目的审核信息&#xff0c;注意必要的异常处理。编写修改方法&#xf…

(十三)JavaWeb后端开发——MySQL2

目录 1.DQL数据查询语言 1.1基本查询 1.2条件查询 where关键字 1.3分组查询 1.4排序查询 1.5分页查询 2.多表设计 3.多表查询——联查 4.多表查询——子查询​ 5.MySQL 事务 6.MySQL 索引 1.DQL数据查询语言 分为五大基本查询语法 1.1基本查询 -- 查询特定字段 s…

【STL栈和队列】:高效数据结构的应用秘籍

前言&#xff1a; C 标准模板库&#xff08;STL&#xff09;为我们提供了多种容器&#xff0c;其中 stack&#xff08;栈&#xff09;和 queue&#xff08;队列&#xff09;是非常常用的两种容器。 根据之前C语言实现的栈和队列&#xff0c;&#xff08;如有遗忘&#xff0c;…

LWIP通信协议UDP发送、接收源码解析

1.UDP发送函数比较简短&#xff0c;带操作系统和裸机一样。以下是udp_sendto源码解析&#xff1b; 2.LWIP源码UDP接收数据 2.1.UDP带操作系统接收数据&#xff0c;以下是源码解析&#xff1b; 2.2.UDP裸机接收数据&#xff0c;以下是源码解析

小菜家教平台:基于SpringBoot+Vue打造一站式学习管理系统

前言 现在已经学习了很多与Java相关的知识&#xff0c;但是迟迟没有进行一个完整的实践&#xff08;之前这个项目开发到一半&#xff0c;很多东西没学搁置了&#xff0c;同时原先的项目中也有很多的问题&#xff09;&#xff0c;所以现在准备从零开始做一个基于SpringBootVue的…

【优选算法 — 双指针】双指针小专题

和为 s 的两个数 和为s的两个数 题目描述 解法一&#xff1a;暴力枚举 暴力枚举&#xff0c;先固定一个数&#xff0c;然后让这个数和另一个数匹配相加&#xff0c; 如果当前的数 所有剩余的数 target&#xff0c;则返回这两个数&#xff0c;否则固定下一个数&#…

轻松理解操作系统 - 轻松了解 inode 是如何管理文件的

Linux 由于其开源、比较稳定等特点统治了服务端领域。也因此&#xff0c;学习Linux 系统相关知识在后端开发等岗位中变得越来越重要&#xff0c;甚至可以说是必不可少的。 因为它的广泛应用&#xff0c;所以在程序员的日常工作和面试中&#xff0c;它都是经常出现的。它的开源特…

Vue(JavaScript)读取csv表格并求某一列之和(大浮点数处理: decimal.js)

文章目录 想要读这个表格&#xff0c;并且求第二列所有价格的和方法一&#xff1a;通过添加文件输入元素上传csv完整&#xff08;正确&#xff09;代码之前的错误部分因为价格是小数&#xff0c;所以下面的代码出错。如果把parseFloat改成parseInt&#xff0c;那么求和没有意义…

微信小程序-事件总线

一.事件总线的概念和作用 事件总线是对发布-订阅模式的一种实现&#xff0c;是一种集中式事件处理机制&#xff0c;允许不同组件之间进行彼此通信&#xff0c;常用于两个非父子组件和兄弟组件之间的通讯。 在日常开发过程中&#xff0c;我们可以使用第三方的发布订阅 JS 包来实…

成都郝蓉宜恺文化传媒:引领大数据应用新篇章

在信息化浪潮汹涌的今天&#xff0c;大数据被誉为新时代的“石油”&#xff0c;正在以前所未有的速度改变着我们的生活和工作方式。成都郝蓉宜恺文化传媒&#xff0c;作为大数据领域的领军企业&#xff0c;始终站在创新的前沿&#xff0c;引领着大数据应用的新篇章。 作为大数…

qt QDropEvent详解

1、概述 QDropEvent是Qt框架中用于处理拖放释放事件的一个类。它允许开发者在用户界面中更好地管理和处理拖放操作&#xff0c;从而实现交互式和响应式的应用程序。QDropEvent类提供了处理拖放释放事件所需的方法和信号&#xff0c;使得开发者能够轻松地实现拖放功能&#xff…

Kotlin的内置函数

Kotlin 提供了丰富的内置函数&#xff0c;它们极大简化了日常开发工作。常见内置函数包括 标准库函数&#xff08;let、apply、run 等&#xff09;&#xff0c;用于提高代码的简洁性和可读性。下面我们详细介绍这些函数的功能、用法以及它们之间的区别。 1. let 函数 let 通常…

Pod安装软件将CDN改为国内的镜像

1、碰到错误 在pod install的时候碰到以下的下载错误&#xff1a; 文字错误如下&#xff1a; CDN: trunk URL couldnt be downloaded: https://cdn.jsdelivr.net/cocoa/Specs/5/b/d/OpenCV/2.4.11/OpenCV.podspec.json Response: Timeout was reached CDN: trunk URL couldn…

Rockchip SoC AI 与视觉处理器路线图:赋能未来的 AI 驱动设备

随着人工智能&#xff08;AI&#xff09;和计算机视觉技术不断推动各行各业的创新&#xff0c;Rockchip 已成为提供强大系统级芯片&#xff08;SoC&#xff09;解决方案的领先厂商。该公司已开发出多款集成 AI 功能并支持先进多媒体与视觉技术的 SoC&#xff0c;非常适合用于 A…

尚庭公寓-小程序接口

7. 项目开发 7.4 移动端后端开发 7.4.1 项目初始配置 7.4.1.1 SpringBoot配置 1. 创建application.yml文件 在web-app模块的src/main/resources目录下创建application.yml配置文件&#xff0c;内容如下&#xff1a; server:port: 80812. 创建SpringBoot启动类 在web-app…