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

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]的含义，根据题目的要求，确定递推公式，之后依据递推公式写出相应的代码。具体内容如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python编码：https://www.bilibili.com/cheese/play/ep1375307https://www.bilibili.com/cheese/play/ep1375307

• Java编码：https://www.bilibili.com/cheese/play/ep1368533https://www.bilibili.com/cheese/play/ep1368533

• Golang编码：https://www.bilibili.com/cheese/play/ep1368733https://www.bilibili.com/cheese/play/ep1368733

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 }

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

• Python编码：https://www.bilibili.com/cheese/play/ep1375307https://www.bilibili.com/cheese/play/ep1375307

• Java编码：https://www.bilibili.com/cheese/play/ep1368533

• Golang编码：https://www.bilibili.com/cheese/play/ep1368733

4.总结

对于动态规划，求解当前目标的状态dp[i]，则依赖于前期的状态（dp[i-1]或者dp[i-1]）。对于目标值amount，则依赖于amount之前的值，因此需要遍历遍历1 - amount元之间的所有值。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：https://www.bilibili.com/cheese/play/ss897667807https://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：https://www.bilibili.com/cheese/play/ss161443488https://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：https://www.bilibili.com/cheese/play/ss63997https://www.bilibili.com/cheese/play/ss63997

对于LeetCode数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：旧时王谢堂前燕，飞入寻常百姓家。