题解 | 兑换零钱(一)

class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {  //数组中的值，可重复拿出来凑成aim，要求数最少
        if(aim == 0){  //凑0，可以，但需要0张
            return 0;
        }
        
        if(arr.empty()){  //当没有钱时，找不了
            return -1;
        }

        //动态规划：用从最小的开始，进行凑，继承最少的张数
        sort(arr.begin(), arr.end());
        if(aim < arr.front())return -1; //aim比最小的面值小则返回0；

        unordered_map<int, int> mp;  //键存放的是金额，值存放张数
        mp[0] = 0;  //初始化

        for(int i=1; i<=aim; i++){
            for(int num: arr){
                if(num <= i && mp.find(i-num) != mp.end()){  //可以凑, 找到了组合
                    if(mp.find(i) == mp.end()){  //如果还没创建
                        mp[i] = 1 + mp[i-num];
                    }else{  //已经有，取最大值
                        mp[i] = min( mp[i], 1+mp[i-num] );
                    }
                }
            }
        }

        return mp.find(aim) == mp.end() ? -1:mp[aim];
    }
};