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)
Overview
Dynamic programming solves overlapping subproblems once and stores their answers for reuse. It applies when a problem has a manageable set of states and an optimal solution can be built from smaller states; a recurrence defines how those states relate.
The Two Conditions
Overlapping subproblems — the naive recursion asks the same question repeatedly. fib(30) computes fib(10) thousands of times.
Best substructure — the best solution is built from best solutions to subproblems. True for shortest paths and knapsack; false for problems where a locally best 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 really need. Costs stack space.
Tabulation (bottom-up) — fill a table from the smallest subproblem upward, no recursion at all. No stack risk and often 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.
Things to try with Dynamic Programming
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.
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 a few tools you use daily.
Common mistakes with Dynamic Programming
A state that omits relevant information. If two situations represented by the same state can lead to different answers, the state is incomplete. This is a common cause of 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. This 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.
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.
Predict, then reveal
About to run: Compare cells filled against naive calls. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
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
Cache subproblem results so they are solved once, not millions of times, and watch Fibonacci drop from exponential to linear.
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.