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

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
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (aim == 0) {
            return 0;
        }
        Arrays.sort(arr);
        if (arr[0] > aim) {
            return -1;
        }

        int[] dp = new int[Math.max(aim, arr[arr.length - 1]) + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[arr[i]] = 1;
        }
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] != 1) {
                int min = Integer.MAX_VALUE;
                boolean isFound = false;
                for (int j = 0; j < arr.length; j++) {
                    int index = i - arr[j];
                    if (index >= 0) {
                        if (dp[index] > 0) {
                            isFound = true;
                            min = Math.min(dp[index] + 1, min);
                        }
                    }
                }
                if (isFound) {
                    dp[i] = min;
                }
            }
        }
        if (dp[aim] == 0) {
            dp[aim] = -1;
        }
        return dp[aim];
    }


}

心态崩了，不记录一下估计后面自己都很难看懂了，代码需要优化一下，要吐了