网站推广的方法有博物馆网站建设必要

网站推广的方法有,博物馆网站建设必要,icp域名备案查询,为什么营销型网站比普通网站建站贵给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。你可以认为每种硬币的数量是无限的。示例 1表示不同面额的硬币以及一个整数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提示1 coins.length 121 coins[i] 0 amount 解题思路动态规划定义状态设dp[i]表示 “凑成金额i所需的最少硬币数”。初始化初始化dp数组长度为amount 1值为amount 1因为最多需要amount个 1 元硬币用amount 1表示 “无法凑成”令dp[0] 0凑成金额 0 不需要硬币。状态转移遍历每个金额i从 1 到amount对每个硬币coin若coin ≤ i则dp[i] min(dp[i], dp[i - coin] 1)选当前硬币时硬币数 凑成i-coin的最少硬币数 1。结果判断若dp[amount]仍为初始值amount 1说明无法凑成返回-1否则返回dp[amount]。Python代码from typing import List class Solution: def coinChange(self, coins: List[int], amount: int) - int: 零钱兑换问题计算凑成指定金额所需的最少硬币数 :param coins: 可用的硬币面额列表非负整数无重复 :param amount: 目标凑单金额非负整数 :return: 最少硬币数若无法凑成返回-1 # 边界条件1目标金额为0无需硬币 if amount 0: return 0 # 边界条件2硬币列表为空 或 所有硬币面额都大于目标金额无法凑成 if not coins or min(coins) amount: return -1 # 初始化dp数组dp[i]表示凑成金额i所需的最少硬币数 # 初始值设为amount1最大可能需要amount个1元硬币用amount1标记无法凑成 dp [amount 1] * (amount 1) dp[0] 0 # 基准凑成金额0需要0个硬币 # 优化对硬币排序遇到大于当前金额的硬币可提前终止内层循环 coins.sort() # 遍历每个金额从1到目标金额 for i in range(1, amount 1): # 遍历每个硬币面额 for coin in coins: # 若当前硬币面额大于当前金额后续硬币更大直接break if coin i: break # 状态转移选当前硬币时硬币数凑成i-coin的最少硬币数1 dp[i] min(dp[i], dp[i - coin] 1) # 最终判断若dp[amount]仍为初始值说明无法凑成否则返回最少硬币数 return dp[amount] if dp[amount] ! amount 1 else -1 # ------------------- 测试用例 ------------------- if __name__ __main__: solution Solution() # 测试用例1常规可凑成示例1 coins1 [1, 2, 5] amount1 11 print(f测试用例1coins{coins1}, amount{amount1}) print(f最少硬币数{solution.coinChange(coins1, amount1)}) # 预期输出3551 # 测试用例2无法凑成示例2 coins2 [2] amount2 3 print(f\n测试用例2coins{coins2}, amount{amount2}) print(f最少硬币数{solution.coinChange(coins2, amount2)}) # 预期输出-1 # 测试用例3金额为0示例3 coins3 [1] amount3 0 print(f\n测试用例3coins{coins3}, amount{amount3}) print(f最少硬币数{solution.coinChange(coins3, amount3)}) # 预期输出0 # 测试用例4硬币面额无序 大额金额 coins4 [10, 5, 1, 25] amount4 41 print(f\n测试用例4coins{coins4}, amount{amount4}) print( f最少硬币数{solution.coinChange(coins4, amount4)}) # 预期输出3251051 → 修正25105141不251051是4个正确最优是251051 或 10*41实际最优是 251051414个代码会返回4LeetCode提交代码class Solution: def coinChange(self, coins: List[int], amount: int) - int: # 初始化dp数组默认值为“无法凑成”的标记amount1 dp [amount 1] * (amount 1) dp[0] 0 # 凑成金额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) # 判断结果若dp[amount]未被更新说明无法凑成 return dp[amount] if dp[amount] ! amount 1 else -1程序运行结果展示测试用例1coins[1, 2, 5], amount11 最少硬币数3 测试用例2coins[2], amount3 最少硬币数-1 测试用例3coins[1], amount0 最少硬币数0 测试用例4coins[10, 5, 1, 25], amount41 最少硬币数4总结本文探讨了使用动态规划解决零钱兑换问题。给定不同面额的硬币数组coins和目标金额amount需计算凑成金额的最少硬币数若无法凑成则返回-1。核心思路是通过动态规划数组dp记录每个金额的最小硬币数初始化dp[0]0其他为amount1表示不可达。遍历金额时对每个硬币面额进行状态转移dp[i] min(dp[i], dp[i-coin]1)。最终检查dp[amount]是否被更新未更新则返回-1。Python代码实现并通过测试用例验证如示例coins[1,2,5]和amount11输出3551。算法时间复杂度为O(amount×n)其中n为硬币种类数。