题解 | 兑换零钱(一)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        //aim代表总容量，arr.size()代表数量，arr[i]表示体积，价值数组初始化为1
        int n=arr.size();
        int dp[5001];
        fill(dp,dp+5001,10001);
        dp[0]=0;
        for(int i=0;i<n;i++)//这里之所以从0开始是因为arr是从下标0开始记录物品信息的
        {
            for(int j=arr[i];j<=aim;j++)
            {
                dp[j]=min(dp[j],dp[j-arr[i]]+1);
            }
        }
        if(dp[aim]==10001)
        {
            return -1;
        }
        else{
            return dp[aim];
        }
    }
};