动态规划凑硬币

Bertha 。 2022-06-08 13:35 193阅读 0赞

> 题目：几年教师节活动中，公司里为培训讲师提供了不同面值的饮料兑换券（每种面值数量不限），培训讲师可以领取兑换券去食堂兑换鲜榨果汁，要求兑换券和果汁必须等价，姜小虎想要兑换一杯果汁，计算它最少要领取几张兑换券，如果无法兑换返回-1.
> 
> 输入描述：第一行：兑换券的面值种类（种类>0） 第二行：数组，代表兑换券面值（面值>0） 第三行：一个整数，代表饮料的价值（饮料的价值>0）
> 
> 输出描述：对于每个测试用例，要求输出最少兑换券张数

这是我在做完美公司笔试的时候遇到的编程题，我自身对动态规划不是很熟悉，当时这道题的数据通过率很低，笔试结束后又重新看了这道题，发现这是一道很经典的凑硬币题，但是有一些细微的点需要注意。

import java.util.Scanner;
    /**
     * 动态规划
     * @author Rose
     *
     */
    public class Main {
        static int[] dp;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            //面值种类
            int n = in.nextInt();
            int[] money = new int[n];
    
            for (int i = 0; i < n; i++) {
                money[i] = in.nextInt();
            }
            //饮料价值
            int value = in.nextInt();
            dp = new int[value+1];
            getMinCount(money, value, 0);
            if(dp[value] == Integer.MAX_VALUE - 1)  //第一处：无法兑换
                System.out.println(-1);
            else
                System.out.println(dp[value]);//可以兑换
        }
        private static int min(int a, int b){
            return a>b?b:a;
        }
        private static void getMinCount(int[] money, int value, int i){
            if(i <= value){
       //第二处：边界限制
                if(i == 0){
       //第三处：当i = 0
                    dp[i] = 0;
                    getMinCount(money, value, i+1);
                    return;
                }else{
                    int min = Integer.MAX_VALUE - 1;
                    for (int j = 0; j < money.length; j++) {
                        if(i >= money[j])
                            min = min(dp[i-money[j]] + 1, min);
                    }
                    dp[i] = min;
                    if(i == value)
                        return;
                    else
                        getMinCount(money, value, i+1);
    
                }
            }
    
        }
    }

上述代码中第一处：代码中为每一个dp\[i\]都初始化为Integer.MAX\_VALUE-1，若经过递归后dp\[i\]的值还是Integer.MAX\_VALUE-1，说明该价值的饮料无法兑换

上述代码第二处：如果不加这个限制，当value = 0时会报错，原因是i= 0时为dp\[0\]赋值之后转入下一层递归，此时i=1，数组越界

上述代码第三处：当i= 0时要单独赋值