零钱兑换

1. 题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

2. 思路

1. 思路一
   • DFS
   • 本质上和组合总和.md一样
   • 区别在于可以重复
2. 思路二
   • DFS+缓存

3. 实现

3.1. DFS

func coinChange(coins []int, amount int) int {
    minCount := math.MaxInt32
    coniChangeDFS(coins, amount, 0, &minCount)

    if minCount == math.MaxInt32 {
        return -1
    }

    return minCount
}

func coniChangeDFS(coins []int, target int, count int, minCount *int) {
    if target < 0 {
        return
    }

    if target == 0 {
        *minCount = min(*minCount, count)
        return
    }

    for i := 0; i < len(coins); i++ {
        coniChangeDFS(coins, target-coins[i], count+1, minCount)        
    }

}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b

}

3.2. DFS+缓存

func coinChange(coins []int, amount int) int {
	sort.Slice(coins, func(i, j int) bool {
		return coins[i] > coins[j]
	})
	memo := make(map[int]int, 0)
	minCount := coniChangeDFS(coins, amount, memo)

	if minCount == math.MaxInt32 {
		return -1
	}

	return minCount
}

func coniChangeDFS(coins []int, target int, memo map[int]int) int {
	count, ok := memo[target]
	if ok {
		return count
	}
	count = math.MaxInt32

	if target < 0 {
		return math.MaxInt32
	}

	if target == 0 {
		return 0
	}

	for i := 0; i < len(coins); i++ {
		count = min(count, coniChangeDFS(coins, target-coins[i], memo)+1)
	}

	memo[target] = count
	return count
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b

}

4. 参考

• Java 递归 + 记忆化搜索 + 动态规划 - 零钱兑换 - 力扣（LeetCode）