需要添加的硬币的最小数量

标签: 贪心 数组 排序

难度: Medium

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。

示例 1：

输入：coins = [1,4,10], target = 19
输出：2
解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。

示例 2：

输入：coins = [1,4,10,5,7,19], target = 19
输出：1
解释：只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1 。

示例 3：

输入：coins = [1,1,1], target = 20
输出：3
解释：
需要添加面值为 4 、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16] 。 
可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3 。

提示：

  • 1 <= target <= 105
  • 1 <= coins.length <= 105
  • 1 <= coins[i] <= target

Submission

运行时间: 92 ms

内存: 26.4 MB

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        #[0,0]
        right=0
        res=0
        i,n=0,len(coins)
        coins.sort()
        while right<target:
            if i<n:
                cnum=coins[i]
                i+=1
                while cnum>right+1:
                    res+=1
                    right+=right+1
                right+=cnum 
            else:
                res+=1
                right+=right+1
               
        return res

Explain

该题解使用了贪心算法来确定最少需要添加的硬币数量以覆盖从1到target的所有金额。首先对硬币进行排序，然后用两个指标来跟踪：right表示当前可以通过已有硬币和新加入的硬币连续覆盖的最大值，i是遍历硬币数组的索引。在每次迭代中，如果当前硬币值大于right+1（表示有缺口无法用现有的硬币连续覆盖到该硬币的值），则添加一个硬币，其面值为right+1，以此填补缺口并尝试增大覆盖范围。这样保持覆盖范围的连续性，直到覆盖到target。最后，返回添加的硬币数量。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        right = 0  # 表示当前可以连续覆盖到的最大值
        res = 0  # 需要添加的硬币数量
        i, n = 0, len(coins)
        coins.sort()  # 对硬币面值进行排序
        while right < target:  # 循环直到覆盖到target
            if i < n:  # 如果还有硬币可以使用
                cnum = coins[i]  # 获取当前硬币的面值
                i += 1
                while cnum > right + 1:  # 如果当前硬币无法填补到right+1的缺口
                    res += 1  # 添加一枚硬币
                    right += right + 1  # 更新可覆盖到的最大值
                right += cnum  # 使用当前硬币更新可覆盖到的最大值
            else:  # 如果没有硬币可以使用
                res += 1  # 继续添加硬币
                right += right + 1  # 更新可覆盖到的最大值
        return res  # 返回需要添加的硬币数量

Explore

选择添加面值为right+1的硬币是因为，此时right+1是当前无法用已有硬币组合达到的最小金额。为了确保可以连续覆盖所有的金额直到target，必须首先填补这个最小的缺口。添加面值为right+1的硬币能够最有效地扩展已覆盖的金额范围，因此这是贪心策略中最优的选择，保证了每次操作都尽可能最大地增加覆盖范围。

当所有给定的硬币都已使用完毕，而right仍未达到target时，算法继续按照之前的策略添加硬币。即继续添加面值为right+1的硬币。这样做是因为每次添加面值为right+1的硬币仍然是填补当前金额连续性的最有效方式。通过不断添加这样的硬币，直到覆盖范围扩展到或超过target。

该贪心策略在多数情况下能够保证最小数量的硬币添加，但并不总是保证全局最优解。特别是在某些特殊组合的硬币面值时，可能存在更优的硬币组合策略。例如，如果硬币面值大而稀疏，且target相对较大，仅依靠贪心策略可能无法发现某些利用大面值硬币通过较少数量的添加来实现覆盖的策略。在这种情况下，可能需要更复杂的动态规划方法来找到真正的最小添加数量。

这里的数学原理基于从当前已覆盖的最大金额right出发，通过添加right+1的硬币，可以确保金额的连续覆盖范围扩展到right + (right + 1)。这意味着每次操作后，覆盖的金额范围几乎翻倍。这种策略利用了连续性和累加的特性，保证了每次添加硬币后，新的可覆盖金额范围是前一范围的扩展，从而有效地逼近目标金额target。