赞
赏
力扣第 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 为例子:
我们定义了一个数组,数组的长度和 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 当中的最小值。
因为是从小到大的顺序进行计算,所以数组中的已经维护的数值,都是最小的数值。如果不能够组成数据,在数组中,我们就定义一个比较大的数值,最后用来判断是否有组合能够组成。
//动态规划
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];
}
}
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]
}
}