网站自己建设国家城乡建设网站

原题链接

文章目录

• 需要添加的硬币的最小数量：贪心算法实现
• • 题目概述
  • • 示例分析
  • 关键思路分析
  • • 贪心算法的优化选择证明
    • 案例推演与算法实现
  • C++ 实现
  • 结论

需要添加的硬币的最小数量：贪心算法实现

题目概述

在这个困难难度的算法题中，我们要解决的问题是确定在给定一系列硬币面值的情况下，为了使[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 + 1，x + 1 = s + 2，此时依然无法凑出金额x，因为区间没有覆盖到x这个点上，因此这个方案无效。

综合以上3个选择，我们可以比对[1, small + s]和[1, x + s]，因为small < x，所以毫无疑问选择x是最优做法。

案例推演与算法实现

[案例推演与算法实现的内容保持不变]

C++ 实现

实现中，首先对硬币进行排序，然后遍历每个硬币，同时维护一个变量x表示当前考虑的金额，以及一个变量s表示目前可以凑出的最大金额。若当前硬币面值大于x，则添加面值为x的硬币，直到可以凑出当前考虑的硬币面值为止。这个过程一直重复，直到可以凑出目标金额target。

class Solution {
public:int minimumAddedCoins(vector<int>& coins, int target) {sort(coins.begin(), coins.end());long long ans = 0, s = 0, x = 1;for (auto c : coins) {if (c > x) {while (c > x) {s = s + x;x = s + 1;ans++;}}s = s + c;x = s + 1;}while (s < target) {s = s + x;x = s + 1;ans++;     }return ans;}
};

结论

通过贪心算法的应用，我们可以有效地解决这个算法问题，确保在给定硬币面值的情况下，以最小的硬币数量覆盖[1, target]的所有整数。