[Verse 1]
Got a problem with some change to make today
Minimize the coins but find the optimal way
Dynamic programming gonna save the day
Bottom up or top down, either way we slay
Start with base case, zero change is free
Build up solutions systematically
For each amount, check every coin we got
Take the minimum, that's the winning spot
[Chorus]
Break it down, build it up
Coin by coin, fill the cup
Memo table, save the state
Optimal sub, don't be late
Greedy fails but DP wins
Bottom up is where it begins
Coin change, rearrange
Dynamic programming in the game
[Verse 2]
Create a table, size amount plus one
Fill with infinity, except index zero's done
For every coin denomination in our set
Check if current amount can be met
If coin value's less than or equal to i
Take the min of what we got and what we try
One plus table at position i minus coin
That's the recurrence, let the solutions join
[Chorus]
Break it down, build it up
Coin by coin, fill the cup
Memo table, save the state
Optimal sub, don't be late
Greedy fails but DP wins
Bottom up is where it begins
Coin change, rearrange
Dynamic programming in the game
[Bridge]
Time complexity's amount times coins
Space complexity's linear, no random joins
If the final answer's still infinity
No solution exists, that's the reality
Trace back the path if you need to know
Which coins to use, let the algorithm show
[Verse 3]
Top down approach with memoization
Recursive calls with optimization
If we've seen this amount before today
Return the cached result right away
Base case zero, recursive relation
One plus minimum of each combination
Both approaches give the same result
Choose your style, that's the default
[Chorus]
Break it down, build it up
Coin by coin, fill the cup
Memo table, save the state
Optimal sub, don't be late
Greedy fails but DP wins
Bottom up is where it begins
Coin change, rearrange
Dynamic programming in the game
[Outro]
From pennies to quarters, dollars to cents
Dynamic solutions, no time to repent
Master coin change, you've learned the art
Optimal substructure, that's the smart part