Dynamic programming has a reputation for being the scary part of the interview. People hear "DP" and assume they need a special kind of brain to spot the answer. That's not how it works. DP is a method you can follow, not a flash of insight you either have or don't.
I want to give you a process that takes the panic out of it. The goal isn't to memorize 50 patterns. It's to know what to do when you're staring at a problem you've never seen.
What DP actually is
Strip away the name. Dynamic programming is just recursion where you stop recomputing the same answers.
That's it. You have a problem that breaks into smaller versions of itself, those smaller versions overlap, and you save the results so you only solve each one once.
If you can write a recursive solution, you're most of the way to a DP solution. The "save the results" part is the easy bit you add at the end.
The order that keeps you calm
The mistake most people make is trying to write the fast table-based solution immediately. They reach for a 2D array and an inner loop before they understand the problem. Then they get lost in indices and freeze.
Do it in this order instead:
- Write the brute-force recursion. Don't worry about speed.
- Find what changes between calls. Those are your state.
- Add memoization so you don't repeat work.
- Only if you need to, convert it to a bottom-up table.
Most interviews are happy with steps 1 through 3. You rarely have to do step 4 under pressure, and when you do, it's a mechanical translation of what you already have.
Step 1: solve it slowly first
Take the classic: given coins of certain values, what's the fewest coins to make a target amount?
Don't think about tables. Ask the recursive question. "If I'm trying to make amount N, and I pick one coin, what's left?" You're now trying to make a smaller amount. Same problem, smaller input.
def min_coins(coins, amount):
if amount == 0:
return 0
if amount < 0:
return float('inf')
best = float('inf')
for c in coins:
best = min(best, 1 + min_coins(coins, amount - c))
return best
This is slow. It recomputes the same amounts over and over. But it's correct, and writing it is not hard. Get correct first.
Step 2: name your state
State is the set of values that fully describe where you are in the problem. In the coin example, the only thing that changes between calls is amount. So the state is just amount.
This question, "what changes between calls?", is the whole game. Sometimes it's one number. Sometimes it's an index plus a remaining budget. Sometimes it's two pointers into two strings. Once you can name the state, the rest is bookkeeping.
If you can describe your state in one sentence, you understand the problem. If you can't, you're not ready to write the loop yet.
Step 3: add memory
Now stop the repeated work. Cache results keyed by state.
from functools import lru_cache
def min_coins(coins, amount):
@lru_cache(maxsize=None)
def solve(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
return min(1 + solve(remaining - c) for c in coins)
return solve(amount)
One decorator. The recursion didn't change. You just added a memory of answers you've already computed. That's the leap from exponential to fast, and it costs you a single line.
In an interview, saying "I'll write the recursion, identify the state, then memoize it" out loud tells the interviewer you have a method. That's worth as much as the final code.
How to practice so it sticks
Don't grind random hard problems hoping patterns soak in. Build the muscle deliberately.
Pick five problems you can already solve with recursion. Solve each one again using the four steps above, out loud, as if someone is watching. The repetition is the point. You're training the order of operations, not collecting solutions.
Then do a few under a timer with someone asking you to explain your state choice. Mock interviews matter here because the panic is social. You can solve a problem alone and still blank when a person is watching. Practicing the talking part separately from the thinking part fixes that.
When you're stuck mid-problem
If you freeze, return to the one question: what changes between recursive calls? Write the slow version. Get something correct on the board. A working brute-force answer beats a blank screen, and it usually hands you the state for free.
DP rewards a calm, ordered approach far more than cleverness. Find the recursion. Name the state. Add memory. Do that enough times and the scary part stops being scary.