Tabulation — Bottom-Up Dynamic Programming

In the previous module on memoization, we explored how to optimize recursive solutions by caching computed results. We started with the natural, top-down recursive formulation and added a memo to avoid redundant work. This approach, while powerful, still carries the conceptual overhead of recursion—function call stacks, implicit dependency management, and the ever-present specter of stack overflow for deeply nested problems.

Tabulation flips this paradigm entirely.

Instead of starting from the original problem and recursively breaking it down, tabulation begins at the base cases—the smallest, most fundamental subproblems—and systematically builds upward to the final answer. Rather than hoping that memoization will prevent repeated work, tabulation guarantees that each subproblem is solved exactly once, in the precise order required by the dependency structure.

This is bottom-up dynamic programming: the art of constructing a solution table, cell by cell, until the answer emerges at the top.

Tabulation is an iterative approach to dynamic programming where we construct a table (array, matrix, or higher-dimensional structure) that holds the solutions to all subproblems. Instead of computing values on demand through recursive calls, we compute them proactively, in an order that ensures every value we need is already available when we need it.

The name "tabulation" comes from the central artifact: the table (or DP table, DP array). Each cell in this table corresponds to a subproblem, and the value stored in that cell is the solution to that subproblem. The algorithm's job is to fill this table completely, after which the answer to the original problem can be read directly from the appropriate cell.

The mental model shift:

With memoization (top-down), you think: "What subproblems does this problem depend on? Let me compute those first (via recursion)."

With tabulation (bottom-up), you think: "What are the smallest possible subproblems? Let me solve those and build up to my target."

This shift is profound. Top-down follows the problem's natural decomposition; bottom-up follows the solution's natural construction.

Understanding the structure of a DP table is essential for mastering tabulation. The table's dimensions, indices, and cell semantics are not arbitrary—they directly encode the problem's state space and the relationships between subproblems.

Dimensions correspond to state variables:

Each dimension of the DP table corresponds to one variable that defines the state of a subproblem. For a problem with state (i), we use a 1D array. For state (i, j), we use a 2D array. For state (i, j, k), a 3D array, and so on.

Cell semantics define the subproblem:

The value stored in dp[i] (or dp[i][j], etc.) must have a precise meaning. This meaning is the DP definition or state definition—arguably the most important aspect of designing a DP solution. Without a clear, consistent definition of what each cell represents, the algorithm cannot be correct.

For example, in the Fibonacci problem:

• dp[i] = the i-th Fibonacci number

In the Longest Common Subsequence problem:

• dp[i][j] = length of the LCS of the first i characters of string A and the first j characters of string B

In the 0/1 Knapsack problem:

• dp[i][w] = maximum value achievable using the first i items with capacity w

Index ranges and off-by-one considerations:

A common source of bugs in tabulation is index management. The table size must accommodate all necessary states, including base cases. Many DP solutions use 1-indexed tables (where dp[0] represents an empty or null state) to simplify transitions:

For a problem with n elements:
- 0-indexed: dp[0..n-1], size n
- 1-indexed: dp[0..n], size n+1, where dp[0] is often a base case

1-indexed tables are particularly useful when the transition formula references dp[i-1], because i-1 is always valid (never negative) when i >= 1.

The most illuminating way to understand tabulation is to see how it relates to the recursive formulation of the same problem. Every tabulation solution has a corresponding recursive solution, and vice versa. The transformation between them is systematic and mechanical, once you understand the mapping.

Let's trace this transformation for the classic Fibonacci problem.

Step 1: Recursive Definition

The naive recursive solution directly expresses the mathematical definition:

fib(n):
  if n <= 1: return n
  return fib(n-1) + fib(n-2)

This says: to get fib(n), first compute fib(n-1) and fib(n-2), then add them. The base cases are fib(0) = 0 and fib(1) = 1.

Step 2: Identify State and Transitions

• State: A single integer n
• Transition: fib(n) = fib(n-1) + fib(n-2)
• Base cases: fib(0) = 0, fib(1) = 1
• Dependencies: fib(n) depends on fib(n-1) and fib(n-2) (smaller values)

Step 3: Design the Table

• Create a 1D array dp of size n+1
• dp[i] = the i-th Fibonacci number
• We need dp[0] through dp[n]

Step 4: Initialize Base Cases

dp[0] = 0
dp[1] = 1

These are the atomic subproblems that don't depend on anything else.

Step 5: Fill the Table in Dependency Order

Since dp[i] depends on dp[i-1] and dp[i-2], we must compute smaller indices before larger ones. This means a simple loop from 2 to n:

for i from 2 to n:
    dp[i] = dp[i-1] + dp[i-2]

Step 6: Extract the Answer

The answer is dp[n]—the value in the cell corresponding to the original problem.

The control flow in tabulation is fundamentally different from memoized recursion. Where recursion relies on the call stack to manage the order of computation, tabulation uses explicit loops to march through the state space.

The canonical tabulation structure:

Key insight: The loop enforces correct order

The loop structure is not arbitrary—it's designed to ensure that when we compute dp[s], all subproblems that dp[s] depends on have already been computed. This is the dependency order or topological order of the subproblem graph.

For Fibonacci, the dependency is simple: dp[i] depends on dp[i-1] and dp[i-2], both with smaller indices. A simple forward loop (for i from 2 to n) satisfies this.

For more complex problems (like grid paths or LCS), the dependency structure requires nested loops with carefully chosen directions. We'll explore this deeply in the next page on dependency order.

Visualizing the computation as table filling:

Imagine the DP table as a spreadsheet. Tabulation is the process of filling in cells from left to right, top to bottom (or whatever order the dependencies require). When you reach any cell, you look at the cells it depends on—which are guaranteed to already be filled—and compute the new value.

This visual metaphor is incredibly powerful for designing and debugging DP solutions. You can literally draw the table, mark the base cases, and trace the filling order to verify your logic before writing code.

To solidify the tabulation concept, let's work through a 2D example: the Unique Paths problem.

Problem Statement: Given an m × n grid, find the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1, n-1). You can only move right or down at each step.

This problem has a beautiful tabular structure that makes tabulation the natural formulation.

Step 1: Define the State

dp[i][j] = number of unique paths from (0,0) to (i,j)

This is our DP definition. Each cell represents a subproblem: "How many ways can we reach this cell from the start?"

Step 2: Establish the Transition

To reach cell (i,j), we must come from either:

• Above: (i-1, j) — if we moved down
• Left: (i, j-1) — if we moved right

Therefore:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Step 3: Identify Base Cases

• The first row: dp[0][j] = 1 for all j (only one way to reach: always move right)
• The first column: dp[i][0] = 1 for all i (only one way to reach: always move down)

Step 4: Determine Loop Order

Since dp[i][j] depends on dp[i-1][j] (above) and dp[i][j-1] (left), we need to fill:

• In order of increasing i (top to bottom)
• In order of increasing j (left to right)

Nested loops: outer loop over rows, inner loop over columns.

Tabulation offers several advantages over memoized recursion, making it the preferred approach in many scenarios. Understanding these benefits helps you make informed decisions about which technique to apply.

1. No Recursion Overhead

Recursion incurs costs that iteration avoids:

• Function call overhead: Each recursive call pushes a stack frame (return address, local variables, etc.)
• Stack space: Deep recursion can consume significant stack memory
• Stack overflow risk: For very deep recursion (e.g., fib(100000)), the call stack may exceed system limits

Tabulation uses only loop constructs—no stack frames, no overhead, no risk of stack overflow.

2. Predictable Memory Access Patterns

Tabulation typically accesses memory in sequential, predictable patterns (e.g., iterating through an array from index 0 to n). This is cache-friendly:

• Spatial locality: Adjacent array elements are in the same cache line
• Temporal locality: Recently accessed elements are likely to be accessed again soon

Memoized recursion, by contrast, may access the memo table in unpredictable order based on the recursion tree, leading to more cache misses.

3. Easier Space Optimization

Because the computation order is explicit and fixed, tabulation makes it easier to identify opportunities for space optimization. If you only need the previous row to compute the current row, you can reduce space from O(n²) to O(n) using a rolling array technique.

With memoization, such optimizations are harder because the recursion pattern doesn't naturally expose which memo entries can be discarded.

4. Deterministic Execution

Tabulation executes the same operations in the same order every time. This determinism aids:

• Debugging: You can print the table state at any point and know exactly what should be there
• Profiling: Performance characteristics are consistent across runs
• Testing: Intermediate states are predictable and can be validated

While tabulation is conceptually simpler than recursion, it introduces its own class of bugs. Being aware of these pitfalls helps you avoid them.

We've established the foundational concepts of tabulation—the iterative, bottom-up approach to dynamic programming. Let's consolidate the key insights:

What's next:

Understanding that we fill a table is only half the battle. The critical insight is in what order we fill it. The next page explores dependency order—how to analyze a problem's subproblem dependencies and derive the correct loop structure. This is where tabulation becomes both an art and a science.