每天刷一道牛客题霸-第24天- 换钱最少货币数

题目

https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=190&&tqId=36067&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
   public static int minMoney (int[] arr, int aim) {
        int[] count = new int[aim +1];
        Arrays.fill(count, aim + 1);
        count[0] = 0;
        for (int i =1;i<=aim;i++){
            for (int j = 0 ; j < arr.length ; j++){
                if (i >=arr[j]){
                    count[i] = Math.min(count[i-arr[j]] +1 , count[i]);
                }
            }
        }
        return count[aim] != aim+1 ? count[aim] :-1;
        // write code here
    }
}