后端开发刷题 | 兑换零钱(动态规划)

news/2024/9/18 15:02:33/ 标签: 动态规划, 算法, 数据结构, java, 开发语言

描述

给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个aim,代表要找的钱数,求组成aim的最少货币数。

如果无解,请返回-1.

数据范围:数组大小满足0≤n≤10000 , 数组中每个数字都满足 0<val≤10000,0≤aim≤5000

要求:时间复杂度 O(n×aim),空间复杂度 O(aim)。

示例1

输入:

[5,2,3],20

返回值:

4

示例2

输入:

[5,2,3],0

返回值:

0

示例3

输入:

[3,5],2

返回值:

-1

思路分析:

  1. 初始化变量
    • Max = aim + 1:定义了一个全局最大值,用于初始化dp数组。这个值被设置为aim + 1,是因为如果dp数组中的某个值保持为Max,则表示无法用给定的硬币组成该金额。
    • dp = new int[aim + 1]:定义了一个dp数组,其中dp[i]表示组成金额i所需的最少硬币数。数组大小为aim + 1,因为需要包括目标金额本身。
    • Arrays.fill(dp, Max):将dp数组的所有元素初始化为Max,即无法组成该金额的状态。
    • dp[0] = 0:初始化dp数组的第一个元素为0,表示组成金额为0所需的最少硬币数为0。
  2. 动态规划过程
    • 外层循环遍历目标金额i(从1到aim),表示当前要尝试组成的金额。
    • 内层循环遍历硬币数组arr,检查每个硬币的面值。
    • 如果当前硬币的面值arr[j]小于等于当前要组成的金额i,则尝试使用这枚硬币。通过dp[i] = Math.min(dp[i], dp[i-arr[j]] + 1)更新dp[i]的值。这里dp[i-arr[j]] + 1表示使用了一枚面值为arr[j]的硬币后,还需要多少硬币来组成剩余的金额i-arr[j],然后加1表示当前使用的这枚硬币。
  3. 返回结果
    • 最后,dp[aim]存储了组成目标金额aim所需的最少硬币数。但是,如果dp[aim]仍然是初始化的Max值,说明无法用给定的硬币组成目标金额,因此返回-1。否则,返回dp[aim]

代码:

java">import java.util.*;public class Solution {/*** 最少货币数* @param arr int整型一维数组 the array* @param aim int整型 the target* @return int整型*/public int minMoney (int[] arr, int aim) {//定义一个全局最大值int max=aim+1;int[] dp=new int[aim+1];Arrays.fill(dp,max);//初始化数组dp[0]=0;for(int i=1;i<=aim;i++){for(int j=0;j<arr.length;j++){if(arr[j]<=i){dp[i]=Math.min(dp[i],dp[i-arr[j]]+1);}}}return dp[aim]>aim?-1:dp[aim];}
}


http://www.ppmy.cn/news/1524440.html

相关文章

【Jupyter Notebook】汉化

1.打开:Anaconda Prompt 2.输入:"activate Zhui01"(注意&#xff1a;Zhui01是刚创建的环境名字) activate Zhui01 3.输入:"pip install jupyterlab-language-pack-zh-CN" pip install jupyterlab-language-pack-zh-CN 4.打开:Jupyter Notebook 5.点击&q…

vue3 响应式API customRef()

使用ref()定义响应式数据&#xff1a; <template><div><div>{{ inputValue }}</div><input type"text" v-model"inputValue"></div> </template> <script setup lang"ts"> import { ref } fro…

【干货分享】Ftrans安全数据交换系统 搭建跨网数据传输通道

安全数据交换系统是一种专门设计用于在不同的网络、系统或组织之间安全地传输数据的软件或硬件解决方案。这种系统通常包含多种安全特性&#xff0c;以确保数据在传输过程中的保密性、完整性和可用性。 安全数据交换系统可以解决哪些问题&#xff1f; 安全数据交换系统主要解…

Spring 循环依赖原理及解决方案

一、什么是循环依赖 循环依赖指的是一个实例或多个实例存在相互依赖的关系&#xff08;类之间循环嵌套引用&#xff09;。 举例&#xff1a; Component public class AService {// A中注入了BAutowiredprivate BService bService; }Component public class BService {// B中也…

得物超级品质保障中心,助力电商品质保障迈向新高度

近期记者走进国内知名潮流电商平台——得物App的超级品质保障中心。该中心位于上海市嘉定区&#xff0c;总建筑面积达到约12万平方米&#xff0c;是集查验鉴别、鉴别研究、质量管理、仓储流转等功能于一体的综合性服务设施&#xff0c;全面覆盖了服装、配饰、奢侈品等多个业务品…

APACHE-ATLAS-2.1.0 - 基础运维

&#xff08;一&#xff09;SOLR相关 1. 如何创建/删除集合&#xff1f; # 1. 删除 solr/bin/solr delete -c vertex_index solr/bin/solr delete -c edge_index solr/bin/solr delete -c fulltext_index# 2. 创建 solr/bin/solr create -c vertex_index -force -d conf/solr…

从零开始学cv-0:图像处理基础知识

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一&#xff0c;图像分类1.1、模拟图像1.2、数字图像 二、颜色模式&#xff08;颜色存储&#xff09;2.1、RGB模式&#xff08;发光模式&#xff09;2.2、CMYK模…

pptp解说

PPTP&#xff08;Point-to-Point Tunneling Protocol&#xff09;是一种网络协议&#xff0c;用于在互联网上创建虚拟专用网络&#xff08;VPN&#xff09;连接。 PPTP 允许远程用户通过公共网络&#xff08;如互联网&#xff09;安全地连接到私有网络。它是一种较早的VPN技术…

鸿萌数据恢复服务:Mac 文件系统是如何影响 Mac 数据恢复的?

天津鸿萌科贸发展有限公司从事数据安全服务二十余年&#xff0c;致力于为各领域客户提供专业的数据备份、数据恢复解决方案与服务&#xff0c;并针对企业面临的数据安全风险&#xff0c;提供专业的相关数据安全培训。 公司是多款国际主流数据恢复软件的授权代理商&#xff0c;为…

C++设计模式——State状态模式

一&#xff0c;状态模式的定义 状态模式是一种行为型设计模式&#xff0c;状态模式允许对象在内部状态发生切换时改变它自身的行为。 状态模式的主要目的是将复杂的状态切换逻辑抽象化为一组离散的状态类&#xff0c;使代码结构更加清晰和易于维护。 状态模式将对象的行为封…

继收购西门子物流自动化后,丰田又投资一家AGV公司,智能物流版图已极其夸张...

导语 大家好&#xff0c;我是社长&#xff0c;老K。专注分享智能制造和智能仓储物流等内容。 继成功将西门子物流自动化(机场物流业务)纳入麾下后&#xff0c;丰田并未停下其征伐的步伐&#xff0c;而是再度出手&#xff0c;与新兴科技巨头Gideon携手&#xff0c;共同绘制了一幅…

AI 产品经理:2024 年职场新航标 ——AI 产品经理的未来与契机

前言 这两年&#xff0c;AI 骤然“火”了起来&#xff0c;可谓出现了重大“转折”。就在这短短两年间&#xff0c;全球各大“大厂”几乎在同一时间争先恐后地跟进 AI 技术。从 ChatGPT 发布起&#xff0c;谷歌、Facebook、亚马逊等纷纷紧跟其后&#xff0c;国内的百度、腾讯、…

【笔记】一维动态规划DP

文章目录 动态规划DPDP解题步骤例子1lanqiao3367 破损的楼梯题目描述输入格式输出格式解题思路代码 lanqiao3423 安全序列题目描述输入格式输出格式解题思路代码 动态规划DP 动态规划用于解决具有重叠子问题、最优子结构特征的问题。 重叠子问题&#xff1a;子问题是原问题的…

安装与pytorch不同cuda版本的bitsandbytes

由于历史遗留问题&#xff0c;虽然我的cuda版本是11.8&#xff0c;但是我的torch对应cuda版本是12.1&#xff0c;安装bitsandbytes后&#xff0c;就会抛出以下报错&#xff1a; Could not load bitsandbytes native library: libcusparse.so.12: cannot open shared object fi…

Flask如何传递URL参数

在Flask中&#xff0c;传递URL参数是一种常见且强大的功能&#xff0c;它允许你的Web应用根据URL中的不同部分来动态地生成内容或执行不同的操作。虽然直接撰写5000字来详细解释这一功能可能过于冗长&#xff0c;但我可以提供一个简明而全面的概述&#xff0c;包括基本概念、使…

ISAC: Toward Dual-Functional Wireless Networks for 6G and Beyond【论文阅读笔记】

此系列是本人阅读论文过程中的简单笔记&#xff0c;比较随意且具有严重的偏向性&#xff08;偏向自己研究方向和感兴趣的&#xff09;&#xff0c;随缘分享&#xff0c;共同进步~ Integrated Sensing and Communications: Toward Dual-Functional Wireless Networks for 6G and…

AI客服机器人开启企业客户服务新纪元

随着人工智能(AI)技术的迅猛发展&#xff0c;使得AI客服机器人走进了我们的视野&#xff0c;成为提高客户满意度和业务效率的不二法宝。这些智能机器人不仅能够处理海量信息&#xff0c;还能为客户提供个性化的服务体验。 一、AI客服机器人的基本原理 AI客服机器人是基于人工智…

探索非局部均值滤波在椒盐噪声去除中的应用

在图像处理领域&#xff0c;椒盐噪声是一种常见的干扰&#xff0c;它会导致图像出现随机的黑白像素点&#xff0c;严重影响图像质量。为了解决这一问题&#xff0c;本文将介绍一种有效的去噪技术——非局部均值滤波&#xff08;NLM&#xff09;的改进版本&#xff0c;即NAMF&am…

Java面试篇基础部分-JVM详细介绍

JVM的运行机制 JVM(Java Virtual Machine)是用于运行Java字节码的虚拟计算机,其中包括一套字节码的指令集、程序寄存器、虚拟机栈、虚拟机堆、本地方法区、垃圾回收器。JVM运行在操作系统上层,它不跟底层硬件直接进行交互。如下图所示   Java源代码通过了编译器编译成响…

电商品牌假货要怎么处理

在电商蓬勃发展的今日&#xff0c;假货问题如影随形&#xff0c;严重威胁着品牌的声誉与市场的健康。力维网络以专业打假服务&#xff0c;为品牌保驾护航。 一、精准监测&#xff0c;揪出假货端倪 力维网络的数据监测系统犹如一张严密的大网&#xff0c;覆盖全网。通过全面采集…