题解 | #换钱的最少货币数#

动态规划(完全背包)：dp[i]表示兑换面值为i的钱币(装满容量为i的背包)所需要的最少货币数(物品数)，第i个状态由上一状态，即放或者不放第j个物品推导而来，初始化dp为最大值，dp[0]=0.

class Solution {
public:
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        vector<int> dp(aim+1,999999);
        dp[0]=0;
        for(int j=0;j<arr.size();j++)
            for(int i=1;i<=aim;i++)
                if(i-arr[j]>=0)
                    dp[i]=min(dp[i],dp[i-arr[j]]+1);
        return dp[aim]==999999 ? -1: dp[aim];
    }
};