题目
给你一个下标从 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,2]，那么它们可以凑成1-3的任意金额；
如果有三个硬币[1,2,2]，那么可以凑成1-5的任意金额；
如果有三个硬币[1,2,4]，那么可以凑成1-7的任意金额；
注意，如果三个硬币为[1,2,5]，则无法凑成金额4。需要至少添加面额为1-4中的一个硬币方可凑成4。
因此，可以总结出以下规律：
如果前面的硬币能凑成1-n的任意金额，若下一个金币面额coins[i]满足coins[i] <= n + 1， 则加上这个硬币可以凑成1 - (n + n + 1)的任意金额；否则(coins[i] > n + 1)，至少无法凑成金额n + 1，需要补上一个面额为n + 1硬币方可继续。
因此，解决方法可以如下：
-
先对已有硬币
coins从小到大进行排序。 -
使用一个变量
current_range标记当前能够凑成任意金额的右区间(即已遍历的硬币能够凑成1 - current_range的任意金额)。 -
使用变量
added_cnt表示需要添加的硬币数；使用变量used_coins表示已使用的已有硬币数。 -
如果
current_range小于目标值target，持续以下循环：-
如果当前未使用的最小已有硬币
coins[used_coins]小于等于current_range + 1，则加上这个硬币可以凑成current_range + coins[used_coins]的任意金额，更新current_range和used_coins，继续循环； -
否则，则需要添加一个硬币，面额为
current_range + 1，以凑成current_range * 2 + 1的任意金额，更新added_cnt和current_range，继续循环；
-
代码
class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:
coins.sort()
current_range = 0 # 当前银币能够凑0..current_accepted_range的任意金额
added_cnt = 0 # 需要添加的硬币数
used_coins = 0 # 已经使用的硬币数
while current_range < target:
if used_coins < len(coins) and coins[used_coins] <= current_range + 1:
current_range += coins[used_coins]
used_coins += 1
else:
added_cnt += 1
current_range += current_range + 1
return added_cnt