题解 | #兑换零钱(一)#

#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 n=arr.size();
        vector <int> dp(aim+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<n;i++){
            for(int j=arr[i];j<=aim;j++){
                dp[j]=min(dp[j-arr[i]]+1,dp[j]);
            }
            
        }
        if (dp[aim] == INT_MAX) return -1;
        return dp[aim]; 
    }
    
};