DP Without Fear
Intermediate · 24 min read · Problem-Solving Patterns, Dynamic Programming
From brute-force recursion to memoisation to a table, in four mechanical steps.
Dynamic programming has the scariest reputation in interview prep, mostly because it's usually taught backwards: here's a table, here's a formula, fill it in. Nobody explains where the formula came from. This lesson does it the other way round. DP is recursion that remembers.
If you're comfortable with recursion, you already know 80% of DP.
Why plain recursion is slow
Fibonacci, the classic: fib(n) = fib(n − 1) + fib(n − 2).
The four steps (always the same)
Define a function that answers the problem for a smaller piece, and write it by trusting smaller calls. The function's parameters are the state.
A complete worked example: min cost climbing stairs
Step 1 — recursion. Define best(i) = cheapest cost to stand on stair i. To stand on stair i, you came from i − 1 (paying cost[i − 1]) or from i − 2 (paying cost[i − 2]):
How to find the state (the hard part)
Ask these questions in order:
Top-down or bottom-up?
In an interview, writing the memoised version first is completely acceptable — and if you have time, converting it to a table shows mastery.
Practice ladder
Interview questions
- What's the difference between memoisation and tabulation?
- How do you know a problem can be solved with DP?
Further reading
Key takeaways
- DP is recursion that remembers: overlapping subproblems + caching.
- Four steps: brute-force recursion → memoise → table → shrink memory.
- The hard part is the state: what do you need to know to finish optimally? Define it in words.
- State the recurrence and base cases out loud before coding.
- Memoisation is a fine interview answer; tabulation adds stack safety and space savings.