Coding interview pattern
Solve overlapping subproblems once, store the results, and build the answer up.
The idea
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
Cost
| 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
Translatable skeleton
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
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
In the interview
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.
dp interview questions - memoization vs tabulation - dynamic programming patterns
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Keep going
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Explore level by level with a queue; the natural fit for shortest paths on unweighted graphs.
See all coding patterns, the coding questions for your role, and the behavioral round.