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

换钱的最少货币数

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

换钱的最少货币数

问题描述：给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1。【要求】时间复杂度O(n×aim)，空间复杂度O(n)。
示例1
输入：[5,2,3],20
返回值：4
说明：目标是值为aim=20,当组成的货币值为4张5元时，货币数量是最小的。
示例2
输入：[5,2,3],0
返回值：0
示例3
输入：[3,5],2
返回值：-1

方法一

思路分析

本题求解我们直接想到的是能否使用贪心算法，即每次寻找货币中的最大面值，利用aim对最大面值取余，然乎对余数进行相同的操作，但是利用贪心算法可能导致某些情况得不到解。因此我们想到使用动态规划的办法，利用一个数组$dp[aim]$记录从0元开始到aim的换钱最小货币数，寻找其状态转移方程是动态规划问题中的关键。我们可以通过下面的步骤找到该方程：
• 首先判断aim值是否比所给货币数组中的最小值还小，如果是则输出-1；
• 设置$dp[0]=0$,即组成0元的方法数为0；
• 寻找$dp[1]$，即构成1元，只需要先找到一个货币值为1的货币，接下来凑够0元即可，即$dp[1]=dp[1-1]+1$;
• 寻找$dp[2]$,即构成2元，此时有1元和2元两种货币可使用，因此有两种方法，即直接使用2元货币，方法数为$dp[2-2]+1$；使用1元的货币，则为$dp[2-1]+1$,因此最少的货币数为$min(dp[2-1]+1,dp[2-2]+1)$
• 因此状态转移方程为：$dp[aim]=min(dp[aim-arr[i]]+1,dp[aim])$，其中 $aim-arr[i] >=0$，$arr[i]$ 表示第i个货币的面值，循环遍历所有的货币，先找到一个货币值$arr[i]$，接着$aim-arr[i]$表示需要凑的目标值，此时至少需要的货币数目为$dp[aim-arr[i]]+1$，共循环arr.size次，以及凑够aim需要的货币数，初始化为无穷大值。

实例分析

输入：[5,2,3] 6 返回值：2	aim值	$dp[aim]$
	$aim=0 $	dp[0]=0
	$aim=1$	$dp[1]=不存在$
	$aim=2 $	$dp[2]=min(dp[2-2]+1,dp[2])=1$
	$aim=3$	$dp[3]=min(dp[3-2]+1,dp[3-3]+1,dp[3])=1$
	$aim=4$	$dp[4]=min(dp[4-2]+1,dp[4-3]+1,dp[4])=2$
	$aim=5$	$dp[5]=min(dp[5-2]+1,dp[5-3]+1,dp[5-5]+1,dp[5])=min(2,2,1)=1$
	$aim=6$	$dp[6]=min(dp[6-2]+1,dp[6-3]+1,dp[6-5]+1,dp[6])=min(3,2)=2$

C++核心代码

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();
        sort(arr.begin(),arr.end());
        if(aim<arr[0])
            return -1;
        if (0 == n || 0 > n)
        {
            return -1;
        }
        if (aim == 0)
            return 0;
        int dp[aim+1];//待凑钱的数组
        dp[0]=0;
        for(int i = 1; i <= aim; i++) 
        {
            dp[i] = 99999; //初始化数组dp[],设置dp[i]等于无穷大
        }
        for(int i = 1; i <= aim; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i >= arr[j])
                {
                    dp[i] = min(dp[i- arr[j] ] + 1, dp[i]);
                }
            }
        }
        if( dp[aim] == 99999 )
            return -1;
        else return dp[aim];
    }
    
    int min(int a,int b)
    {
        return (a>b?b:a);
    }
};

复杂度分析

• 时间复杂度：首先要对数组进行排序，时间复杂度为$O(n \log n)$，存在两层嵌套循环，时间复杂度为$O(n*aim)$，总的时间复杂度为$O(n \log n+n*aim)$
• 空间复杂度: 使用了一个辅助数组$dp[aim]$，因此空间复杂度为$O(n)$

方法二

思路分析

创建二位辅助数组$dp[arr.size][aim+1]$，从所给货币的第一种面值开始，即$dp[0][i]$，由目标货币值对其进行整除，余下的货币数填入二维数组中。当使用一种货币时，余下的零钱为总的货币数减去使用了的货币，并且货币数增加1个，即为$dp[i][j-arr[0]]+1$，如果不使用当前货币则货币数为$dp[i-1][j]$，两者取较小的一个。具体步骤如下：
• 定义辅助二维数组$dp[arr.size][aim+1]$
• 只能使用arr[0]货币的情况下找某个钱数的最小张数，其值为$dp[i][j-arr[0]]+1$
• 不使用当前货币则货币数为$dp[i-1][j]$
• 上面两者取较小的那一个

python核心代码

#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
       def minMoney(self , arr , aim ):
        # write code here
            if len(arr)==0 or aim<0:
                return -1
            n=len(arr)
            m=float('Inf')
            dp=[[0 for i in range(aim+1)] for j in range(len(arr))]
            for i in range(1,aim+1):
                dp[0][i]=m
                if i-arr[0]>=0 and dp[0][i-arr[0]]!=m:
                    dp[0][i]=dp[0][i-arr[0]]+1#从所给货币的第一种面值开始，即dp[0][i]，由目标货币值对其进行整除，余下的货币数填入二维数组中
            left=0
            for i in range(1,n):
                for j in range(1,aim+1):
                    left=m
                    if j-arr[i]>=0 and dp[i][j-arr[i]]!=m:
                        left=dp[i][j-arr[i]]+1#当使用一种货币时，余下的零钱为总的货币数减去使用了的货币，并且货币数增加1个
                    dp[i][j]=min(left,dp[i-1][j])#如果不使用当前货币则货币数为dp[i-1][j]，两者取较小的一个
            if dp[n-1][aim]!=m:
                return dp[n-1][aim]
            else:
                return -1

复杂度分析

• 时间复杂度：存在两层嵌套循环，因此时间复杂度为$O(n*aim)$
• 空间复杂度: 使用了一个辅助数组$dp[arr.size][aim+1]$，因此空间复杂度为$O(n)$

算法自然分析文章被收录于专栏

在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。