Dynamic Programming
Solve a problem by combining solutions to overlapping subproblems, computed once each. Recursion plus a table.
Level: advanced
What is it?
Dynamic programming (DP) solves problems that have optimal substructure (the best answer is built from best answers to smaller pieces) and overlapping subproblems (the same pieces recur). Top-down DP writes the recursion and memoizes results; bottom-up DP fills a table from the smallest subproblems upward. Either way each subproblem is solved once, turning exponential recursion into polynomial time.
Why does it matter?
DP is the tool for optimization and counting problems where greedy choices fail: minimum coins, longest common subsequence, knapsack, edit distance, and many scheduling problems. Recognizing the state and the recurrence is the skill interviews test.
Mental model
Doing a big sum on paper and writing down every intermediate result so you never recompute it. When the same partial sum is needed again, you read it off the page instead of redoing the arithmetic.
How it works
- State: what minimal information describes a subproblem (an index, a remaining amount, a pair of positions)?
- Recurrence: how does the answer for a state come from answers to smaller states?
- Base cases: the states whose answer is known directly.
- Top-down (memoization) is easier to write; bottom-up (tabulation) avoids recursion and can save memory by keeping only the previous row.
- Time is the number of states times the work per state; space is usually the table size.
- Greedy works when a locally best choice is always safe; DP is needed when you must compare alternatives.
Steps
- Define the state
- Write the recurrence
- Set the base cases
- Fill in order of dependencies
- Read the answer from the final state
Code example: Fewest coins, bottom-up
def coin_change(coins, amount):
INF = amount + 1
best = [0] + [INF] * amount # best[a] = fewest coins to make a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
best[a] = min(best[a], best[a - c] + 1)
return best[amount] if best[amount] != INF else -1
print(coin_change([1, 5, 6], 10)) # 2 (5 + 5)
print(coin_change([2], 3)) # -1 (impossible)Complexity and trade-offs
Time: Number of states × work per state (here O(amount × coins))
Space: O(number of states); often reducible to one row
Trade-offs
- Turns exponential search into polynomial time by remembering results
- Needs memory for the table, which can be large
- Finding the right state is the hard part
Real-world usage
- Optimization: knapsack, coin change, scheduling
- Sequence alignment and edit distance (diff tools, spell-check, bioinformatics)
- Parsing and shortest paths on DAGs
Common mistakes
- Choosing a state that leaves out information the recurrence needs.
- Applying DP when subproblems do not overlap, gaining nothing.
- Filling the table in an order that reads cells not yet computed.
Interview questions
How do you recognize a dynamic programming problem?
Look for optimal substructure and overlapping subproblems: a recursive solution that recomputes the same inputs, asking for a minimum, maximum, count, or feasibility over choices.
Memoization versus tabulation?
Memoization is recursion plus a cache: simple, and computes only needed states. Tabulation fills a table iteratively from the base cases: no recursion overhead and easier to optimize space.
Why does greedy fail for coin change with coins {1, 5, 6} and amount 10?
Greedy takes 6 first and then needs four 1s (5 coins), while 5 + 5 uses only 2. DP considers every coin at every amount and finds the true minimum.