Coins to Add for Every Total
coins is sorted from small to large. You want to be able to pay every total from 1 to target exactly, using each coin at most once. Return the fewest coins, of any values you choose, that must be added to make that possible.
Example 1
coins [1,3]
target 6
returns 1
With 1 and 3 the total 2 cannot be paid. Adding a 2 covers everything up to 6.
Example 2
coins [1,5,10]
target 20
returns 2
Add 2 and 4: then 1, 2, 4, 5 and 10 pay every total up to 22.
Constraints
0 <= len(coins) <= 601 <= coins[i] <= 10**91 <= target <= 10**9
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.