描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.

数据范围：数组大小满足 0 \le n \le 100000≤n≤10000 ， 数组中每个数字都满足 0 < val \le 100000<val≤10000，0 \le aim \le 50000≤aim≤5000

要求：时间复杂度 O(n \times aim)O(n×aim) ，空间复杂度 O(aim)O(aim)。

示例1

输入： 
[5,2,3],20
复制
返回值： 
4
复制

示例2

输入： 
[5,2,3],0
复制
返回值： 
0
复制

示例3

输入： 
[3,5],2
复制
返回值： 
-1
复制

备注： 

0 \leq n \leq 10\,0000≤n≤10000 0 \leq aim \leq 5\,0000≤aim≤5000

1)递归解法，遍历多叉树；注意使用备忘录剪枝，否则会超时； 
class Solution {
public:
    int func(vector<int>& arr, int aim, vector<int>& dp)
    {
        if (aim == 0) return 0;
        if (aim < 0) return -1;
        if (dp[aim] != -100) return dp[aim];
        int n = arr.size();
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            int tmp = func(arr, aim-arr[i], dp);
            if (tmp == -1) continue;
            res = min(res, tmp+1);
        }
        if (res == INT_MAX) {
            res = -1;
        }
        dp[aim] = res;
        return res;

    }
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        // write code here
        
        if (aim == 0) {
            return 0;
        }
        int n = arr.size();
        if (n == 0) return -1;
         sort(arr.begin(), arr.end());
        if (arr[0] > aim) {
            return -1;
        }
        vector<int>dp(aim+1, -100);
        int res = func(arr, aim, dp);
        return res;
        
    }
};

2）动态规划
背包问题的变种
该题目可以理解为恰好装满体积为aim的背包时可以装的最小价值（每种面额的货币类似于每种体积的物品，其价值均为1）
int minMoney(vector<int>& arr, int aim) {
        if (aim == 0) return 0;
        int n = arr.size();
        if (n == 0) return -1;
        vector<int> dp(aim+1, aim+1); // dp[i]恰好凑到i的最少货币数
        dp[0] = 0;
        for (int i = 1; i <= aim; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[j] <= i) {
                    dp[i] = min(dp[i], dp[i-arr[j]] + 1);
                }

            }

        }
        if (dp[aim] == aim + 1) return -1;
        else return dp[aim];
    }