Bottom-Up Tabulation

Memoization works top-down: you ask for the big answer and let recursion fill the cache as it goes. Tabulation turns that around. You start from the smallest subproblems, solve them first, and build upward until you reach the one you actually wanted. Same subproblems, same answers - opposite direction.

A new problem: climbing stairs

You are climbing a staircase with n steps. Each move takes you up either 1 step or 2 steps. How many distinct ways are there to reach the top?

Think about your last move. To land on step n, you either came from step n-1 (a 1-step move) or from step n-2 (a 2-step move). Those two groups never overlap, so the total is their sum:

ways(n) = ways(n-1) + ways(n-2)
ways(0) = 1   (one way to "stand at the bottom": do nothing)
ways(1) = 1   (a single 1-step move)

That is the same recurrence as Fibonacci. The lesson underneath: a huge share of DP is spotting that "the answer for n is built from the answers for smaller inputs," then writing that relationship down.

Filling the table

Instead of recursing, make an array dp where dp[i] holds the number of ways to reach step i. Seed the smallest cases, then let a loop fill each cell from the two below it.

def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

for n in range(1, 8):
    print(n, "steps ->", climb_stairs(n), "ways")

1 steps -> 1 ways
2 steps -> 2 ways
3 steps -> 3 ways
4 steps -> 5 ways
5 steps -> 8 ways
6 steps -> 13 ways
7 steps -> 21 ways

What just happened: the loop never recurses and never re-computes. By the time it reaches dp[i], the two cells it needs (dp[i-1] and dp[i-2]) are already filled, so each cell is a single addition. That is the essence of tabulation: order the subproblems so that every answer is ready before you need it. The running time is O(n) with O(n) space for the table.

💡 Key point. Memoization and tabulation compute exactly the same subproblems. Memoization discovers the order lazily through recursion; tabulation commits to the order up front with a loop. Pick whichever reads more clearly for the problem - tabulation avoids recursion-depth limits, memoization can skip subproblems it never needs.

Trimming the memory: the rolling version

Look at the loop again: to fill dp[i] you only ever look at the previous two cells. The rest of the table is dead weight. So keep just two variables and slide them forward.

def climb_stairs(n):
    if n <= 1:
        return 1
    prev, curr = 1, 1          # ways to reach step 0 and step 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

print(climb_stairs(7))
print(climb_stairs(40))

21
165580141

What just happened: prev and curr always hold the last two results, and each step rolls them forward by one. Same O(n) time, but now O(1) space - constant memory no matter how big n gets. This "keep only what the next step needs" trick is one of the most common DP optimizations.

⚠️ Gotcha. The two-variable update relies on doing both assignments at once. In Python, prev, curr = curr, prev + curr evaluates the whole right side first, so prev + curr still uses the old prev. Writing it as two separate lines (prev = curr then curr = prev + curr) overwrites prev too early and silently computes the wrong sequence.

Check yourself

[
  {
    "q": "What is the core difference between tabulation and memoization?",
    "choices": ["Tabulation builds answers bottom-up in a table with a loop; memoization is top-down recursion that caches results", "They are two different names for the same code", "Tabulation always uses recursion; memoization always uses loops", "Tabulation only works for Fibonacci-shaped problems"],
    "answer": 0,
    "explain": "Both solve the same subproblems. Tabulation orders them smallest-first and fills a table iteratively; memoization recurses top-down and caches each result on first computation."
  },
  {
    "q": "For climbing stairs with 1- or 2-step moves, why is ways(n) = ways(n-1) + ways(n-2)?",
    "choices": ["Because the answers happen to be Fibonacci numbers", "Because your last move came from either step n-1 or step n-2, and those two sets of paths never overlap", "Because you can only ever take 2-step moves", "It is a coincidence that only holds for small n"],
    "answer": 1,
    "explain": "Every path to step n ends with a final move from n-1 or from n-2. Counting each group and adding them (they are disjoint) gives the recurrence."
  },
  {
    "q": "What does the rolling two-variable version save compared to the full table?",
    "choices": ["Time - it changes the big-O", "Nothing, it is only a style preference", "Memory - it keeps O(1) space instead of an O(n) table", "Accuracy on large inputs"],
    "answer": 2,
    "explain": "Each step needs only the previous two results, so two variables suffice. Time stays O(n); space drops from O(n) to O(1)."
  }
]