Break problems into overlapping subproblems and cache the answers, bottom-up or top-down.
What dynamic programming is
DP applies when a problem decomposes into subproblems that overlap - the same smaller question is asked many times - and satisfies optimal substructure: the best answer to the whole builds from best answers to parts. Cache each subproblem's answer the first time and an exponential recursion collapses to polynomial work.
There are two mechanical styles. Top-down: write the natural recursion, add a memo. Bottom-up: fill a table from the smallest cases upward. They compute the same thing; top-down is faster to write correctly under pressure, bottom-up exposes the space optimization (often only the last row or two variables are needed).
How to recognize it
Signals: 'count the number of ways', 'minimum cost / maximum value to reach or build X', 'can it be done' over sequences with choices at each step, longest/shortest subsequence-style measures. Also: a backtracking solution whose branches keep recomputing identical suffixes - that redundancy is the invitation.
The skill that actually gets tested is state design. Ask: what is the minimal description of 'where I am' such that the future depends only on it, not on how I got here? One sentence of the form 'dp[i] = the best X using the first i items' is worth more than any code.
A working method
1) Define the state in prose. 2) Write the recurrence as a choice: dp[i] combines a small, explicit set of options (take or skip, which predecessor, which last step). 3) Set base cases carefully - they encode the empty problem. 4) Pick an order (or memoize and let recursion find it). 5) Read off the answer and only then optimize space.
When stuck, enumerate the last decision: 'the final step was either ... or ...'. Nearly every recurrence falls out of naming what the last move could have been.
pseudocode
# canonical shape: 'take or skip' (house robber)
# dp[i] = max money from the first i houses
dp[0] = 0, dp[1] = value[0]
for i in 2 .. n:
dp[i] = max(dp[i-1], # skip house i
dp[i-2] + value[i-1]) # rob house i
return dp[n]
Complexity
Time = number of states x work per transition. dp[i] over n items with O(1) transitions is O(n); two-sequence states dp[i][j] are O(n x m); a state that scans all predecessors (as in longest increasing subsequence's simple form) is O(n^2). Space matches the table but usually compresses: if dp[i] reads only dp[i-1] and dp[i-2], two variables suffice.
Common pitfalls
Under-specified state: if the future depends on something your state omits (like whether the previous element was taken), the recurrence is simply wrong. Fix the state, not the code around it.
Base cases that don't mean anything: dp[0] should answer the genuinely empty problem. Guessing 0 or 1 without asking what the empty case means breeds off-by-ones.
Iteration order violating dependencies in bottom-up tables - reading cells not yet computed.
Counting problems: ways-to-make-amount with coins iterated in the wrong loop order counts permutations instead of combinations. Coins outer = combinations; amount outer = permutations. Know which one the problem wants.
Jumping to a 2D table when 1D suffices, or optimizing space before the recurrence is even right.
Worked examples
1. Climbing stairseasy
You climb a staircase of n steps taking 1 or 2 steps at a time. How many distinct ways can you reach the top?
Name the last move: you arrived at step n from n-1 (a 1-step) or from n-2 (a 2-step). Those two option-sets are disjoint and exhaustive.
So ways(n) = ways(n-1) + ways(n-2) - Fibonacci in costume. State: dp[i] = number of ways to reach step i.
Base cases from meaning: one way to stand at the start (do nothing), one way to reach step 1.
dp[i] depends only on the previous two values, so two rolling variables replace the array: O(n) time, O(1) space.
pseudocode
prev2 = 1 # ways to reach step 0
prev1 = 1 # ways to reach step 1
for i in 2 .. n:
curr = prev1 + prev2
prev2 = prev1; prev1 = curr
return prev1
Remember: Enumerate the last move and the recurrence appears; notice the shallow dependency and the table shrinks to two variables.
2. Coin change (fewest coins)medium
Given coin denominations and a target amount, return the fewest coins needed to make the amount, or -1 if impossible.
Greedy fails here - with coins {1, 3, 4} and amount 6, greedy takes 4+1+1 but the answer is 3+3. That failure is the cue for DP.
State: dp[a] = fewest coins to make amount a. Last move: the final coin was some c, so dp[a] = 1 + min over coins of dp[a - c].
Base: dp[0] = 0 (zero coins make zero). Initialize the rest to infinity so unreachable amounts stay marked.
Fill a from 1 to amount; answer is dp[amount] or -1 if still infinite. O(amount x coins) time, O(amount) space.
pseudocode
dp = [0] + [infinity] * amount
for a in 1 .. amount:
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[amount] if finite else -1
Remember: When greedy's locally-best coin provably fails, 'try every last coin and take the min' is the recurrence - infinity marks the unreachable.
3. Longest common subsequencemedium
Given two strings, return the length of their longest common subsequence (characters in order, not necessarily contiguous).
Two sequences means a two-index state: dp[i][j] = LCS length of the first i chars of s and first j of t.
Last-move enumeration: if s[i-1] == t[j-1], that character extends the best of both prefixes: 1 + dp[i-1][j-1]. Otherwise drop the last char of one side: max(dp[i-1][j], dp[i][j-1]).
Base row and column are 0 - an empty string shares nothing. Fill row by row; every read is up or left, so order is safe.
O(n x m) time; space drops to one row since only the previous row is read. This table is the parent of edit distance and diff tools.
pseudocode
dp = (n+1) x (m+1) zeros
for i in 1 .. n:
for j in 1 .. m:
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[n][m]
Remember: Two sequences, two indices: compare last characters - match extends the diagonal, mismatch drops one side and takes the max.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1What two properties make a problem suitable for DP?
Sorted input and distinct elements
✓ Overlapping subproblems and optimal substructure
Small input and integer values
A greedy choice and a base case
Overlap makes caching pay (the same subproblem recurs); optimal substructure makes cached sub-answers composable into the global answer. Without overlap, plain divide-and-conquer suffices; without substructure, cached values don't help.
2What is the most productive first step when facing a suspected DP problem?
Choose between top-down and bottom-up
✓ Write a one-sentence definition of the state: dp[...] = exactly what
Allocate the table
Look for a greedy shortcut
The state definition dictates the recurrence, the bases, and the order. Most failed DP attempts are under-specified states, not coding errors - the future must depend only on the state.
3How is the recurrence usually discovered?
By pattern-matching against known problems
✓ By enumerating what the last decision could have been and combining the resulting subproblems
By induction on the input length
By profiling the brute force
'The last step was a 1-step or a 2-step', 'the last coin was c', 'the last characters match or not' - naming the final move partitions the problem into the sub-cases the recurrence combines.
4When can a DP table's space be reduced?
Always, to O(1)
✓ When each state reads only a bounded recent window (previous row / last two cells), keep just that window
Only in top-down implementations
When the answer is boolean
Space equals what transitions still need. dp[i-1], dp[i-2] means two variables; a row that reads only the previous row means two rows (or one, updated in the right direction). Reconstruction of the actual solution may still need the full table.
✓ the locally best coin can exclude combinations that are globally better, as with {1,3,4} making 6
greedy cannot handle amount 0
it doesn't fail - greedy is optimal for all coin systems
Greedy on {1,3,4} for 6 picks 4+1+1 (three coins) while 3+3 uses two. Optimality of greedy depends on special coin systems; DP's try-every-last-coin min is correct for all of them.
Frequently asked questions
Top-down or bottom-up - which should I use in interviews?
Whichever you can produce correctly fastest - usually top-down, since it is the brute force plus a cache. Convert to bottom-up when the interviewer asks about iterative versions or when space optimization matters; the table order mirrors the recursion's dependencies.
How do I tell DP from greedy?
Try to break the greedy: one counterexample (like coins {1,3,4} for amount 6) settles it. If every locally best choice provably stays globally safe, greedy wins on simplicity; if not, DP's exhaustive-with-caching is the fallback.
How do I recover the actual solution, not just its value?
Either keep the full table and walk backwards re-asking which option produced each cell's value, or store a parent/choice marker alongside each state. Space-optimized rolling arrays sacrifice this - mention the trade before making it.
What are the classic state shapes worth memorizing?
Linear dp[i] over a sequence (rob/skip, climb), two-sequence dp[i][j] (LCS, edit distance), knapsack dp[capacity] with items iterated outside, and interval dp[l][r] over substrings. Most interview DP is one of these four wearing a costume.