可视化图解算法77：零钱兑换（兑换零钱）

原创

用户11589437

修改于 2026-01-08 19:35:22

640

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

1.题目

描述

给定数组 coins ，coins中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个amount，代表要找的钱数，求组成amount的最少货币数。

如果无解，请返回-1.

数据范围：数组大小满足 0 ≤n≤10000 ，数组中每个数字都满足 0 <<val≤10000，0≤amount≤5000

要求：时间复杂度O(n×amount) ，空间复杂度 O(amount)。

示例 1：

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

示例 2：

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

示例 3：

输入：coins =[1], amount =0
输出：0

2. 题解思路

先明确变量i、dp[i]的含义，根据题目的要求，确定递推公式，之后依据递推公式写出相应的代码。具体内容如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3.编码实现

核心代码如下：

func coinChange(coins []int, amount int) int {
    //小于1的都返回0
    if amount < 1 {
        return 0
    }
    //1.定义状态. i：币值; dp[i]：币值为i的最少货币数; dp[i]表示凑齐i元最少需要多少货币数
    dp := make([]int, amount+1)
    //2.初始化边界条件：dp[0]=0 币值为0，需要最少的货币数为0; dp[i]=amount+1，设定最少的货币数不存在（无解）
    dp[0] = 0
    for i := 1; i < len(dp); i++ {
        dp[i] = amount + 1 //初始化为无解值
    }

    //3.确定递推公式：
    //3.1 遍历1-amount元
    for i := 1; i <= amount; i++ {
        //3.2 对于每一个目标值，每种面值的货币都要枚举
        for j := 0; j < len(coins); j++ { //从给定的币种遍历最合适的
            //只有面值不超过要凑的钱才能用
            if coins[j] <= i {
                //维护最小值
                cost := coins[j]
                dp[i] = min(dp[i], dp[i-cost]+1) //dp[i-cost]+1：上一次满足条件dp的基础之上加1张
            }
        }
    }
    //4.输出结果: 如果最终答案为maxInt代表无解
    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}

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

具体完整代码你可以参考下面视频的详细讲解。