LeetCode 322. 零钱兑换

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

func coinChange(coins []int, amount int) int {
	var res = math.MaxInt32
	//首先对数据进行逆序排序，先遍历大的数据
	sort.Slice(coins, func(i, j int) bool { return coins[i] > coins[j] })
	res = coin(coins, amount, 0, 0, res)
	if res == math.MaxInt32 {
		return -1
	}
	return res
}

func coin(coins []int, amount, i, count int, ans int) int {
	if amount == 0 {
		ans = int(math.Min(float64(ans), float64(count)))
		return ans
	}
	if i == len(coins) {
		return ans
	}
	//依次遍历每个数量的 coins[i] 
	for k := amount / coins[i]; k >= 0 && k+count < ans; k-- {
		ans = coin(coins, amount-k*coins[i], i+1, count+k, ans)
	}
	return ans
}

func coinChange(coins []int, amount int) int {
	if amount < 1 && len(coins) < 1 {
		return -1
	}
	memo := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		memo[i] = math.MaxInt32
		for _, c := range coins {
			if i >= c && memo[i] > memo[i-c]+1 {
				memo[i] = memo[i-c] + 1
			}
		}
	}
	if memo[amount] == math.MaxInt32 {
		return -1
	}
	return memo[amount]
}