Bottom-Up Tabulation

Back in Tier 4, memoization solved the "recompute the same subproblem over and over" problem by caching results the first time a recursive call needed them - a top-down approach, since it starts from the big problem and works its way down to base cases as needed. This chapter introduces the other half of dynamic programming: tabulation, a bottom-up approach that starts from the smallest subproblems and builds up to the answer, filling in a table one entry at a time instead of recursing at all.

Memoization still thinks in terms of the original recursive function - it just remembers past answers so it never repeats work. Tabulation flips the direction entirely: instead of asking "what do I need to solve this big problem?" and recursing downward, it asks "what is the smallest version of this problem, and what does its answer let me compute next?" and works upward, iteratively, until it reaches the size you actually wanted. The two techniques compute the same answers and have the same time complexity, but tabulation avoids two real costs of recursion: the overhead of function calls, and the risk of a stack overflow on inputs deep enough to exceed Python's recursion limit.

A classic first tabulation example: you can climb a staircase 1 or 2 steps at a time, and you want to know how many distinct ways there are to reach step n. The number of ways to reach step i is the number of ways to reach step i - 1 (then take one final 1-step) plus the number of ways to reach step i - 2 (then take one final 2-step) - the exact same recurrence as Fibonacci, just wearing a staircase costume.

Because computing `dp[i]` only ever needs the two entries directly before it, the whole table can be compressed down to two rolling variables instead of an array of size n - a common tabulation optimization once you notice a dp recurrence only reaches a fixed, small window backward:

• -Tabulation builds the answer array (or table) from the base case upward, with a plain loop - no recursion, no call stack, no memo dictionary needed.
• -It has the same time complexity as the equivalent memoized recursion, but with lower constant-factor overhead and no stack-depth risk.
• -When a recurrence only depends on a fixed number of previous entries (like climb_stairs depending only on i-1 and i-2), the table can often be compressed to O(1) space.