网站建设 手机和pc,建站工具搭建网站,太原建站推广,做企业平台的网站原题链接 文章目录 需要添加的硬币的最小数量#xff1a;贪心算法实现题目概述示例分析 关键思路分析贪心算法的优化选择证明案例推演与算法实现 Python 实现结论 需要添加的硬币的最小数量#xff1a;贪心算法实现
题目概述
在这个困难难度的算法题中#xff0c;我们要解… 原题链接 文章目录 需要添加的硬币的最小数量贪心算法实现题目概述示例分析 关键思路分析贪心算法的优化选择证明案例推演与算法实现 Python 实现结论 需要添加的硬币的最小数量贪心算法实现
题目概述
在这个困难难度的算法题中我们要解决的问题是确定在给定一系列硬币面值的情况下为了使[1, target]区间内的每个整数都可以由这些硬币的某种组合表示出来需要向数组中添加的最小数量的硬币。
示例分析
示例 1: 输入: coins [1,4,10], target 19输出: 2 需要添加面值2和8的硬币 示例 2: 输入: coins [1,4,10,5,7,19], target 19输出: 1 仅需要添加面值为2的硬币 示例 3: 输入: coins [1,1,1], target 20输出: 3 需要添加面值为4、8和16的硬币
关键思路分析
解决问题的关键在于贪心算法的应用。核心思想是对于每个无法直接凑出的金额x添加面值为x的硬币以达到最优效果。通过这种方法我们可以逐步构建出一个能够覆盖[1, target]区间的硬币集合。
贪心算法的优化选择证明
我们可以根据这个案例抽象出普遍性做法。如果要靠添加硬币的方式才能凑出金额x如果此时已经能凑出[1, s]的金额x s 1我们应该选择添加面值x以得到更优结果。
证明
选择1. 如果添加小于x的面值 比如说添加面值small此时面值small与金额x - small也可以凑出金额x。增加了面值small后[small 1 small 2 small 3…small s]这些金额都可以通过与前面的金额相加凑出不妨想象一个区间[small 1, small s]因为x - small是位于[1, s]之中的x s 1且small至少为1因此x - small至少为x - 1 s所以现在可以凑出x了还可以凑出[x, small s]中的金额结合原来的[1, s]我们可以凑出[1, small s]的金额。
选择2. 添加面值x: 增加了面值x后[x 1 x 2 x 3…x s]这些金额都可以通过与前面的金额相加凑出因此可以结合前面的区间凑出[1, x s]。
选择3. 添加大于x的面值 如果添加面值x 1原先能凑出的区间为[1, s]因为x s 1x 1 s 2此时依然无法凑出金额x因为区间没有覆盖到x这个点上因此这个方案无效。
综合以上3个选择我们可以比对[1, small s]和[1, x s]因为small x所以毫无疑问选择x是最优做法。
案例推演与算法实现
从最基础的情况出发假设最初无法凑出金额1。此时我们添加面值为1的硬币。接着对于每个接下来的金额x如果当前硬币组合无法凑出x我们则添加面值为x的硬币从而扩展可凑金额的范围。这个过程一直持续到可以凑出target为止。
Python 实现
实现中首先对硬币进行排序然后遍历每个硬币同时维护一个变量x表示当前考虑的金额以及一个变量s表示目前可以凑出的最大金额。若当前硬币面值大于x则添加面值为x的硬币直到可以凑出当前考虑的硬币面值为止。这个过程一直重复直到可以凑出目标金额target。
class Solution:def minimumAddedCoins(self, coins: List[int], target: int) - int:coins.sort()ans 0x 1s 0for c in coins:if c x:while c x:s s xans 1x s 1s s cx s 1if s target:while target s:s s xans 1x s 1return ans结论
通过贪心算法的应用我们可以有效地解决这个算法问题确保在给定硬币面值的情况下以最小的硬币数量覆盖[1, target]的所有整数。
