【编程题动态规划】兑换零钱(一)（详细注释易懂）

题目描述

题目链接：兑换零钱(一)_牛客题霸_牛客网 (nowcoder.com)

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

如果无解，请返回-1.

数据范围：数组大小满足 0≤n≤10000 ，数组中每个数字都满足 0

要求：时间复杂度 o(n×aim) ，空间复杂度 o(aim)。

示例1

输入：

[5,2,3],20返回值：4

示例2

输入：

[5,2,3],0

返回值：

示例3

输入：

[3,5],2

返回值：

-1

题目解读

题目说，给你几个面值，再给你一个要凑的金额，让你给出凑出这个金额需要的最少的钱数。题目好懂，因为我们生活中钱时时刻刻在用，属于是喝醉了我算不清有几个人，还算不清帐吗？哈哈哈！但是要是面值一定，但要凑的钱数太大，口算也很难，所以还是要有一个计算方法。

解题思想

那如何做呢，人可以通过给出的面额和要凑的钱数进行跳跃式计算，比如面额是4 ，5 ，要凑的钱是 13，直接就得到 4 4 5 =13，并且确认这是达到要凑的钱数最少的面值组合，但计算机不行。那就只能挨个计算了，也就是我们说的动态规划。

具体思想就是（还是以上面的举例为例），我先设定，凑0元钱，只用0张钱；然后我要凑一元钱，去面值里面找，没有合适的；然后凑两元钱，还是没有合适的；凑三元，没有合适的；凑四元，4-4=0，我就看凑0元需要几张钱，发现是0张，那凑4元，就是在原有基础上加1，也就是需要1张钱；凑5元，5-4=1，发现凑1元，没有明确的张数，那再看面值5元的，5-5=0，那依然是需要0 1=1张；凑6元，6-4=2，没有明确的张数，6-5=1，也没有；凑7元，7-4=3，没有明确的张数，7-5=2，也没有明确的张数；凑8元，8-4=4，我们看到凑四元需要1张，那凑8元就是2张，8-5=3，没有明确的张数；凑9元，9-4=5，需要1 1=2张，9-5=4，需要1 1=2张，凑够9元有两种方案，选最少的张数，这里都是2，所以就保留2；凑10元，10-4=6，没有明确的张数，10-5=5，需要1 1=2；凑11元，11-4=7，没有明确的张数，11-5=6，也没有；凑12元，12-4=8，需要2 1=3张，12-5=7，没有明确的张数；凑13元，13-4=9，需要2 1=3，13-5=8，需要2 1=3，选最少的张数，就是3；最后看要凑的钱数里面，就是看凑13元里面，有多少张钱数，那怎么判断呢？最后凑13元，钱的张数如果小于等于13元，那就是对的，因为可能有面值1元的。所以，上面提到的没有明确的张数，我们可以设置为 13 1=14，这样如果你被凑到了就一定会小于等于 13元，反之就大于13元。

代码注释

import java.util.*;public class solution {        public int minmoney (int[] arr, int aim) {        // write code here        if(arr.length ==0 )            return -1;       // 用来记录凑 从 1到 aim元，所需的钱的张数        int[] dp = new int[aim 1];          // 对所需的张数，进行初始化        arrays.fill(dp,aim 1);        dp[0]=0;        for(int i=1;i aim?-1:dp[aim];    }}