Description
Return the fewest positive-denomination coins needed to reach amount, with unlimited copies; return -1 if impossible.
Solution
def coin_change(coins, amount):
dp = [0] + [amount+1]*amount
for total in range(1,amount+1):
for coin in coins:
if coin <= total:
dp[total] = min(dp[total],dp[total-coin]+1)
return dp[amount] if dp[amount] <= amount else -1Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,5],11]- Output
4
5 + 2 + 2 + 2 uses four coins.
Example 2
- Input
[[2],3]- Output
-1
An odd total cannot be made from twos.
Example 3
- Input
[[3],0]- Output
0
The empty selection makes zero.
Approach
For each total, try every coin as its last coin and take the smallest reachable predecessor plus one.
Time & space
O(A c) time; O(A) space for amount A and c coin types.