← Dynamic Programming · guided lesson
Dynamic Programming
the story
Dynamic programming
Every tool here exists because something was too slow or broke without it. Here is what.
Richard Bellman studied multistage decision problems at the RAND Corporation; his 1952 PNAS paper is titled "On the Theory of Dynamic Programming", and his 1957 book Dynamic Programming spread the method. In his 1984 autobiography he recalled choosing the name to shield the work: the Secretary of Defense, Wilson, had "a pathological fear and hatred of the word, research", while "dynamic" was a word even a Congressman couldn't object to. The dates don't quite fit — Charles Wilson took office in January 1953, after the 1952 paper already used the name — so read it as Bellman's own recollection.
the problem it solved
Multistage decisions — choosing a sequence of actions over time — where trying every sequence is hopeless, but each stage depends only on the state you are in.
why it matters: without it
Every "best way" or "how many ways" question with a choice at each step — routes, edits, budgets — would stay exponential: 45 stairs already needs billions of calls.
sources: Dreyfus — Richard Bellman on the Birth of Dynamic Programming (Operations Research, 2002), quoting Eye of the Hurricane (1984) ↗ · Bellman — On the Theory of Dynamic Programming (PNAS, 1952) ↗ · U.S. Department of Defense — Charles E. Wilson, Secretary of Defense 1953–1957 ↗
also in this chapter: Bottom-up tables and rolling rows · 0/1 and unbounded knapsack · Two-string DP: edit distance and LCS · Longest increasing subsequence (patience sorting)
the idea
The idea in 30 seconds
Many recursive solutions ask the same small question again and again. Fibonacci(40) calls fib(2) over 60 million times.
DP = recursion + a notebook: the first time you solve a subproblem, write the answer down; every later time, just read it.
Once you can say "the answer for n is built from the answers for smaller n", you can fill a table from small to big — no recursion needed.
picture this
An Excel sheet where cell B7 is =B5+B6. Excel doesn't re-add the whole column every time you look at B7: every cell already holds its value, and a new cell only reads cells that are finished. A DP table is that sheet — one cell per small question, each filled once, each built from cells above it or to its left.
watch it
Why plain recursion explodes
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Why plain recursion explodes
The same fib(k) is computed again and again (red). The counter shows how often each value is recomputed.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Memoization collapses the tree
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Memoization collapses the tree
Same recursion, plus a notebook. Repeated calls become instant memo hits (green leaves) — whole subtrees disappear.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 10
Read it once. Say it out loud once. Bas.
DP applies when a problem has overlapping subproblems (the same sub-question repeats) and optimal substructure (the best answer is built from best answers to sub-questions).
key idea 2 of 10
Read it once. Say it out loud once. Bas.
The ladder: plain recursion (exponential) → memoization / top-down (cache results) → tabulation / bottom-up (fill a table in order) → space optimisation (keep only the rows you still read).
key idea 3 of 10
Read it once. Say it out loud once. Bas.
The 5-step recipe: 1) state — what does dp[i] (or dp[i][j]) mean in one sentence; 2) transition — how it's built from smaller states; 3) base cases; 4) order — fill so every state you read is already done; 5) answer — which cell holds it.
key idea 4 of 10
Read it once. Say it out loud once. Bas.
Time ≈ number of states × work per state. Fibonacci: n states × O(1). LCS: m·n states × O(1). LIS: n states × O(n) = O(n²).
key idea 5 of 10
Read it once. Say it out loud once. Bas.
0/1 knapsack (each item once) loops capacity downward in a 1D array; unbounded (reuse allowed) loops upward. That single loop direction is the whole difference.
key idea 6 of 10
Read it once. Say it out loud once. Bas.
Two-string DP (LCS, edit distance): dp[i][j] = answer for the first i chars of one and the first j chars of the other. Compare the last characters and look at the 3 neighbours: ↖, ↑, ←.
key idea 7 of 10
Read it once. Say it out loud once. Bas.
Grid DP: dp[r][c] from the cell above and the cell to the left (and sometimes up-left). Edges have only one neighbour — they are your base cases.
key idea 8 of 10
Read it once. Say it out loud once. Bas.
Interval DP (palindromes, burst balloons): dp[i][j] for a range, filled from short intervals to long ones. Often O(n³).
key idea 9 of 10
Read it once. Say it out loud once. Bas.
Counting problems use +, optimisation problems use min/max, feasibility problems use ||. The skeleton is the same.
key idea 10 of 10
Read it once. Say it out loud once. Bas.
If dp[i] only reads dp[i-1] and dp[i-2], you only need two variables. If a 2D row only reads the previous row, you only need one or two rows.
spot the pattern
When you see this, think this
"Count the number of ways…"
Counting DP: dp[state] = sum of ways of the smaller states it comes from
"Minimum / maximum cost, length, profit…" with choices at each step
Optimisation DP: dp[state] = best over choices (min/max)
"Is it possible to…" (reach, split, partition, form)
Feasibility DP with booleans: dp[state] = OR over choices
Your recursion has parameters that repeat (draw the tree — same arguments appear twice)
Overlapping subproblems → memoize
+9 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Not writing the meaning of dp[i] in one sentence before coding. Most wrong DP code comes from a fuzzy state.
- Off-by-one between
dp[i]= "first i characters" ands.charAt(i - 1). Pick one convention and say it out loud.
quick check
One question. No pressure.
Which two properties make a problem a good fit for DP?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Climbing Stairs
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Which two properties make a problem a DP problem?
Question 1: Which two properties make a problem a DP problem?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.