题解 | 兑换零钱(一)

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        if (aim < 1) {
            return 0;
        }
        int[] countStr = new int[aim + 1];
        return minMoneyCompute(arr, aim, countStr);
    }
    public int minMoneyCompute (int[] arr, int aim, int[] countStr) {
        if (aim == 0) {
            return 0;
        }
        if (aim < 0) {
            return -1;
        }
        if (countStr[aim] != 0) {
            return countStr[aim];
        }
        int min = Integer.MAX_VALUE;
        for (int i : arr) {
            int res = minMoneyCompute(arr, aim - i, countStr);
            if (res != -1 &&  res < min) {
                min = res + 1;
            }
        }
        countStr[aim] = min;
        return countStr[aim] == Integer.MAX_VALUE ? -1 : countStr[aim];
    }

}