题目
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1:
nums = [1, 3], n = 6
Return 1.
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].
Example 3:
nums = [1, 2, 2], n = 5
Return 0.
思路
说实话这道题没有想出来，还以为是个排列组合的问题，后来看了解释才恍然大悟。网上版本有很多种，我看的官网discussion里头的（这里）。
思路就是贪心法，假设目标是覆盖[0,n]，当前我们的组合能够覆盖[0,miss)的数字（注意这里的miss是目前无法到达的目标，我们得用贪心的思想让这个目标可达），并且目前正在处理有序数组中num[i]的数，那么有两种情况需要考虑：
- 如果num[i]比miss来的小，说明总有一个之前有的数，加上了num[i]以后能够到达miss完成任务。因为我们比较贪心，想让可覆盖的数越多越好，所以把num[i]带上，得到最大可以覆盖的范围[0,miss+num[i])；
- 如果num[i]比miss来的大，那么显然把num[i]加进去是无法得到miss的。比如：目前有0,1,2,…,9可以覆盖(即miss=10)，来了个num[i]=12的，显然加入12并不能解决覆盖10的问题（试想一下0+12都比10来的大）。所以最经济实惠的办法就是把miss自己加进去，这样还能把覆盖范围拓展到[0,miss*2)；
代码
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
long known_sum = 1, count = 0, i = 0;
while(known_sum <= n){
if(i < nums.size() && nums[i]<=known_sum){
//If we have a choice to expand the range
known_sum += nums[i++]; //The best choice is to add nums[i] in, which can reach up to (known+nums[i])
} else {
//Or we have to add in one item to make the best range, which means to double the range to 2*known_sum
known_sum += known_sum;
count++;
}
}
return count;
}
};