Golang中的硬币找零问题解析

Golang中的硬币找零问题解析 有人能帮我创建一个零钱兑换函数吗？

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

你可以假设每种硬币的数量是无限的。

来源：Leetcode

3 回复

为什么当金额不为0时，我们要进行 n - 1 操作？

更多关于Golang中的硬币找零问题解析的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


很抱歉，我忽略了那部分，所以这个解决方案对 [1,2,5] 有效，但对于更复杂的问题，即使存在可能的解，它也会走向 -1 的路径。

例如：对于这个例子，它给了我 -1，但正确答案是 20

    [186,419,83,408]
    6249

以下是一个使用动态规划的Go语言实现，用于解决硬币找零问题：

func coinChange(coins []int, amount int) int {
    // 创建dp数组，初始化为amount+1（表示不可能达到的值）
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0  // 金额为0时需要0个硬币
    
    // 遍历所有金额
    for i := 1; i <= amount; i++ {
        // 尝试使用每种硬币
        for _, coin := range coins {
            if coin <= i {
                dp[i] = min(dp[i], dp[i-coin] + 1)
            }
        }
    }
    
    // 检查是否有解
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

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

示例使用：

func main() {
    coins := []int{1, 2, 5}
    amount := 11
    
    result := coinChange(coins, amount)
    fmt.Printf("最少硬币数: %d\n", result)  // 输出: 3 (5+5+1)
    
    // 测试无解情况
    coins2 := []int{2}
    amount2 := 3
    result2 := coinChange(coins2, amount2)
    fmt.Printf("无解返回: %d\n", result2)  // 输出: -1
}

这个实现的时间复杂度是O(amount * n)，其中n是硬币种类数。空间复杂度是O(amount)。

回到顶部