Medium
Coin Change
👶 The 5-Year-Old Summary
Minimum coins to make amount! Coins: [1,2,5], amount: 11 → 11 = 5+5+1 = 3 coins! Find the fewest coins!
🎮 Interactive Visualizer
coins = [1, 2, 5], amount = 11
🧠The Brain Hack
dp[amount] = 1 + min(dp[amount - coin])! For each amount, try each coin. Take minimum! Start with dp[0]=0, rest = infinity!
💻 The Clean Solution
def coin_change(coins, amount):
# dp[i] = min coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# coins=[1,2,5], amount=11 → 3 (5+5+1)Time: O(amount × len(coins))
Space: O(amount)