Pattern Recognition Drill
Medium Dynamic Programming
The Problem
Given coin denominations and a target, find minimum coins needed.
What approach would you use?
Think about it before scrolling down.
dp[i] = min coins for amount i. For each amount, try every coin. O(amount * coins).
Greedy (largest coin first) FAILS for non-standard denominations (e.g., coins [1,3,4], target 6).
Common Trap
Greedy seems intuitive but doesn't always give optimal. DP is needed for correctness.