题目 #

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

思路1 #

分析 #

自己想的记忆化搜索，假设凑够钱数为n的最小硬币数为 $f(n)$

$$ f(n) = \left\{ \begin{array}{ll} 1 & n == coins[i] \\ MaxInt & n < coins[i] \\ \min(f(n-coins[0]), f(n-coins[1]…)) + 1 & other \end{array} \right. $$

代码实现 #

 1func getMinCount(coins []int, amount int, amountMap []int) int {
 2	if amount < 0 {
 3		return -1
 4	}
 5	if amount == 0 {
 6		return 0
 7	}
 8	if amountMap[amount] != 0 {
 9		return amountMap[amount]
10	}
11
12	// 根据coins遍历，取所有方案最小的
13	minCount := -1
14	for i := len(coins); i > 0; i-- {
15		if amount < coins[i-1] {
16			continue
17		}
18		if amount == coins[i-1] {
19			amountMap[amount] = 1
20			return 1
21		}
22		tmp := getMinCount(coins, amount-coins[i-1], amountMap)
23		if tmp < 0 {
24			continue
25		}
26		if minCount < 0 {
27			minCount = tmp
28			continue
29		}
30		if tmp < minCount {
31			minCount = tmp
32		}
33	}
34	if minCount >= 0 {
35		amountMap[amount] = minCount + 1
36		return minCount + 1
37	}
38	amountMap[amount] = -1
39	return -1
40}

思路2 #

分析 #

记忆化搜索转换一下思路就是动态规划，从0开始计算，一直计算到amount

代码实现 #

 1func min(a, b int) int {
 2	if a > b {
 3		return b
 4	}
 5	return a
 6}
 7
 8func coinChange1(coins []int, amount int) int {
 9	if amount == 0 {
10		return 0
11	}
12	amountMap := make([]int, amount+1)
13	for i := 1; i <= amount; i++ {
14		amountMap[i] = math.MaxInt
15		for _, v := range coins {
16			if i < v {
17				continue
18			}
19			amountMap[i] = min(amountMap[i]-1, amountMap[i-v]) + 1
20		}
21	}
22	if amountMap[amount] == math.MaxInt {
23		return -1
24	}
25	return amountMap[amount]
26}