Coding Interview Prep · 70 min · Python
Dynamic Programming: Memoization & Tabulation
DP isn't magic — it's recursion plus a memory that prevents redundant work.
Hiring signal: Defines subproblems and recurrences before coding, not after
What you will learn
- Identify overlapping subproblems and optimal substructure in a problem
- Convert a naive recursive solution to top-down DP with memoization
- Rewrite top-down DP as bottom-up tabulation
- Reduce space by using a 1D or rolling array when the recurrence allows
- Solve canonical patterns: Fibonacci, 0/1 knapsack, LCS, LIS, coin change
The Problem
DP is the pattern most people fear and most interviewers use to separate candidates. The fear comes from treating each problem as unique and trying to memorise solutions. The insight that dissolves the fear: every DP problem is just recursive brute force + a cache + (optionally) flipping to a table. The structure is always the same; only the subproblem definition changes.
The Concept
What DP Actually Is (The Unfearful Version)
Dynamic programming is not a new algorithm — it's an optimization of recursion. When you write a recursive solution to a problem and notice that the same subproblem is computed multiple times, you cache the result. That's it. DP = recursion + caching.
The classic example: Fibonacci. Naive recursion computes fib(5) by computing fib(3) twice, fib(2) three times, fib(1) five times. The recursion tree has exponential redundant work. Add a cache (memoization) and each subproblem is computed once — O(n) instead of O(2^n).
The two conditions that make DP applicable:
- Overlapping subproblems: the recursion recomputes the same state multiple times. If each subproblem is unique, caching doesn't help and DP is useless.
- Optimal substructure: the optimal answer to the big problem can be built from optimal answers to smaller subproblems. If the big problem's answer depends on non-optimal sub-answers, DP can't construct the optimum.
Once you identify these two properties, the solution follows a mechanical process: define what dp[i] means, write the recurrence that relates dp[i] to smaller states, set base cases, and choose an evaluation order (top-down with memoization or bottom-up with a table). The hard part is step 1 — defining the state. Once the state is right, the recurrence usually falls out naturally.
Unlock the full lesson
You've read the first 2 sections. The rest of this lesson covers The Framework, Build It, Interview Discipline, Ship It, Use It, Evaluation, Exercises, Key Terms, Common Pitfalls, Interview Framing — plus a hands-on lab, quiz, and project artifact.
Create a free account to unlock Phase 0 and Phase 1 of every course — no credit card.
Browse all courses · View pricing · DeVenture Academy