嗨客网搜索
零钱兑换

描述

力扣第 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 为例子:

17_零钱兑换.png

我们定义了一个数组,数组的长度和 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] } }

赞助商链接:


嗨客网顶部