esc to dismiss

322. 零钱兑换

题目

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

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

示例 1:

输入:coins = [1, 2, 5], amount = 11

输出:3

解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3

输出:-1

示例 3:

输入:coins = [1], amount = 0

输出:0

示例 4:

输入:coins = [1], amount = 1

输出:1

示例 5:

输入:coins = [1], amount = 2

输出:2

解体思路

这道题目的解题思路是: 动态规划 ,按照 自底向上的方式:

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1, amount+1)
    dp[0] = 0

    for i := 1; i <= amount; i++ {
        best := -1
        for _, c := range coins {
            if i >= c && dp[i-c] >= 0 {
                best = min(best, dp[i-c] + 1)
            }
        }
        dp[i] = best
    }
    return dp[amount]
}

func min(best, val int) int {
    if best >= 0 && best < val {
        return best
    }
    return val
}

但写完之后我发现如果用 自顶向下+备忘录,也就是递归的方式,路径会更短,因为上述的有些组合不会被递归到。

提示

LeetCode 题解中管这种递归方式叫 “记忆化搜索”,又是一个新名词,不知道跟 自顶向下+备忘录 有什么区别。

经验教训

略。

x