【测试岗】手撕代码 - 零钱兑换

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，记录凑成每个金额所需的最少硬币数，从而自底向上地解决问题。

具体步骤如下：

1. 初始化动态规划数组 dp：

• dp[i] 表示凑成金额 i 所需的最少硬币数。首先我们将所有金额的值初始化为一个较大的数（如无穷大），表示暂时无法凑成这个金额。
• 特别地，dp[0] = 0，因为凑成金额 0 所需的硬币数是 0。

2. 遍历所有的金额 i：

• 对于每个金额 i，我们尝试每一种硬币面额 coin，如果当前硬币面额小于等于 i，则通过状态转移方程更新 dp[i] 的值。
• 状态转移方程为：dp[i] = min(dp[i], dp[i - coin] + 1)，其中 dp[i - coin] 表示减去一个当前硬币后剩余金额的最优解。

3. 结果判断：

• 当遍历完所有金额后，检查 dp[amount] 的值。如果它仍然是无穷大，表示无法凑成该金额，返回 -1；否则，返回 dp[amount]，即凑成 amount 所需的最少硬币数。

3. 算法分析

时间复杂度：

• 内层循环遍历 coins，外层循环遍历 amount，因此时间复杂度为 O(amount * n)，其中 n 是硬币的种类数。

空间复杂度：

• 由于我们使用了一个大小为 amount + 1 的数组来存储每个金额的最少硬币数，因此空间复杂度为 O(amount)。