C++ 解法, 执行用时: 5ms, 内存消耗: 412KB, 提交时间: 2022-03-08

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> f(aim + 1, 1e8);
        
        f[0] = 0;
        for (auto x : arr) {
            for (int j = x; j <= aim; j ++ ) 
                f[j] = min(f[j], f[j - x] + 1);
        }
        
        if (f[aim] == 1e8) return -1;
        return f[aim];
    }
};

C 解法, 执行用时: 5ms, 内存消耗: 420KB, 提交时间: 2022-03-06

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @param aim int整型 the target
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int minMoney(int* arr, int arrLen, int aim ) {
    int result = 0;
    int flag = 1;
    if(aim==0) return 0;
    if(arrLen==0) return -1;
    int sum[aim+1], tmp;
    for(int i=1;i<=aim;i++) sum[i] = 0;
    for(int i=0;i<arrLen;i++) {
        if(arr[i]<=aim) {
            if(arr[i]==aim) return 1;
            sum[arr[i]] = 1;
        }
    }
    
    while(flag) {
        result++;
        flag = 0;
        for(int i=1;i<=aim;i++) {
            if(sum[i]==result) {
                for(int j=0;j<arrLen;j++) {
                    tmp = i+arr[j];
                    if(tmp<=aim && sum[tmp]==0) {
                        if(tmp==aim) return result+1;
                        sum[tmp] = result+1;
                        flag = 1;
                    }
                }
            }
        }
    }
    
    return -1;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 420KB, 提交时间: 2021-09-13

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

C++ 解法, 执行用时: 5ms, 内存消耗: 424KB, 提交时间: 2021-09-25

//lc322 类完全背包
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
        //f[j]表示前i中硬币凑总金额为j，硬币的最少个数
        vector<int> f(aim + 1, 1e9);
        f[0] = 0;
        for(auto c : arr){
            for(int i = c; i <= aim; ++ i){
                f[i] = min(f[i], f[i - c] + 1);
            }
        }
        if(f[aim] == 1e9) return -1;
        return f[aim];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 428KB, 提交时间: 2022-07-26

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
        sort(arr.begin(),arr.end());
        if(aim<1)
            return 0;
        vector<int>dp(aim+1,aim+1);
        dp[0]=0;
        for(auto i: arr)
        {
            for(int j=i;j<=aim;++j)
                dp[j]=min(dp[j],dp[j-i]+1);
        }
        
        return dp[aim]>aim?-1:dp[aim];
    }
};