一、问题描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

说明: 你可以认为每种硬币的数量是无限的。 来源：LeetCode 322. 零钱兑换

二、方案一：动态规划

1、思路

动态规划是解决此类问题的常用方法。我们定义一个一维数组 dp[i] 表示凑成金额 i 所需要的最少硬币数。

• 初始化 dp[0] = 0，因为凑成金额 0 所需要的硬币数是 0。
• 对于每个金额 i，我们需要考虑所有可能的硬币面额 coin，更新 dp[i] 的值。

2、代码实现

func coinChange(coins []int, amount int) int {
    // 初始化 dp 数组
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt32
    }
    // 填充 dp 数组
    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if i >= coin && dp[i-coin] != math.MaxInt32 {
                dp[i] = min(dp[i], dp[i-coin]+1)
            }
        }
    }
    // 如果 dp[amount] 仍然是 math.MaxInt32，说明无法凑成总金额
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(amount×n)，其中 amount 是总金额，n 是硬币种类的数量。我们需要填充一个长度为 amount 的一维数组，每次填充需要考虑 n 个硬币。
• 空间复杂度：O(amount)，我们需要一个长度为 amount 的一维数组来存储中间结果。

三、方案二：递归 + 记忆化搜索

1、思路

我们可以使用递归的方法来解决这个问题。对于每个金额 i，我们需要考虑所有可能的硬币面额 coin，更新凑成金额 i 所需要的最少硬币数。为了避免重复计算，我们可以使用一个一维数组来存储已经计算过的结果。

2、代码实现

func coinChange(coins []int, amount int) int {
    memo := make([]int, amount+1)
    for i := range memo {
        memo[i] = -1
    }
    var dfs func(amount int) int
    dfs = func(amount int) int {
        if amount == 0 {
            return 0
        }
        if amount < 0 {
            return -1
        }
        if memo[amount] != -1 {
            return memo[amount]
        }
        minCoins := math.MaxInt32
        for _, coin := range coins {
            subProblem := dfs(amount - coin)
            if subProblem == -1 {
                continue
            }
            minCoins = min(minCoins, subProblem+1)
        }
        if minCoins == math.MaxInt32 {
            memo[amount] = -1
        } else {
            memo[amount] = minCoins
        }
        return memo[amount]
    }
    return dfs(amount)
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(amount×n)，其中 amount 是总金额，n 是硬币种类的数量。尽管我们使用了递归，但由于记忆化搜索，每个子问题只被计算一次。
• 空间复杂度：O(amount)，我们需要一个长度为 amount 的一维数组来存储中间结果。

四、总结

方案	时间复杂度	空间复杂度	备注
动态规划	O(amount×n)	O(amount)	适合解决此类问题，易于理解和实现
递归 + 记忆化搜索	O(amount×n)	O(amount)	通过递归实现，代码更简洁，但可能不如动态规划直观

两种方案在时间和空间复杂度上相同，选择哪种方案取决于个人偏好。动态规划更为直观，而递归 + 记忆化搜索代码更简洁。在实际应用中，可以根据具体情况选择最适合的方案。