牛客网面试必刷：CD12 换钱的最少货币数

绝地灬酷狼 2024-03-22 21:51 61阅读 0赞

#### 牛客网面试必刷：CD12 换钱的最少货币数 ####

*  前言
 *  一、动态规划
 *   *  （1）需要判断钱币和总金额
     *  （2）不需要判断钱币和总金额

--------------------

## 前言 ##

**问题链接**: [CD12 换钱的最少货币数][CD12]  
![在这里插入图片描述][3e05e93802dd4c79aae04da76dca5b9f.png]

--------------------

## 一、动态规划 ##

**参考自：**[【编程题 动态规划】兑换零钱(一)（详细注释 易懂）][Link 1]

**解题思想：**

**具体思想就是（还是以上面的举例为例），我先设定，凑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元。**

### （1）需要判断钱币和总金额 ###

public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int amt = in.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
        
                arr[i] = in.nextInt();
            }
            int[] dp = new int[amt+1];
            Arrays.fill(dp,amt+1);
            dp[0] = 0;//很重要，一定要设置dp[0]=0，这是起点！
            for(int i = 1; i <= amt ;i++){
        
                for(int j = 0; j < n ; j++){
        
                    if(i>=arr[j]){
        //如果arr[j]>i，说明钱包里的这张钱已经大于需要拼凑的金额，无法用来拼凑,需要忽略，否则索引越界！
                        dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
                    }
                }
            }
            System.out.println(dp[amt]>amt?-1:dp[amt]);
        }

### （2）不需要判断钱币和总金额 ###

import java.util.*;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int amt = in.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
        
                arr[i] = in.nextInt();
            }
            int[] dp = new int[amt+1];
            Arrays.fill(dp,amt+1);
            dp[0] = 0;
            for (int i = 1 ; i <= n ; i++) {
        
                for (int j = arr[i - 1] ; j <= amt ; j++) {
        
                    dp[j] = Math.min(dp[j], dp[j - arr[i - 1]] + 1);
                }
            }
            System.out.println(dp[amt]>amt?-1:dp[amt]);
        }
    }

[CD12]: https://www.nowcoder.com/practice/4e05294fc5aa4d4fa8eacef2e606e5a8
[3e05e93802dd4c79aae04da76dca5b9f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a8654a06940343aa9a880517592d5c8d.png
[Link 1]: https://blog.csdn.net/qq_51901495/article/details/126454253