Solve each subproblem once, write the answer down, and never compute it again. Watch a table fill in cell by cell and turn an exponential problem into a linear one.
Controls
n10
The DP Table
step 0
Insight
DP applies when a problem has overlapping subproblems — the same smaller question asked many times — and optimal substructure, where the best overall answer is built from best sub-answers.
cells filled0
naive calls–
answer–
Complexity
Fibonacci DPO(n)
KnapsackO(n·W)
Naive recursionO(2^n)
Dynamic Programming
Remember what you already worked out. That is genuinely the whole idea.
What this is
Dynamic programming solves a problem by breaking it into subproblems, solving each once, and storing the answers. It applies when the same subproblems keep reappearing — which is exactly when plain recursion wastes enormous effort.
The Two Conditions
Overlapping subproblems — the naive recursion asks the same question repeatedly. fib(30) computes fib(10) thousands of times.
Optimal substructure — the best solution is built from best solutions to subproblems. True for shortest paths and knapsack; false for problems where a locally optimal choice can block a better global one.
If only the first holds you can still memoise for speed. If neither holds, DP is the wrong tool.
Memoisation vs Tabulation
Memoisation (top-down) — write the natural recursion, add a cache, return early on a hit. Minimal change to readable code, and it only computes subproblems you actually need. Costs stack space.
Tabulation (bottom-up) — fill a table from the smallest subproblem upward, no recursion at all. No stack risk and usually faster, but you must work out the correct fill order yourself.
The table in this lab is the tabulation view. Each cell depends only on cells already filled — the amber cells show exactly which ones.
Reading the Recurrence
Every DP problem reduces to a recurrence — a formula for one cell in terms of earlier cells. The panel shows the one in use. For edit distance:
# delete# insert# replace Once you have the recurrence and the base cases, the code writes itself. Finding the recurrence is the hard part — the implementation is mechanical.
The Payoff Is Enormous
Naive Fibonacci is O(2ⁿ); with DP it is O(n). At n = 40 that is roughly a billion operations versus forty. Compare the "cells filled" and "naive calls" figures as you raise n — the gap is not a constant factor, it is a different universe.
The Classic Problems
0/1 Knapsack — maximise value within a weight limit. Each cell asks: with this capacity and these items available, what is the best I can do?
Edit distance — minimum insertions, deletions and substitutions to turn one string into another. Powers spell-checkers and diff tools.
Coin change — fewest coins making a target. A greedy approach fails on awkward denominations; DP always succeeds.
Remembering instead of recomputing
Dynamic programming applies when a problem has two properties:
Overlapping subproblems. The same smaller problem is solved many times.
Optimal substructure. The best solution is built from the best solutions to its subproblems.
Naive recursive Fibonacci demonstrates the first spectacularly:
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2)
Computing fib(40) makes about 331 million calls, because fib(35) is recomputed millions of times. It is O(2ⁿ).
Store each result the first time it is computed and the tree collapses:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2)
O(n) time, and fib(40) returns instantly. One decorator, three orders of magnitude.
n
Naive calls
Memoised calls
10
177
11
20
21,891
21
40
331,160,281
41
Top-down and bottom-up
Two ways to write the same solution, and they differ in style rather than complexity.
Memoisation (top-down) is recursion plus a cache. Write the recurrence naturally and add @lru_cache. Only the subproblems actually needed are computed, which matters when the state space is large and sparsely visited.
Tabulation (bottom-up) fills a table from the base cases upwards, iteratively. No recursion, so no stack limit, and usually a smaller constant factor.
def fib_table(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
That last version illustrates the further optimisation available to many DP solutions: if each state depends only on the previous one or two, the whole table is unnecessary and two variables suffice. Space drops from O(n) to O(1).
Memoisation
Tabulation
Style
Recursive
Iterative
Computes
Only needed states
All states
Stack risk
Yes
No
Space optimisation
Harder
Often easy
Easier to write
Usually
Usually not
Write it top-down first, because the recurrence is what you actually have to think about. Convert to bottom-up if recursion depth or constant factors matter.
Recognising a DP problem
The signals are recognisable once you have seen a few:
"Find the maximum/minimum/number of ways" over a set of choices.
Each step has a small number of options, and the choices interact.
Brute force is exponential because the same situations recur.
The answer for n depends on answers for smaller inputs.
The method is always the same four steps: define the state (what distinguishes one subproblem from another), write the recurrence (how a state's answer follows from smaller states), identify the base cases, and decide the order of computation.
Defining the state is the hard part. Everything else is mechanical once the state is right.
The two conditions, and what happens when one is missing
Dynamic programming needs overlapping subproblems and optimal substructure. Those are not decoration -- each one is doing a specific job, and the cleanest way to understand them is to watch what breaks when a problem has one but not the other.
example_01.pyPython
# CONDITION 1: overlapping subproblems. Without them, memoising is pure
# overhead -- the cache is written and never read.
calls = {"n": 0}
hits = {"n": 0}
def fib(n, memo=None):
calls["n"] += 1
if memo is not None and n in memo:
hits["n"] += 1
return memo[n]
if n < 2:
return n
v = fib(n - 1, memo) + fib(n - 2, memo)
if memo is not None:
memo[n] = v
return v
calls["n"] = hits["n"] = 0
fib(22)
plain = calls["n"]
calls["n"] = hits["n"] = 0
fib(22, {})
print("fib(22): %d calls plain, %d with a memo (%d cache hits)"
% (plain, calls["n"], hits["n"]))
# Now merge sort, which also splits into two subproblems at every level.
msplits = {"n": 0}
seen = {}
def msort(a):
key = tuple(a)
msplits["n"] += 1
seen[key] = seen.get(key, 0) + 1
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = msort(a[:mid]), msort(a[mid:])
out = []
while left and right:
out.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
return out + left + right
import random
msort(random.Random(1).sample(range(200), 200))
repeats = sum(1 for v in seen.values() if v > 1)
print("merge sort on 200 items: %d subproblems, %d of them repeated"
% (msplits["n"], repeats))
# Zero repeats. Merge sort has optimal substructure but NO overlap: each
# subproblem is a different slice, so a cache would never hit. That is
# why merge sort is divide-and-conquer and not dynamic programming --
# the distinction is exactly this measurement.
# CONDITION 2: optimal substructure. The best solution must be buildable
# from best solutions to subproblems. Coin change has it:
def coins_dp(target, coins):
best = [0] + [float("inf")] * target
for t in range(1, target + 1):
for c in coins:
if c <= t and best[t - c] + 1 < best[t]:
best[t] = best[t - c] + 1
return best[target]
def coins_greedy(target, coins):
n, left = 0, target
for c in sorted(coins, reverse=True):
while left >= c:
left -= c
n += 1
return n if left == 0 else None
print()
print("%-16s %10s %10s" % ("coin system", "greedy", "DP"))
for name, coins, target in (("1, 5, 10, 25", [1, 5, 10, 25], 30),
("1, 3, 4", [1, 3, 4], 6),
("1, 7, 10", [1, 7, 10], 14)):
print("%-16s %10s %10d" % (
name + " -> %d" % target, coins_greedy(target, coins),
coins_dp(target, coins)))
# The greedy answers are wrong on the second and third systems: 6 is 3+3
# (two coins) and greedy takes 4+1+1 (three); 14 is 7+7 (two) and greedy
# takes 10+1+1+1+1 (five). Greedy assumes the biggest coin is always part
# of the best answer, which is a claim about the coin system, not about
# the problem. DP makes no such assumption -- it tries every coin at
# every total, which is why it costs more and why it is always right.
Output
Things to try
Run Fibonacci and step through. Each cell reads exactly two earlier cells — highlighted in amber — and is computed once and only once.
Compare cells filled against naive calls. At n = 16 it is 17 versus nearly 2,000.
Switch to edit distance with kitten/sitting. The answer is 3, and the table shows every intermediate alignment cost.
Try knapsack. Each cell chooses between taking the item and skipping it — the amber cells show both options being compared.
Look at the bottom-right cell. In every one of these problems it holds the final answer, built entirely from the cells before it.
Worth remembering
Dynamic programming is recursion plus memory. Spot repeated subproblems, define a recurrence, fill a table in dependency order, and exponential work collapses to polynomial. The difficulty is never the code — it is finding the recurrence.
The classic problems, by state shape
Problem
State
Recurrence sketch
Fibonacci
i
f(i) = f(i-1) + f(i-2)
Climbing stairs
i
Same as Fibonacci
Coin change
amount
min over coins of 1 + f(amount - coin)
0/1 knapsack
(item, capacity)
Take it or leave it, whichever is better
Longest common subsequence
(i, j)
Match: 1 + f(i-1, j-1), else max of skipping either
Edit distance
(i, j)
Insert, delete or substitute, whichever is cheapest
Longest increasing subsequence
i
1 + max over previous smaller elements
Two observations from that table.
The state dimension determines the complexity. A one-dimensional state over n values is O(n) states; a two-dimensional state over two strings is O(nm). Multiply by the work per state to get the total.
Two-dimensional string problems are one family. Longest common subsequence, edit distance and sequence alignment share a shape: compare the current characters, and either match them or skip one. Learning one gives you the others.
Where it is used in practice
diff and version control — longest common subsequence on lines.
Spell checking and fuzzy matching — edit distance.
Bioinformatics — Needleman-Wunsch and Smith-Waterman sequence alignment are DP.
Speech recognition — the Viterbi algorithm finds the most likely state sequence.
Resource allocation and scheduling — knapsack variants.
Text justification — the line-breaking algorithm in TeX.
Reinforcement learning — value iteration is DP over states.
That list is worth noticing because DP has a reputation as an interview topic. It is in fact behind several tools you use daily.
Common mistakes
A state that does not capture everything relevant. If two situations with the same state have different answers, the state is wrong. This is the root cause of most incorrect DP solutions.
Missing or wrong base cases. Off-by-one at the boundary propagates everywhere.
Mutable default arguments as caches.def f(n, memo={}) shares one cache across all calls, which sometimes helps and sometimes leaks between unrelated inputs.
Recursion depth. Top-down on n = 100,000 exceeds Python's stack limit. Convert to iteration.
Unhashable arguments with lru_cache. Lists cannot be cached; convert to tuples.
Filling the table in the wrong order, so a state is computed before its dependencies.
Questions people ask
How do I know a problem is DP? Exponential brute force, overlapping subproblems, and an answer built from smaller answers. "Count the ways" or "find the optimum over choices" are strong hints.
Memoisation or tabulation? Write memoisation first — it is easier to get right. Convert if you hit stack limits or need the space optimisation.
What is the difference from divide and conquer? Divide and conquer splits into independent subproblems (merge sort). DP applies when they overlap, so caching pays.
What is the difference from greedy? Greedy commits to a locally best choice and never reconsiders. DP considers all choices and keeps the best. Greedy is faster and only correct for some problems.
Can I always reduce the space? Only when each state depends on a bounded window of earlier states. A full two-dimensional dependency needs the table.
Is lru_cache enough? For most top-down solutions, yes — it is C-speed and handles eviction. Use an explicit dict when you need to inspect or control the cache.
Recap in one screen
DP applies when subproblems overlap and the optimum is built from sub-optima.
Memoisation is recursion plus a cache; tabulation fills a table iteratively from the base cases.
Defining the state correctly is the whole problem; the recurrence follows from it.
Complexity is the number of states times the work per state.
It powers diff, spell checking, sequence alignment, Viterbi decoding and scheduling — not only interviews.
Where to practise this
Four problems that between them cover the whole method — overlapping subproblems, a case where greedy is plainly wrong, a reformulation that beats the obvious recurrence, and the rolling variables that remove the table:
Climbing stairs — the smallest complete DP, with the call counts that justify memoising.
Coin change — and the counterexample where taking the biggest coin first loses.
The same Fibonacci written three ways, with the call counts printed side by side, then a coin-change table you can read row by row. The gap between 240,000 calls and 26 is the entire subject.
dynamic_programming.pyPython 3
# Dynamic programming: solve each subproblem once, then reuse the answer.
calls = {"naive": 0, "memo": 0}
def fib_naive(n):
calls["naive"] += 1
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
def fib_memo(n, cache=None):
if cache is None:
cache = {}
calls["memo"] += 1
if n in cache: # already solved: reuse it
return cache[n]
value = n if n < 2 else fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
cache[n] = value # top-down: remember on the way out
return value
def fib_table(n):
table = [0, 1] + [0] * (n - 1) # bottom-up: no recursion at all
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
N = 25
print(f"fib({N}) =", fib_naive(N), f"in {calls['naive']} calls")
print(f"fib({N}) =", fib_memo(N), f"in {calls['memo']} calls")
print(f"fib({N}) =", fib_table(N), "in one loop, O(1) memory if you keep two values")
# --- coin change: the classic table ------------------------------------
def coin_change(coins, target):
# best[t] = fewest coins that make t; inf means "cannot be made"
best = [0] + [float("inf")] * target
for t in range(1, target + 1):
for c in coins:
if c <= t and best[t - c] + 1 < best[t]:
best[t] = best[t - c] + 1
return best
coins = [1, 3, 4]
target = 11
best = coin_change(coins, target)
print()
print(f"coins {coins}, making every amount up to {target}:")
print(" amount:", "".join(f"{t:>4}" for t in range(target + 1)))
print(" coins :", "".join(f"{c:>4}" for c in best))
print()
print(f"{target} needs {best[target]} coins (4+4+3).")
print("Greedy would take 4+4+1+1+1 = 5. Each cell here was computed once and")
print("read many times - that is the whole method.")
Output
How the code works
if n in cache: return cache[n]Memoisation in one line. The recursion is unchanged; it simply stops descending into a subtree whose answer is already known, which collapses an exponential tree into a linear path.
cache[n] = valueTop-down: the answer is stored on the way back out. The structure of the code still mirrors the recurrence, which is why memoisation is usually the easier of the two directions to write.
table = [0, 1] + [0] * (n - 1)Bottom-up: fill the small cases first and build upwards, so no call stack is involved at all. Same complexity, no recursion limit, and usually faster in practice.
if c <= t and best[t - c] + 1 < best[t]:The recurrence, and it is the only piece of real thinking in the whole method: the best way to make t is one coin on top of the best way to make t − c, for whichever c wins.
best[t - c]Reading a cell that was filled earlier in the same loop. Dynamic programming needs subproblems that overlap — if each one were used once, a table would buy nothing over plain recursion.
Change one thing
Raise N to 30 and watch the naive count. Around 35 it stops being a demonstration and starts being a wait.
Print the whole best row for coins = [1, 5, 10, 25]. Every value matches the greedy answer — which is exactly why greedy appears to work on real currency.
Track which coin won each cell in a second list, then walk it backwards to recover the actual coins rather than just the count.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Dynamic programming needs subproblems that:
If each subproblem were needed once, a table would buy nothing over plain recursion. The reuse is what pays for the storage.
Top-down memoisation and bottom-up tabulation differ in that tabulation:
Same complexity, no recursion limit, and usually a better constant. Memoisation is normally the easier one to write, because the code still mirrors the recurrence.
For coins [1, 3, 4] and target 6, greedy takes 4+1+1. What does the DP table give?
The table computes every amount up to the target, so it finds the combination greedy's one-way choice never considers.
Cheat sheet
Dynamic Programming
Solve each subproblem once, write the answer down, and never compute it again. Watch a table fill in cell by cell and turn an exponential problem into a linear one.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.