刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/coin-change/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个整数数组 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

提示：

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

思路

最开始看到题目，直接就开始呼贪心代码，然后写完之后，发现会超时（后来看题解时候，发现开始还是有贪心剪枝可以过的，后来更新了用例就不得行了...)

那就换思路！
然后就想到了这个感觉很像爬楼梯，类比下就是，我们每一次只能爬coins中给定数字个台阶，直到爬到指定的台阶数，然后求得最少爬台阶次数。

那顺着这个思路，就上动态规划吧：

• dp[i] 表示 amount 为 i` 时，最少爬台阶次数
• 初始条件为dp[0] = 0

剩下就没啥要说的了，上代码，有个剪枝细节在备注里了~

代码

动态规划

func coinChange(coins []int, amount int) int {
	if len(coins) <= 0 {
		return -1
	}
	if amount == 0 {
		return 0
	}

	sort.Slice(coins, func(i, j int) bool {
		return coins[i] < coins[j]
	})

	max := amount + 1
	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = max
	}
	for nowAmount := 1; nowAmount <= amount; nowAmount++ {
		for i := 0; i < len(coins); i++ {
			// 因为有了排序，所以一旦开始面值大于当前所求总和
			// 后面的面值就不需要尝试了
			if coins[i] > nowAmount {
				break
			}
			if dp[nowAmount-coins[i]]+1 < dp[nowAmount] {
				dp[nowAmount] = dp[nowAmount-coins[i]] + 1
			}
		}
	}
	if dp[amount] == max {
		return -1
	}
	return dp[amount]
}

贪心

func coinChange(coins []int, amount int) int {
	if len(coins) <= 0 {
		return -1
	}
	if amount == 0 {
		return 0
	}

	sort.Slice(coins, func(i, j int) bool {
		return coins[i] > coins[j]
	})

	res := amount + 1
	var getNum func(coins []int, nowNum, remainRes int)
	getNum = func(coins []int, nowNum, remainRes int) {
		for i := 0; i < len(coins); i++ {
			if coins[i] == remainRes && nowNum+1 < res {
				res = nowNum + 1
			} else if remainRes > coins[i] {
				// 第二个剪枝，假设都用当前币种，所需数量依然大于现有结果，
				// 那么就直接放弃，肯定结果数更大
				if remainRes/coins[i] > res-nowNum {
					break
				}
				getNum(coins, nowNum+1, remainRes-coins[i])
			}
			// 第一个剪枝，对于超出结果的面值放弃，找更小面值硬币
		}
	}
	getNum(coins, 0, amount)

	if res == amount+1 {
		return -1
	}
	return res
}