题解 | #兑换零钱(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        int[] minNum = new int[aim + 1];
        boolean[] ok = new boolean[aim + 1];
        ok[0] = true;

        for (int i = 1; i != aim + 1; ++i) {
            int total = i;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j != arr.length; ++j) {
                int need = total - arr[j];
                if (need >= 0 && ok[need] && minNum[need] + 1 < min) {
                    min = minNum[need] + 1;       
                    ok[total] = true;            
                }                
            }

            if (ok[total]) {
                minNum[total] = min;
            }
        }

        if (ok[aim]) {
            return minNum[aim];
        } else {
            return -1;
        }
        
    }
}