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

import java.util.*;


public class Solution {

    public int minMoney (int[] arr, int aim) {
        if (aim == 0) {
            return 0;
        }
        int[] dp = new int[aim + 1];
        for (int i = 1; i <= aim; i++) {
            int min = Integer.MAX_VALUE;
            for (int currentMoney : arr) {
                if (i - currentMoney < 0) {
                    continue;
                }
                if (i - currentMoney == 0) {
                    min = 0;
                    break;
                }
                if (dp[i - currentMoney] > 0) {
                    min = Math.min(dp[i - currentMoney], min);
                }
            }
            if (min != Integer.MAX_VALUE) {
                dp[i] = min + 1;
            }
        }
        return dp[aim] == 0 ? -1 : dp[aim];
    }
}