题解 | #换钱的最少货币数#

 /**
     * 动态规划推到公式：
     * dp[n]=min(dp[n-coin]+1), coin in coins
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int minMoney(int[] arr, int aim) {
        // write code here
        int[] dp = new int[aim + 1];
        for (int value : arr) {
            dp[value] = 1;
        }

        for (int i = 1; i < dp.length; i++) {
            if (dp[i] == 0) {
                dp[i] = Integer.MAX_VALUE;
            }
            for (int value : arr) {
                if (i - value > 0 && dp[i - value] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - value] + 1);
                }
            }
        }
        return dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim];
    }