bottom-up tabulation

Instead of starting from the big question and recursing down to the small ones, you start from the smallest answers you already know and build upward, filling a table row by row until the big answer is the last cell you write. It is like assembling a tower of blocks: you cannot place a higher block until the ones it rests on are in place, so you lay the foundation first and work up. There is no recursion at all — just loops that fill an array in a carefully chosen order.

The recipe is: allocate a table indexed by the state, write the base-case entries directly, then loop over the states in an order that guarantees every entry is computed only after all the entries it depends on, applying the transition to fill each cell from earlier cells. For Fibonacci: make an array f, set f[0]=0 and f[1]=1, then for i from 2 to n set f[i]=f[i-1]+f[i-2]; the answer is f[n]. The loop order from small i to large i is exactly what makes f[i-1] and f[i-2] already available when you need them. The running time is again (number of states) times (work per transition), but now with no function-call overhead and no stack.

Tabulation's payoffs are speed and predictable memory. Because the fill order is explicit, you can often shrink space dramatically: Fibonacci only ever looks back two cells, so two scalar variables suffice instead of the whole array, giving O(1) space. The price is that you must work out a valid evaluation order yourself, and a naive tabulation computes every state in the table even ones the answer never actually needs — whereas a top-down memoization touches only reachable states. So tabulation trades a little flexibility for raw efficiency and stack safety.