#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]; } };