0%

零钱兑换

Coin Change 题目

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

解题思路

条件:

  1. 有多种面额
  2. 每种面额数量不限
  3. 输出凑成面额的最少硬币个数
  4. 没有可能输出 -1

如有 [1, 2, 5] 三种面额,总金额 amount 为 11,答案为 3 既 11 = 5 + 5 + 1

比如你想求 amount = 11 时的最少硬币数(原问题),如果知道凑出 amount = 10 的最少硬币数(子问题),只需要把子问题的答案加一(再选一枚面值为 1 的硬币))就是原问题的答案,因为硬币的数量是没有限制的,子问题之间没有相互制,是互相独立的。这类子问题又称为最优子结构。

func coinChange(coins []int, amount int) int {
cache := make(map[int]int)
return dp(coins, amount, cache)
}

func dp(coins []int, amount int, cache map[int]int) int {
if n, ok := cache[amount]; ok {
return n
}
if amount == 0 {
return 0
}
if amount < 0 {
return -1
}
res := math.MaxInt8
for _, coin := range coins {
sub := dp(coins, amount-coin, cache)
if sub == -1 {
continue
}
res = min(res, 1+sub)
}
if res != math.MaxInt8 {
cache[amount] = res
} else {
cache[amount] = -1
}
return cache[amount]
}

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