零钱兑换

描述

力扣第 322 题。给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例2：

输入：coins = [2], amount = 3
输出：-1

示例3：

输入：coins = [1], amount = 0
输出：0

示例4：

输入：coins = [1], amount = 1
输出：1

示例5：

输入：coins = [1], amount = 2
输出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

思路

本题是动态规划最好的实现，我们以示例 1 为例子：

我们定义了一个数组，数组的长度和 amount + 1 的值相等，它的坐标位表示对应的总金额数值，数组里面的值表示最少的硬币数量。F(X) 函数中，X 表示的是要求的总金额数量。因为要求总金额是 11 的最少硬币数量，所以我们就获取数组，索引位置是 11 的数值。

• 第一步：F(0) = 0；因为是求总金额为 0 的硬币组合，不需要任何硬币，所以返回 0。

• 第二步：F(1) = 1，因为硬币的数值数组里面，有数值是 1 的硬币，所以它就是求 F(1-1) + 1 的数值，即 F(0) + 1 = 1。

• 第二步：F(2) = min(F(2-1) + 1,F(2-2)) = 1。当求数值是 2 的硬币的时候，要么就是用数值是 1 的硬币值 + 1 ，或者用数值为 2 的硬币 + 0。所以就是求 min(F(1) + 1 ,F(0) + 1) 的最小值

  。。。

• 第 N 步：F(N) = min(F(N-1) + 1 , F(N-2) + 1, F(N-5) + 1)。当要求的数值大于硬币集合里面的所有单个硬币值的时候，就获取其中前一个值的最小数值。

• 第 11 步：F(11) = min(F(11-1) + 1,F(11-2)+1,F(11-5)+1) 。它就是求 F(10) + 1 ,F(9 ) + 1,F(6) + 1 当中的最小值。

因为是从小到大的顺序进行计算，所以数组中的已经维护的数值，都是最小的数值。如果不能够组成数据，在数组中，我们就定义一个比较大的数值，最后用来判断是否有组合能够组成。

代码具体实现

Java语言版本

//动态规划
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        //定义一个一维数组，用来存储状态，每个值对应的相应的最小数量
        int[] amountAndCountArray = new int[amount + 1];
        amountAndCountArray[0] = 0; 
        //从小到大来遍历每个数值，获取每个数值对应的数量
        for(int i=1;i<=amount;i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0;j<coins.length;j++){
                if(i >= coins[j] && amountAndCountArray[i - coins[j]] < min ){
                    min = amountAndCountArray[i-coins[j]] + 1;
                }
            }
            amountAndCountArray[i] = min;
        }
        return amountAndCountArray[amount] == Integer.MAX_VALUE ? -1 : amountAndCountArray[amount];
    }
}

Go语言实现

func coinChange(coins []int, amount int) int {
     if amount == 0 {
            return 0
        }
        //定义一个一维数组，用来存储状态，每个值对应的相应的最小数量
        amountAndCountArray :=  make([]int,amount + 1)
        amountAndCountArray[0] = 0
        //从小到大来遍历每个数值，获取每个数值对应的数量
        for i:=1;i<=amount;i++{
            min :=  amount + 1
            for j := 0;j<len(coins);j++ {
                if i >= coins[j] && amountAndCountArray[i - coins[j]] < min {
                    min = amountAndCountArray[i-coins[j]] + 1
                }
            }
            amountAndCountArray[i] = min
        }
        if amountAndCountArray[amount] == amount + 1 {
            return -1
        }else{
            return amountAndCountArray[amount]
        }
}