Reusing answers you already solved

Solving the same thing again

Recursion solves a big problem
by splitting it into small ones.
Fibonacci is exactly that.
fib(5) calls fib(4) and fib(3),
fib(4) calls fib(3) and fib(2) again.
But look closely,
and fib(2) keeps popping up
on this branch and that one.
In the tree below,
tap one of the nodes.

The same small problem pops up all over the tree. (Click a node → all same values highlight)

See it?
The same fib(2) gets solved
not once but several times.
Same for fib(3).
As n grows,
this duplication blows up fast.
Solving an answer you already have
over and over
is clearly a waste.

Write the answer down

The fix is surprisingly simple.
Write a solved answer
on a note pad.
When the same one is needed again,
don't recompute,
just pull it from the note.
Compute only the new ones,
pull the seen ones back out.
Press the button
to handle calls one at a time.

Compute and jot the new, pull the seen from the note. (This is memoization)

Computing happens just the first time.
Everything else
gets pulled from the note,
so solving the same thing twice
vanishes entirely.
Writing a solved answer down
and reusing it like this
is called memoization.
The name sounds fancy,
but inside it's just "writing it down."

Filling the table from the bottom

You can flip the same idea
the other way around.
Instead of splitting down from the top,
fill the table upward
from the small values at the bottom.
fib(0) and fib(1) we just know.
Add them for fib(2),
add fib(1) and fib(2) for fib(3).
The lower cells are already written,
so the upper one is just an addition.

Fill upward one cell from 0 and 1. (Next cell = sum of the two below it · bottom-up)

This way doesn't even need
a note pad.
The table itself is the memo.
Go from bottom to top
in one pass,
and there's no re-solving at all.
If memoization is
"write it down when needed,"
this is "write it all down ahead."
Both mean the same thing inside.

It gets way faster

So how much faster is it?
The gap from one move,
writing it down, is enormous.
Pure recursion
solves all the duplicates too,
so as n grows
the work explodes upward.
Memo solves each cell just once,
only in proportion to n.
Grow n and compare the two.

Solves at the same n. (Pure recursion = exponential blowup · memo = linear in n)

See the difference?
With even a small bump in n,
the pure-recursion bar
shoots up off the screen.
The memo bar
stays almost flat.
Not solving the same answer again,
that one thing
is what divides slow from fast.

Wrapping up

Dynamic programming
is a hard-sounding name
but inside it's three steps.
Notice you're solving the same thing,
write a solved answer down,
reuse it and it gets way faster.
Tap the cards below one by one
to recap the three steps.

Solve again → write down → way faster. (Recalls that divide and conquer didn't overlap, so no memo needed)

In divide and conquer last time,
the split pieces didn't overlap,
so there was nothing to write down.
That's exactly the fork in the road.
When the pieces overlap,
that is, when the same small problem
keeps coming back,
that's when the one move
of writing it down changes everything.