Coin Change

题目描述

零钱兑换

给定不同面额硬币coins和一个总额度amount，计算凑成总额数所需的最少硬币个数，如果无法凑成总额数，返回-1。

示例：

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

解法

这个题型很经典，大部分动态规划的题目都能从其中找到解题思路

解法一：贪心算法

• 时间复杂度：待定

• 空间复杂度：待定

func coinChange(coins []int, amount int) int {
    ans := amount + 1
    var dfs func(coins []int, amount int, cnt int)
    dfs = func(coins []int, amount int, cnt int) {
        if len(coins) == 0 {
            return
        }
        for i := amount/coins[0]; i >= 0; i-- {
            if cnt + i > ans {
                break
            }
            if amount - i*coins[0] == 0 {
                if ans > cnt+i {
                    ans = cnt+i
                }
                break
            }
            dfs(coins[1:], amount-i*coins[0], cnt+i)
        }
    }

    sort.Slice(coins, func (i, j int) bool { return coins[i] > coins[j] })
    dfs(coins, amount, 0)
    if ans == amount + 1 {
        ans = -1
    }
    return ans
}

解法二：迭代法

• 时间复杂度：O(amount * n)

• 空间复杂度：O(amount)

func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    ans := 0
    queue := []int{amount} // 树状按层搜索
    vis := make(map[int]bool, amount) // 记忆
    for len(queue) > 0 {
        qLen := len(queue)
        ans++
        for i := 0; i < qLen; i++ {
            num := queue[i]
            for _, coin := range coins {
                if vis[num-coin] { // 剪枝
                    continue
                }
                if num - coin < 0 { // 剪枝
                    continue
                }
                if num - coin == 0 { // 搜索结束
                    return ans
                }
                vis[num-coin] = true
                queue = append(queue, num-coin)
            }
        }
        queue = queue[qLen:]
    }
    return -1
}

解法三：动态规划（自顶向下）

• 时间复杂度：O(amount * n)

• 空间复杂度：O(amount)

func coinChange(coins []int, amount int) int {
    // cache[i] 表示凑足金额i需要的最少个数
    cache := make([]int, amount+1)
    return dfs(coins, amount, cache)
}

func dfs(coins []int, amount int, cache []int) int {
    if amount == 0 {
        return 0
    }
    if cache[amount] > 0 || cache[amount] == -1 {
        return cache[amount]
    }

    // dp[i] = min{dp[i-coin]} + 1
    // or dp[i] = -1
    ans := amount+1
    for _, coin := range coins {
        if amount - coin < 0 {
            continue
        }
        cnt := dfs(coins, amount-coin, cache)
        if cnt >= 0 && ans > cnt+1 {
            ans = cnt+1
        }
    }
    if ans == amount+1 {
        ans = -1
    }

    cache[amount] = ans
    return cache[amount]
}

解法四：动态规划（自下向上）

• 时间复杂度：O(amount * n)

• 空间复杂度：O(amount)

func coinChange(coins []int, amount int) int {
    // dp[i] 表示凑足金额i需要的最少个数
    // dp[i] = min{dp[i-coin]} + 1
    // or dp[i] = -1
    dp := make([]int, amount+1)
    dp[0] = 0
    for i := 1; i <= amount; i++ {
        dp[i] = i+1
        for _, coin := range coins {
            if i - coin >= 0 && dp[i-coin] != -1 && dp[i] > dp[i-coin]+1 {
                dp[i] = dp[i-coin] + 1
            }
        }
        if dp[i] == i+1 {
            dp[i] = -1
        }
    }
    return dp[amount]
}