Tabulation: Bottom-Up Dynamic Programming

Introduction

Welcome to the next lesson in our journey through dynamic programming! In our previous lessons, we mastered the memoization technique, a top-down approach where we start with our main problem and use recursion to break it down, caching results along the way to avoid redundant work.

Today, we're going to explore a powerful alternative called tabulation. This is a bottom-up approach to dynamic programming. Instead of breaking a big problem down, we'll start with the smallest, simplest subproblems and use their solutions to iteratively build our way up to the final answer. You'll learn how this method allows us to solve the exact same problems, like Fibonacci and Climbing Stairs, but using simple loops instead of recursion.

From Top-Down to Bottom-Up

Remember how our memoized Fibonacci function worked? To find fib(5), we called fib(4) and fib(3). This continued until we hit our base cases, fib(1) and fib(0). We then passed the results back up the chain.

Let's look at the memo array we used. As we solved for fib(5), the array was filled in, but not necessarily in order. However, to calculate fib(i), we always needed fib(i-1) and fib(i-2). This hints at another way of thinking about the problem.

What if we deliberately solved the subproblems in order, from smallest to largest?

We know fib(0) = 0 and fib(1) = 1.
With these, we can calculate fib(2) = fib(1) + fib(0) = 1.
Now knowing fib(2), we can find fib(3) = fib(2) + fib(1) = 2.
And so on, until we reach fib(5).

This is the essence of the bottom-up approach. We start from the "bottom" (the base cases) and build our way "up" to the target n.

The following video segment explains this transition beautifully.

What Is Dynamic Programming and How To Use It

Watch this clip from the CS Dojo channel. The presenter has just explained memoization and observes how the memo array gets filled. He then poses the exact question we just did: Why not just build the array from left to right from the start?

Watch from 09:26 to 11:20. Focus on the core idea of replacing the recursive structure with a simple for loop that builds the solution array step-by-step.

Tabulation: The Bottom-Up Approach

The technique you just saw is formally called tabulation. The name comes from the fact that we build a table (which in Python is usually a simple list or array) and fill it with the solutions to all subproblems, starting from the base cases.

This image provides a great visual contrast between memoization and tabulation:

Memoization and Tabulation Technique in Dynamic Programming — On the left, memoization (top-down) is like exploring a tree recursively, pruning branches you've already visited. On the right, tabulation (bottom-up) is like filling a table from left to right, where each new entry is built from previous entries.

The Tabulation Algorithm

The process is very systematic:

Create the Table: Create an array (let's call it dp, for dynamic programming) of size n + 1 to hold the solutions for all subproblems from 0 to n.
Initialize Base Cases: Fill in the known values for the base cases directly in the table. For Fibonacci, this would be dp[0] = 0 and dp[1] = 1.
Iterate and Fill: Loop from the first unsolved subproblem up to n. In each iteration, calculate the solution using the values already stored in your table. For Fibonacci, the loop would calculate dp[i] = dp[i-1] + dp[i-2].
Return the Result: The final answer is simply the value at the last index of the table, dp[n].

Let's see this applied to the "Climbing Stairs" problem, which you'll recall has the same structure as Fibonacci.

Climbing stairs to reach the top

This article from GeeksforGeeks explains how to apply the bottom-up (tabulation) approach to the Climbing Stairs problem. It clearly describes the process we just outlined.

Read the section titled 'Using Bottom-Up DP (Tabulation) – O(n) Time and O(n) Space'. Pay attention to the description of the process and then examine the Python code snippet. You'll see it perfectly matches the four steps described above.

As you can see, the code is very direct. There is no recursion, only a simple for loop.

Key Advantage: No More Stack Overflow

One of the most significant practical differences between tabulation and memoization is how they handle very large inputs.

Recursive functions, like our memoized solution, add a new frame to the call stack for each pending call. If n is very large (e.g., 10,000), you could have 10,000 nested function calls, which can exceed the program's recursion depth limit and cause a "stack overflow" error.

Since tabulation uses a simple loop, it doesn't have this problem. It only uses a fixed amount of memory for the table, regardless of how large n gets.

This next video clip provides a powerful demonstration of this exact issue.

What Is Dynamic Programming and How To Use It

Let's return to the CS Dojo video. Here, the presenter runs the memoized and tabulated Python code for Fibonacci with a large input.

Watch from 12:13 to 14:07. Notice how the memoized (recursive) solution works for n=35 but fails with a RecursionError for n=1000. Then, see how the bottom-up (iterative) solution handles n=1000 and even n=10000 with no issues.

This makes tabulation a safer and often more efficient choice for problems that might involve very deep recursion.

Memoization vs. Tabulation: A Summary

Both techniques are valid forms of dynamic programming that turn exponential problems into linear ones. Choosing between them often comes down to the problem structure and personal preference.

The following table, based on the article from AlgoCademy, summarizes the key differences.

Factor	Memoization (Top-Down)	Tabulation (Bottom-Up)
Approach	Starts at `n` and breaks it down.	Starts at base cases and builds up to `n`.
Implementation	Recursive.	Iterative (uses loops).
Subproblem Solving	Solves only the subproblems required to reach `n`.	Solves all subproblems from the base up to `n`.
Stack Overflow Risk	High risk for deep recursion (large `n`).	No risk of stack overflow.
Speed	Can be slightly slower due to function call overhead.	Generally faster due to direct iteration.

You can review a more detailed comparison in the following resource if you wish.

When to Use Memoization vs Tabulation: A Comprehensive Guide

This article provides a concise comparison table that summarizes the differences between the two techniques.

Find the heading 'Comparing Memoization and Tabulation' and review the table. It's a great quick-reference for the points we've discussed.

Conclusion

Great work! You've now been introduced to the two main strategies for dynamic programming.

Key Takeaways:

Tabulation is a bottom-up DP technique that solves problems iteratively.
It works by creating a table (an array/list) and filling it with solutions to subproblems, starting from the base cases.
Because it uses loops instead of recursion, tabulation is generally a bit faster and, most importantly, avoids stack overflow errors for large inputs.
Both tabulation and memoization are powerful tools for solving problems with optimal substructure and overlapping subproblems.

Preview of the Next Lesson:
We've covered the concept of tabulation and seen how it's implemented. In the next lesson, you'll get to put this knowledge into practice. We will tackle another classic DP problem, and you will implement the tabulated solution from scratch, solidifying your understanding of this bottom-up approach.

Recommended resources