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

ops/2024/9/24 16:16:23/

描述

给定数组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/ops/111832.html

相关文章

189. 轮转数组

思路 看 k%len(nums)情况 k%len(nums)0&#xff1a;翻转后还是原列表&#xff0c;那就不需要翻转 k%len(nums)>len(nums)//2,显然从后往前翻转过慢&#xff0c;不如从前往后翻转&#xff08;次数更少&#xff09; k%len(nums)<len(nums)//2,显然从后往前翻转次数更少…

修改docker的默认存储位置及镜像存储位置

前言 Docker 默认安装的情况下&#xff0c;会使用 /var/lib/docker/ 目录作为存储目录&#xff0c;用以存放拉取的镜像和创建的容器等。 不过由于此目录一般都位于系统盘&#xff0c;遇到系统盘比较小&#xff0c;而镜像和容器多了后就容易出问题&#xff0c;这里说明一下如何修…

js TypeError: Cannot read property ‘initialize’ of undefined

js TypeError: Cannot read property ‘initialize’ of undefined 在JavaScript开发旅程中&#xff0c;遇到TypeError: Cannot read property ‘initialize’ of undefined这样的错误提示&#xff0c;无疑是令人沮丧的。这个错误通常意味着你试图访问一个未定义对象的initiali…

Python 正则表达式详解:从基础匹配到高级应用

Python 正则表达式详解&#xff1a;从基础匹配到高级应用 文章目录 Python 正则表达式详解&#xff1a;从基础匹配到高级应用一 功能总览二 不用正则的判断三 使用正则判断1 验证用户邮箱2 正则返回匹配信息 四 多条件匹配五 按类型匹配六 匹配中文七 查找替换等功能八 在模式中…

研1日记13

正态分布&#xff1a; toTenor&#xff1a;转数字变为0-1 加载模型&#xff1a; model youmodel() model.load("路径") 测试单个样本&#xff1a;

介绍一些免费 的 html 5模版网站 和配色 网站

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、H5 网站介绍网站 二、配色网站个人推荐 前言 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、H5 网站介绍 以下是一些提供免费…

《HTML 与 CSS—— 响应式设计》

一、引言 在当今数字化时代&#xff0c;人们使用各种不同的设备来访问网页&#xff0c;包括台式电脑、笔记本电脑、平板电脑和智能手机等。为了确保网页在不同设备上都能提供良好的用户体验&#xff0c;响应式设计变得至关重要。HTML 和 CSS 作为构建网页的基础技术&#xff0c…

C++战列舰小游戏Lv. 1.4版本(半成品)

相比较 1.2 ,增加了升级模块 C战列舰小游戏Lv. 1.2版本(半成品)-CSDN博客 相比较1.3&#xff0c;有了大规模完善和模块增加 C战列舰小游戏Lv. 1.3版本(半成品)-CSDN博客 这是一组初始数据&#xff1a; a[1].gas1000; a[1].attack0; a[1].att_10; a[1].att_20;…