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

换钱的最少货币数

http://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45

换钱的最少货币数

描述

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

示例1

输入：[5,2,3],20

返回值：4

示例2

输入：[5,2,3],0

返回值：0

方法一

思路分析

本题可以使用动态规划的办法，设置二维数组$dp[i][j]$表示要凑成$aim=j$时的最少货币数，其中$i$代表可以使用的货币种类为：$arr[0]-arr[i-1]$，初始化当$aim=0$时最少货币数为0，如果使用$arr[i]$那么货币数为$dp[i][j-arr[i]]+1$,如果不使用货币$arr[i]$,那么$dp[i][j]=dp[i-1][j]$，由此得到状态转移方程。初始化当前可以使用的货币只有一种时，货币数为$dp[i][j]=dp[i][j-arr[0]]+1$；之后随着可以使用的货币种类的增加，货币数发生改变。由此回自上而下，从左到右填充数组，最后输出$dp[len(arr)-1][aim]$记为最少货币数。动态规划的优点时将之前找到的最少货币数记录下来，需要查找的时候直接比较。初始化数组第一行的值INT_MAX，转移方程如下：

$dp[i][j]=\left\{ \begin{array}{**lr**} dp[i][j-arr[i]]+1, & i=0.\\ min\{dp[i-1][j], dp[i][j-arr[i]]+1\}, & 1\leq i.\\ \end{array} \right.$

图解

给定实例，写出求解过程

核心代码

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
        int n=arr.size();
        if(n==0) return -1;
        if(aim==0) return 0;
        vector<vector<int>> dp(n,vector<int>(aim+1));//定义二维数组
        for(int j=1; j <= aim; j++)
		{
            dp[0][j] = INT_MAX;//填充第一行
            if(j-arr[0] >= 0 && dp[0][j-arr[0]] != INT_MAX )
			{
                dp[0][j] = dp[0][j-arr[0]] + 1;//dp[0][j-arr[0]]存储aim=j-arr[0]的最少货币数，并且只使用arr[0]
            }
        }
        
       int res = 0;
        for(int i=1; i < n; i++)
		{
           for(int j=1; j <=aim; j++)//自上而下，从左往右填充数组
		   {　　　　　　　　　 
               res = INT_MAX;
                if(j-arr[i] >=0 && dp[i][j-arr[i]] != INT_MAX)
				{
                    res = dp[i][j-arr[i]] + 1;
                }
                dp[i][j] = min(res, dp[i-1][j]);//如果使用arr[i]那么货币数为dp[i][j-arr[i]] + 1,如果不适用货币arr[i],那么dp[i][j]=dp[i-1][j]
            }
        }
    return dp[n - 1][aim] != INT_MAX ? dp[n - 1][aim]:-1;
    }
};

复杂度分析

时间复杂度：需要对二维数组进行填充，时间复杂度为$O(len(arr)*aim)$，时间复杂度与所给货币的数量以及目标值有关
空间复杂度：需要设置一个二维数组存储过程中的最少货币数，因为时间复杂度$O(len(arr)*aim)$

方法二

思路分析

动态规划的方法，需要减小额外的内存空间，在方法一中，可以看到逐渐添加货币时，需要比较不添加该货币的最少货币数，此时需要与上一行的数字进行比较，压缩空间的办法是直接将比较后的值更新到第一行。

图解

核心代码

	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
        int n=arr.size();
        if(n==0) return -1;
        if(aim==0) return 0;
        int minCoins = 0;
        int res = 0;
        vector<int>dp(aim+1);
        dp[0] = 0;
        for (int i = 1; i < aim + 1; ++i) //初始化数组
        {
            if (i - arr[0] >= 0 && dp[i - arr[0]] != aim)
            {
                dp[i] = dp[i - arr[0]] + 1;//填充第一行，只有一种货币
            }
            else
                dp[i] = aim;
        }

        for (int i = 1; i < n; ++i)
        {
            for (int j = 1; j < aim + 1; ++j)
            {
                res = aim;
                if (j - arr[i] >= 0 && dp[j - arr[i]] != aim)
                {
                    res = dp[j - arr[i]] + 1;//逐渐增加货币，然后寻找最小值
                }
                dp[j] = res <= dp[j] ? res : dp[j];
            }
        }

        minCoins = dp[aim];
        return minCoins == aim ? -1 : minCoins;
    }
};

复杂度分析