题目的主要信息：

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

方法一：空间记忆递归

具体做法：

对于需要凑成$aimaim$的钱，第一次我们可以选择使用$arr[0]arr[0]$，则后续需要凑出$aim-arr[0]aim-arr[0]$的钱，那后续就是上一个的子问题，可以用递归进行。因为每种面值使用不受限，因此第一次我们可以使用arr数组中每一个，同理后续每次也可以使用arr数组中每一次，因此每次递归都要遍历arr数组，相当于分枝为$arr\mathrm{.}size()arr.size()$的树型递归。

递归的时候，一旦剩余需要凑出的钱为0，则找到一种情况，记录下整个的使用货币的数量，维护最小值即可。一旦剩余需要凑出的钱为负，则意味着这一分枝无解，返回-1.

但是树型递归的复杂度需要$O(ai{m}^n)O(aim^\{n\})$，重复计算过于多了，如图所示，因此我们可以用一个dp数组记录每次递归上来的结果，避免小分支重复计算，如果dp数组有值直接获取即可，不用再重复计算了。

class Solution {
public:
    int recursion(vector<int>& arr, int aim, vector<int>& dp){
        if(aim < 0) //组合超过了，返回-1
            return -1;
        if(aim == 0) //组合刚好等于需要的零钱
            return 0;
        if(dp[aim - 1] != 0) //剩余零钱是否已经被运算过了
            return dp[aim - 1];
        int Min = INT_MAX;
        for(int i = 0; i < arr.size(); i++){ //遍历所有面值
            int res = recursion(arr, aim - arr[i], dp); //递归运算选择当前的面值
            if(res >= 0 && res < Min) //获取最小值
                Min = res + 1;
        }
        dp[aim - 1] = Min == INT_MAX ? -1 : Min; //更新最小值
        return dp[aim - 1];
    }
    int minMoney(vector<int>& arr, int aim) {
        if(aim < 1) //小于1的都返回0
            return 0;
        vector<int> dp(aim, 0); //记录递归中间的值
        return recursion(arr, aim, dp);
    }
};

复杂度分析：

• 时间复杂度：$O(n\cdot aim)O(n\; \backslash cdot\; aim)$，一共需要计算aim个状态的答案，每个状态需要枚举n个面值
• 空间复杂度：$O(aim)O(aim)$，递归栈深度及辅助数组的空间

方法二：动态规划

具体做法：

方法一递归是一种自上而下的方式，我们也可以用动态规划自下而上相加，可以用$dp[i]dp[i]$表示要凑出i元钱需要最小的货币数，一开始都设置为最大值$aim+1aim+1$，因此货币最小1元，即货币数不会超过$aimaim$.

初始化$dp[0]=0dp[0]=0$，后续遍历1元到aim元，枚举每种面值的货币都可能组成的情况，取每次的最小值即可，转移方程为$dp[i]=min(dp[i],dp[i-arr[j]]+1)dp[i]\; =\; min(dp[i],\; dp[i\; -\; arr[j]]\; +\; 1)$.

最后比较$dp[aim]dp[aim]$的值是否超过aim，如果超过说明无解，否则返回即可。

class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        if(aim < 1) //小于1的都返回0
            return 0;
        vector<int> dp(aim + 1, aim + 1);  //dp[i]表示凑齐i元最少需要多少货币数
        dp[0] = 0; 
        for(int i = 1; i <= aim; i++){ //遍历1-aim元
            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]; //如果最终答案大于aim代表无解
    }
};

复杂度分析：

• 时间复杂度：$O(n\cdot aim)O(n\backslash cdot\; aim)$，第一层遍历枚举1元到aim元，第二层遍历枚举n种货币面值
• 空间复杂度：$O(aim)O(aim)$，辅助数组dp的大小