Coding interview pattern
Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
The idea
How the dynamic programming pattern works
Dynamic programming applies when a problem has optimal substructure (the answer is built from answers to smaller versions of the same problem) and overlapping subproblems (those smaller versions recur many times). Plain recursion would recompute the same subproblem exponentially often; DP computes each distinct subproblem exactly once and reuses the result, collapsing exponential time to polynomial.
There are two implementations of the same idea. Top-down memoization writes the natural recursion and caches results in a map or array keyed by the subproblem state, so each state is solved on first request and read thereafter. Bottom-up tabulation reverses the order: it fills a table from the base cases upward, which avoids recursion overhead and makes space optimisation easier. They have the same time complexity; choose memoization when the recursion is clearer and tabulation when you want to trim memory.
The hard skill DP tests is defining the state. Ask: what minimal set of variables fully describes a subproblem, what is the recurrence that combines smaller states into a larger one, and what are the base cases. Once the state and transition are right, the code is mechanical. In an interview, narrate the recurrence in plain English before writing it, because that is where the credit is.
Recognition
When to reach for it
- The problem asks for an optimal value (max, min, count of ways) over a sequence of choices.
- A brute-force recursion would recompute the same subproblems repeatedly.
- You can describe a subproblem with a small number of state variables.
- Greedy fails because a locally optimal choice does not guarantee the global optimum.
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| 1D DP (e.g. house robber) | O(n) | O(n) or O(1) optimised |
| 2D DP (e.g. edit distance) | O(n*m) | O(n*m) or O(min(n,m)) |
| Knapsack (capacity W) | O(n*W) | O(W) optimised |
Worked example
Walkthrough: House Robber
- 1Define the state: dp[i] is the most money robbable from the first i houses.
- 2Write the transition: at house i you either skip it (dp[i-1]) or rob it and add its value to dp[i-2].
- 3So dp[i] = max(dp[i-1], dp[i-2] + value[i]).
- 4Base cases: dp[0] = 0, dp[1] = value of the first house.
- 5Because each dp[i] only depends on the previous two, you can drop the array and keep two rolling variables for O(1) space.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
define state; recurrence dp[s] = combine(dp[smaller states]); set base cases; fill in dependency order; return dp[target]Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Climbing Stairs | Easy | The Fibonacci-shaped intro to DP. |
| House Robber | Medium | Linear DP with a skip-or-take choice. |
| Coin Change | Medium | Unbounded knapsack, minimise count. |
| Longest Common Subsequence | Medium | The canonical 2D string DP. |
| Word Break | Medium | DP over string prefixes with a dictionary. |
| Edit Distance | Hard | 2D DP over two strings, three operations. |
Avoid these
Common pitfalls
- Choosing a state that is incomplete, so the recurrence is wrong.
- Wrong iteration order in tabulation, reading cells before they are filled.
- Forgetting base cases or off-by-one in the table dimensions.
- Reaching for DP when greedy or a closed form is correct and simpler.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Define the state in plain English before writing anything, for example dp[i] is the most money robbable from the first i houses; the interviewer awards most of the credit for a correct, complete state definition.
Write the recurrence as a single sentence describing the choice at each step (skip this house or rob it) and only then translate it to a formula; the English version is what proves you understand it.
Start with the clear top-down memoised recursion if tabulation is fiddly, then mention you could convert it to bottom-up and optimise the space; showing both directions signals depth.
Also searched as
dp interview questions - memoization vs tabulation - dynamic programming patterns
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- Dynamic Programming (Chapter 3, Algorithms) Jeff Erickson, University of Illinois Urbana-Champaign
- Lecture 15: Recursive Algorithms MIT OpenCourseWare, 6.006 Introduction to Algorithms
- Lecture 16: Dynamic Programming Subproblems MIT OpenCourseWare, 6.006 Introduction to Algorithms
Build the toolkit
More patterns worth learning
Recognition wins coding rounds. The more shapes you can name on sight, the faster a solution arrives.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Breadth-First Search (BFS)
Explore level by level with a queue; the natural fit for shortest paths on unweighted graphs.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.