【测试岗】手撕代码 - 零钱兑换
322. 零钱兑换
题目描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
题解
from math import infdef min_coins(coins, amount):# 创建一个数组来保存每个金额所需的最少硬币数，初始化为无穷大dp = [float('inf')] * (amount + 1)# 0金额所需硬币数为0dp[0] = 0# 遍历每个金额直到目标金额for i in range(1, amount + 1):# 遍历每种硬币for coin in coins:# 如果当前硬币面值小于等于当前金额if coin <= i:# 更新当前金额所需的最少硬币数dp[i] = min(dp[i], dp[i - coin] + 1)# 如果目标金额无法组成，则返回-1，否则返回最少硬币数return dp[amount] if dp[amount] != float('inf') else -1print(min_coins([1, 2, 5], 11))
print(min_coins([2], 3))
print(min_coins([1], 0))
1. 题目理解
我们需要用给定的硬币面额（coins）来凑成一个指定的总金额（amount）。目标是找到所需的最少硬币数量。如果无法凑成指定金额，返回 -1。题目允许使用的硬币数量是无限的。
2. 代码思路
这是一个经典的动态规划问题，目标是通过选择不同的硬币面额，最小化硬币数量以凑成给定金额。动态规划的思想是通过构建一个数组
dp，记录凑成每个金额所需的最少硬币数，从而自底向上地解决问题。具体步骤如下：
- 初始化动态规划数组
dp：
dp[i]表示凑成金额i所需的最少硬币数。首先我们将所有金额的值初始化为一个较大的数（如无穷大），表示暂时无法凑成这个金额。- 特别地，
dp[0] = 0，因为凑成金额 0 所需的硬币数是 0。
- 遍历所有的金额 i：
- 对于每个金额
i，我们尝试每一种硬币面额coin，如果当前硬币面额小于等于i，则通过状态转移方程更新dp[i]的值。- 状态转移方程为：
dp[i] = min(dp[i], dp[i - coin] + 1)，其中dp[i - coin]表示减去一个当前硬币后剩余金额的最优解。
- 结果判断：
- 当遍历完所有金额后，检查
dp[amount]的值。如果它仍然是无穷大，表示无法凑成该金额，返回 -1；否则，返回dp[amount]，即凑成amount所需的最少硬币数。3. 算法分析
时间复杂度：
- 内层循环遍历
coins，外层循环遍历amount，因此时间复杂度为 O(amount * n)，其中n是硬币的种类数。空间复杂度：
- 由于我们使用了一个大小为
amount + 1的数组来存储每个金额的最少硬币数，因此空间复杂度为 O(amount)。