Standard Bar Dynamic Programming · DP on Subsequences O(n*amount) · O(amount)
A self-service kiosk holds unlimited stock of each coin denomination in its hopper and must dispense exact change for every refund request. Maintenance wants the hopper emptied as rarely as possible, so the firmware computes the fewest coins per payout. Some amounts simply cannot be formed from the available denominations, and the kiosk must flag those too.
Input: An array coins of distinct denominations and an integer amount.
Output: Return the fewest number of coins summing to amount, or -1 when it cannot be formed. Each denomination may be used unlimited times.
1 <= len(coins) <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4Input: {"coins":[1,2,5],"amount":11}
Output: 3
5 + 5 + 1 covers 11 with three coins.
Input: {"coins":[2],"amount":3}
Output: -1
Odd amounts are unreachable using only 2s.