Dynamic programming is the topic candidates fear most, and the one interviewers at Google, Meta, and Amazon keep asking anyway. This hub collects everything on this site about DP interview prep: what the technique actually is, the patterns that cover the vast majority of interview questions, and the ten days of our 60-day challenge that take you from memoized Fibonacci to palindrome partitioning.
What Dynamic Programming Actually Is
Strip away the intimidating name and dynamic programming is one idea: solve each subproblem once, store the answer, and reuse it. A naive recursive Fibonacci recomputes fib(3) thousands of times for fib(40). DP computes it once. That single change turns an exponential O(2^n) algorithm into a linear O(n) one.
Every DP problem has two ingredients:
- Overlapping subproblems: the same smaller computation appears again and again.
- Optimal substructure: the best answer to the big problem is built from the best answers to smaller ones.
If a problem has both, you have two ways to exploit them:
- Memoization (top-down): write the natural recursion, then cache results so each state is computed once.
- Tabulation (bottom-up): fill a table from the smallest cases upward, so every answer you need is already there when you need it.
Interviewers rarely care which one you pick. They care that you can identify the state, write the recurrence, and analyze the complexity.
In practice, top-down is usually faster to write under pressure: you translate the recurrence directly into code and let the cache do the rest. Bottom-up wins when you need the space optimization (keeping only the last row of a table) or when recursion depth would blow the stack. A strong interview answer often starts memoized and ends with “and if space mattered, I’d convert this to a rolling one-dimensional table.”
Why FAANG Interviews Love DP
DP shows up disproportionately in FAANG onsites for a simple reason: it separates candidates who memorized solutions from candidates who can reason. A DP question tests four skills at once: recursion, problem decomposition, complexity analysis, and code hygiene under pressure. You cannot fake your way through “define the state for this problem” the way you can pattern-match a two-pointer question.
It also scales cleanly across the interview loop. Phone screens get the gentle versions (climbing stairs, house robber); onsites get the 2-D tables (edit distance, longest common subsequence); and the follow-up (“can you reduce the space?”) is practically guaranteed. Preparing DP properly therefore pays off at every stage, not just one round.
The good news: interview DP is far more repetitive than it looks. Most questions are one of a handful of patterns wearing different costumes. “Minimum cost to climb stairs,” “house robber,” and “maximum sum of non-adjacent elements” are the same recurrence. Learn the patterns, not the problems.
The DP Patterns That Cover Most Interviews
Our deep dive, 10 Dynamic Programming Patterns Every FAANG Interview Uses, walks through each pattern with worked examples. Here is the map at a glance, with the challenge day that teaches each one:
| Pattern | Classic problems | Learn it on |
|---|---|---|
| 1-D linear DP | Fibonacci, climbing stairs, house robber | Day 31 |
| 0/1 Knapsack | Subset sum, partition equal subset | Day 33 |
| Unbounded knapsack | Coin change, rod cutting | Day 37, Day 38 |
| Two-sequence DP | Longest common subsequence, edit distance | Day 32, Day 36 |
| Subsequence DP | Longest increasing subsequence | Day 35 |
| Interval DP | Matrix chain multiplication, burst balloons | Day 34 |
| Partition DP | Palindrome partitioning, word break | Day 39 |
If you can recognize which row a new problem belongs to, you already know the shape of its state and recurrence. That recognition is what separates a 20-minute solve from a 40-minute struggle.
Learn DP Day by Day
Days 30–39 of the 60-day challenge form a complete DP arc. Each lesson builds on the previous one:
- Day 30: Introduction to Dynamic Programming: overlapping subproblems, optimal substructure, and memoization vs. tabulation with side-by-side code.
- Day 31: Fibonacci and DP: the canonical first DP problem, plus space optimization from O(n) to O(1).
- Day 32: Longest Common Subsequence: your first 2-D table and the template for every two-sequence problem.
- Day 33: The Knapsack Problem: 0/1 knapsack, the single most reused DP pattern in interviews.
- Day 34: Matrix Chain Multiplication: interval DP, where the state is a range instead of a prefix.
- Day 35: Longest Increasing Subsequence: the O(n²) DP and the O(n log n) patience-sorting upgrade.
- Day 36: Edit Distance: insert/delete/replace transitions; the backbone of diff tools and spell checkers.
- Day 37: The Coin Change Problem: unbounded knapsack and why greedy fails on arbitrary coin systems.
- Day 38: Rod Cutting: revenue maximization and reconstructing the actual solution, not just its value.
- Day 39: Palindrome Partitioning: partition DP combined with a precomputed palindrome table.
Work them in order. LCS makes edit distance feel obvious; knapsack makes coin change feel like a variation instead of a new problem.
Complexity Quick Reference
The table below covers the DP problems interviewers ask most. Memorize the shapes, not the entries: a 2-D table over two strings is almost always O(m·n).
| Problem | Time | Space | Space-optimized |
|---|---|---|---|
| Fibonacci / climbing stairs | O(n) | O(n) | O(1) |
| House robber | O(n) | O(n) | O(1) |
| Longest common subsequence | O(m·n) | O(m·n) | O(min(m, n)) |
| Edit distance | O(m·n) | O(m·n) | O(min(m, n)) |
| 0/1 knapsack | O(n·W) | O(n·W) | O(W) |
| Coin change | O(n·amount) | O(amount) | n/a |
| Longest increasing subsequence | O(n²) | O(n) | O(n log n) time w/ binary search |
| Matrix chain multiplication | O(n³) | O(n²) | n/a |
| Palindrome partitioning (min cuts) | O(n²) | O(n²) | n/a |
Two things worth saying out loud in an interview: knapsack’s O(n·W) is pseudo-polynomial (it depends on the numeric value of W, not just input size), and most 2-D tables can be collapsed to one or two rows because each cell only reads from the previous row.
How to Practice DP Without Burning Out
- Recursion first. If you cannot write the brute-force recursion, no amount of table-filling will save you. Brush up with Recursion for Interviews: Think Before You Code.
- State before code. Say “dp[i] is the best answer using the first i items” out loud before typing anything. Most failed DP interviews die at an ill-defined state.
- One pattern per session. Solve three problems from the same row of the pattern table back to back. The repetition is the point.
- Redo, don’t review. Re-solving a problem cold after three days beats re-reading its solution ten times.
DP also pairs naturally with backtracking: many partition problems can be solved either way, and interviewers love asking which is better. Backtracking Explained: N-Queens to Subsets covers that boundary.
Related Resources
- 10 Dynamic Programming Patterns Every FAANG Interview Uses: the full pattern deep dive.
- Recursion for Interviews: Think Before You Code: the prerequisite skill for top-down DP.
- Backtracking Explained: N-Queens to Subsets: when to enumerate instead of optimize.
- The Data Structures Cheatsheet: complexity tables for everything else.
- How Long Does It Take to Get a FAANG Offer?: where DP fits in a realistic prep timeline.
- Arrays topic hub: most DP tables live in arrays; master the substrate first.