Medium Tabulation Dynamic Programming
In plain English: Find the fewest coins needed to make a given amount of money, or say it is impossible.
Build a table where dp[i] = min coins for amount i. For each amount, try every coin and take the best — classic unbounded knapsack.
Prompt
Given coin denominations and a target amount, find the minimum number of coins needed. Return -1 if impossible.
Try to write it from scratch before scrolling down.
Solution
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i and dp[i - c] + 1 < dp[i]:
dp[i] = dp[i - c] + 1 # use coin c
return dp[amount] if dp[amount] != float('inf') else -1
# Test: coin_change([1,5,10,25], 30) == 2 (25+5)
# Test: coin_change([2], 3) == -1