top-down memoization

You write the obvious recursive solution — the one that solves a problem by asking smaller versions of itself — but you give it a notebook. Each time the function finishes computing an answer for some input, it jots that answer down next to the input. Each time it is asked for an answer, it first checks the notebook: if the answer is already there, it returns it instantly instead of recomputing. That notebook is the memo, and the technique is memoization. It keeps the natural, readable recursive structure but kills the duplicated work.

Concretely, a memoized function looks like this in pseudocode: function solve(state): if memo[state] is filled, return memo[state]; if state is a base case, return its known value; otherwise compute the answer by combining solve(smaller states), store it in memo[state], and return it. The first time each distinct state is reached you pay full price; every later request for the same state is a cheap table lookup. For Fibonacci this turns the roughly 2^n naive recursion into O(n): there are n+1 distinct states fib(0)..fib(n), each computed once in constant work, and the rest are lookups. The running time of a memoized DP is therefore (number of distinct states) times (cost to combine subresults for one state).

Because it follows the recursion you would write anyway, memoization is often the easiest DP to get right: you do not have to figure out a safe evaluation order by hand — the recursion only descends into a subproblem when it actually needs it, so dependencies are resolved automatically, and unreachable states are never computed. The costs are real, though: deep recursion can overflow the call stack for large inputs, each call carries function-call overhead, and the hash or array used as the memo consumes memory. When those costs bite, you convert the same recurrence to bottom-up tabulation.