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.
Quick Context
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:
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.
Interactive Exploration Guide
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.
Key Takeaway
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.
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.