算法题：零钱兑换

编码如写诗

发布于 2026-03-02 20:44:52

160

文章被收录于专栏：编码如写诗编码如写诗

算法题：零钱兑换

今天刷到道挺有意思的题，零钱兑换，LeetCode第322题。

题目是这样的：给你一堆不同面额的硬币，还有一个总金额，问凑出这个总金额最少需要几枚硬币。

如果凑不出来，返回-1。

听着挺简单的对吧？

但一上手就发现没那么容易。

题目理解

举个栗子，假设硬币有 [1, 2, 5] 三种面额，要凑11块钱。

怎么凑最省？

5 + 5 + 1，3枚就够了。

要是3 + 3 + 3 + 2，就要4枚，不是最优解。

所以问题就是，在所有可能的组合里，找出硬币数最少的那个。

思路分析

最暴力的解法就是枚举所有组合，然后选最小的。

这个思路看着简单，但问题是组合数量太多，会超时。

比如有n种硬币，总金额是amount，最坏情况下要算多少次？

复杂度是指数级别的，直接原地去世。

所以得想别的办法。

其实这道题是个经典的动态规划问题。

我们定义 dp[i] 为凑出金额 i 需要的最少硬币数。

那 dp[i] 怎么算呢？

对于每一种硬币面额 coin，如果 i >= coin，那么 dp[i] 可能是 dp[i-coin] + 1。

意思就是，先凑出 i-coin，再加上一枚硬币 coin，就能凑出 i。

我们要找所有可能的 coin 里，让 dp[i-coin] + 1 最小的那个。

所以状态转移方程是：

dp[i] = min(dp[i - coin] + 1) for all coin in coins

base case 是 dp[0] = 0，凑0块钱需要0枚硬币。

然后从 1 到 amount 依次计算，最后 dp[amount] 就是答案。

如果 dp[amount] 还是初始值（比如一个很大的数），说明凑不出来，返回-1。

复杂度分析

时间复杂度是 O(amount * n)，n是硬币种类的数量。

空间复杂度是 O(amount)，需要一个长度为 amount+1 的数组。

这个复杂度还是可以接受的。

代码实现

package main

import (
    "fmt"
    "math"
)

func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return0
    }

    // dp[i] 表示凑出金额i需要的最少硬币数
    dp := make([]int, amount+1)

    // 初始化为最大值，因为要求最小值
    for i := 0; i <= amount; i++ {
        dp[i] = math.MaxInt32
    }

    // 凑出0元需要0枚硬币
    dp[0] = 0

    // 从1到amount依次计算
    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)
            }
        }
    }

    if dp[amount] == math.MaxInt32 {
        return-1
    }
    return dp[amount]
}

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

func main() {
    // 测试用例
    coins1 := []int{1, 2, 5}
    amount1 := 11
    fmt.Printf("coins=%v, amount=%d, result=%d\n", coins1, amount1, coinChange(coins1, amount1))

    coins2 := []int{2}
    amount2 := 3
    fmt.Printf("coins=%v, amount=%d, result=%d\n", coins2, amount2, coinChange(coins2, amount2))

    coins3 := []int{1}
    amount3 := 0
    fmt.Printf("coins=%v, amount=%d, result=%d\n", coins3, amount3, coinChange(coins3, amount3))
}