！！！题解 | 兑换零钱(一) 妙趣横生 尤其是对于凑不成的处理非常自然

#include <algorithm>
#include <climits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        // write code here
        int size=arr.size();
        if(size==0)return -1;
        if(aim==0)return 0;
        sort(arr.begin(), arr.end());
        int min1=arr[0];
        //int max=arr[size-1];
        if(min1>aim)return -1;
        //这个例子里自底向下最好理解。
        //从小面值开始 从小到大找到中间历经的所有金额的最少货币数目，直到增长到最大值为止。
        /******************************
		这里的关键在于，如果求金额大小为N的结果，因为不知道最后拿的一枚硬币是哪一枚，
        所以就穷举，假设拿的硬币是这些中的一个，然后再求它的子问题，也就是金额为N-Arr【j】最少的钱币是多少。
        这样其实可以自下向上
        */
        vector<int> res(aim+1,aim+1);//dp数组
        res[0]=0;
        for (int i=1; i<=aim; i++) {//i是和下标相对应 从1开始
            for(int j=0;j<size;j++){
                if(arr[j]<=i){
                    res[i]=min(res[i],res[i-arr[j]]+1);//会发生访问越界吗
                    //不会 因为进入条件分支要满足arr[j]<=i，所以最多访问到res[0]
                    //但这个初始化不好。dp数组设置为INTMAX会没有余量，+1就直接溢出了。
                    //可以设为aim+1；因为正常结果绝对不会超过aim。
                    /*这个min(res[i],res[i-arr[j]]+1);也很绝，因为他也覆盖了无法凑成的情况。
                    例如只有2 凑出5.下标1=aim+1；下标2=1；下标3虽然进入分支，但比较之后发现是和1的aim+2比，所以保持自身的aim+1.非常的自然
                    */
                }
			  else break;//这里break是因为当前面值已经大于金额了，所以后面的也肯定大于金额了，所以后面的就不用再匹配了，这样可以节省一些时间。当然也可以不排序，直接全部进行匹配
            }
        }
        return res[aim]==aim+1?-1:res[aim];
    }
};