题解 | #换钱的最少货币数#

一.题目描述
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1。
arr=[5，2，3]，aim=20。 4张5元可以组成20元，其他的找钱方案都要使用更多张的货币，所以返回4。
arr=[5，2，3]，aim=0。不用任何货币就可以组成0元，返回0。
arr=[3，5]，aim=2。
根本无法组成2元，钱不能找开的情况下默认返回-1。
二.算法(c++动态规划)
图片说明
我们采用一维dp[j]来进行动态规划：
(1)状态dp[j]定义：N件物品，背包容量j下的最优解。
(2)注意枚举背包容量j必须从m开始。
下面是完整的代码

class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        int dp[aim+5];
        dp[0]=0;
        //刚开始初始化,都是正无穷
        for(int i=1;i<=aim;i++) dp[i]=1e9;
        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);
            }
        }
        //要是dp[m]的最后大小不是无穷 表示有解 否则无解
        if(dp[aim]!=1e9) return dp[aim];
        return -1;
    }
};

时间复杂度： $O(n*m)$ 其中m表示需要凑的钱数，需要二重循环
空间复杂度： $O(n)$ 需要开辟空间来存储方案数
优缺点：代码实现简单，而且容易理解

三.算法(java实现)
思路和上面的算法大致一样，下面是完整代码:

import java.util.*;
public class Solution {
    public int minMoney (int[] arr, int aim) {
        int[] dp=new int[aim+1];
        dp[0]=0;
        //刚开始初始化,都是一个较大的数
        for(int i=1;i<dp.length;i++){
            dp[i]=1000000;
        }
        for(int i=0;i<arr.length;i++){
            for(int j=arr[i];j<=aim;j++){
                dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
            }
        }
        //要是dp[m]的最后大小不是无穷 表示有解 否则无解
        if(dp[aim]!=1000000)
        return dp[aim];
        else 
        return -1;
    }
}

时间复杂度： $O(n*m)$ 其中m表示需要凑的钱数，需要二重循环
空间复杂度： $O(n)$ 需要开辟空间来存储方案数
优缺点：代码实现简单，而且容易理解