题解 | 兑换零钱(一)

#include <algorithm>
class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {

        if(aim==0) return 0 ;
        //sort(arr.begin(),arr.end());
        //int mincoin = arr[0];
        int  n = arr.size();
        if(n==0) return -1;

        int max  = arr[n-1];
        //if(aim<mincoin) return -1;
       
        vector<int> dp(aim+1,aim+1);
        dp[0] = 0;
        for (int j=0; j<n   ; j++) {
            for(int i=arr[j];i<=aim;i++){
               dp[i] = min(dp[i],dp[i-arr[j]]+1);
            }
        }
         // 若仍为初始值，说明无法凑出
        return dp[aim] > aim ? -1 : dp[aim];
    }
};

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        if (arr.empty()) return aim == 0 ? 0 : -1;
        
        vector<int> dp(aim + 1, aim + 1);
        dp[0] = 0;
        
        for (int coin : arr) {
            for (int i = coin; i <= aim; i++) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
        
        return dp[aim] > aim ? -1 : dp[aim];
    }
};