题解 | 兑换零钱(一)

#include <functional>
#include <vector>
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
        if(aim<1) return 0;
        int n = arr.size();
        auto cmp = [](const int &a,const int &b){return a>b;};//a>b为真，a的优先级低放前面所以是降序。
        sort(arr.begin(),arr.end(),cmp);
        // sort(arr.begin(),arr.end(),std::greater<int>());
        vector<int >dp(aim+1,aim+1);
        dp[0] = 0;
        for(int i=1;i<aim+1;i++) for(int j=0;j<n;j++) if(arr[j]<=i){
            dp[i] = min(dp[i],dp[i-arr[j]]+1);
        }
        return dp[aim]>aim? -1:dp[aim];


    }
};