题解 | #兑换零钱(一)#

方法：动态规划

根据题设，求存储组成aim的最少货币数，假设该问题有解，那么最后一个组成aim的货币一定是数组arr中的元素；因此我们可以将问题拆解，通过遍历数组arr，得到组成aim - arr[i]的最少货币数，那么组成aim的最少货币数即为1 + min(aim - arr[i])。

1、使用一个大小为aim + 1的数组dp来存储0 - aim钱数所需的最少货币数，可以得到如下的状态方程：

dp[i] = min(dp[i], 1 + dp[i - arr[j]]);

2、如果问题有解，返回dp[aim]；否则返回-1。

时间复杂度：o(n * aim)

空间复杂度：o(aim)

class Solution {
  public:
    int minMoney(vector<int>& arr, int aim) {
        // 用于存储组成aim的最少货币数，初始化为aim + 1
        vector<int> dp(aim + 1, aim + 1);
        // 当钱数为0时，设置为0
        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], 1 + dp[i - arr[j]]);
            }
        }
        // 若为初始数字，则说明无解
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
};