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

1. 注意这是从0开始的背包问题
2. 无线纸张那么每一步都可以换，且三种组合和前面三种剩余的钱数进行对比，取最小。
3. 刚开始MAX初始化target+1会比较好，方便后面的判断。
4. 如果目标少，钱多，那么直接就换不了。

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(!arr.size()){
            return -1;
        }
        int Max = aim +1;
        vector<int> dp(aim+1,Max);

        dp[0] = 0;

        for(int i = 1; i<=aim; i++){
            for(int j = 0;j<arr.size();j++){
                if(arr[j]<=i){//如果当前的钱币比目标值小就可以兑换
                    dp[i] = min(dp[i],dp[i-arr[j]]+1);
                }
            }
        }


        return dp[aim]>aim? -1: dp[aim];

    }
};