描述

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

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

要求：

时间复杂度 $O(n \times aim)$ ，空间复杂度 $O(aim)$。

示例1

输入：

[5,2,3],20

返回值：

4

示例2

输入：

[5,2,3],0

返回值：

0

示例3

输入：

[3,5],2

返回值：

-1

题解

完全背包问题

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