换钱的最小货币数

Question

题目：给定数组 arr ， arr 中所有的值都为正数，每个值仅代表一张钱的面值，再给定一个整数 aim 代表要找的钱数，求组成 aim 的最少货币数目

解答：

• 空间压缩：将原要使用的二维数组压缩称为一维数组
• 考虑：
  • 初始值的设置：对于第一个钱采用是否可以使用作为初始值

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String mn = scanner.nextLine();
        Integer N = Integer.valueOf(mn);
        int []base = {3,5,6,12,4,2};
        System.out.println(getMinCoinOne(base,N));
    }

    private static int getMinCoinOne(int[] base, Integer n) {
        int length = base.length;
        // helper[i + 1]表示前 i 个前的最小货币数
        int []helper = new int[n + 1];
        int max = Integer.MAX_VALUE;
        for (int i = 1 ; i <= n; i ++){
            helper[i] = max;
        }
        if (base[0] <= n){
            // 决定第一个钱是否进行使用
            helper[base[0]] = 1;
        }
        int temp = 0;
        // 从第二个钱开始
        for (int i = 1 ; i < length; i ++){
            for (int j = n; j > 0; j --){
                temp = max;
                if (j - base[i] >= 0  && helper[j - base[i]] != max){
                    temp = helper[j- base[i]] + 1;
                }
                helper[j] = Math.min(helper[j],temp);
            }
        }
        return helper[n] != max ? helper[n] : -1;
    }

}