Coin Change
LeetCode 322 • Medium • Dynamic Programming
Input: coins = [1, 2, 5], amount = 11 → Output: 3
Min coins to make amount. dp[i] = min(dp[i-c]+1) for c in coins. dp[0]=0.
TimeO(amount × coins)nested loops
SpaceO(amount)dp array
Amount: 0
dp[amt]: —
Ready
Press Play or Step. We fill each amount with the fewest coins; narration translates the highlighted line into English.
TimeO(amount × coins)memoized
SpaceO(amount)memo + stack
3
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
PATTERN ▸ dp[amt] = min coins O(amount×coins) · O(amount)
① INIT
dp = [0] + [inf] * amount
② FILL DP
for amt in range(1, amount+1):
for c in coins:
if amt >= c: dp[amt] = min(dp[amt], dp[amt-c]+1)
③ RETURN
return dp[amount] if dp[amount] != inf else -1
▼ your implementation ▼
Verify your solution:
Practice until you don't need to look. Memoized: min_coins(amt) = min(1 + min_coins(amt-c)) for c in coins.
PATTERN ▸ Memoized min_coins(amt) O(amount×coins) · O(amount)
① BASE CASES
if amount == 0: return 0
if amount < 0: return inf
② MEMO CHECK
if amount in memo: return memo[amount]
③ RECURSE & STORE
memo[amount] = min(1 + coinChange(amt-c)) for c in coins
return memo[amount]
▼ your implementation ▼
Verify your solution: