动态规划凑硬币-蒲公英云

动态规划凑硬币

Bertha 。 2022-06-08 13:35 274阅读 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);
            }
        }
    }
}