济南网站建设在哪里,网站自适应 常用尺寸,wordpress rss 全文,做解密类网站可行322. 零钱兑换 题目描述
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。
你可以认为每种… 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)。
