13.4 Tabulation

Memoization evaluates states on demand through recursion. Tabulation takes the opposite approach. Instead of starting from the final answer and recursively exploring smaller subproblems, tabulation starts from the smallest subproblems and systematically builds larger solutions until the final answer is reached.

Tabulation is often called bottom-up dynamic programming. Most production-quality dynamic programming implementations eventually use tabulation because it eliminates recursion overhead, provides predictable memory access patterns, and makes space optimization easier.

Problem

Given a dynamic programming state and recurrence relation, how can we compute all states iteratively without recursion?

Understanding Bottom-Up Computation

Consider Fibonacci numbers.

Recurrence:

$$ F(n)=F(n-1)+F(n-2) $$

Memoization starts with:

F(n)

and recursively requests:

F(n-1)
F(n-2)

Tabulation begins with the smallest known states:

F(0)
F(1)

and computes:

F(2)
F(3)
F(4)
...
F(n)

The computation proceeds in dependency order.

The Core Idea

Every recurrence creates a dependency graph.

For Fibonacci:

F(5)
├── F(4)
└── F(3)

F(4)
├── F(3)
└── F(2)

Observe:

F(2)

must be computed before:

F(3)

and:

F(3)

must be computed before:

F(4)

The dependency graph naturally determines the order of evaluation.

Recipe 1: Identify Base States

Every tabulation algorithm begins with known values.

For Fibonacci:

$$ dp[0]=0 $$

$$ dp[1]=1 $$

These entries require no computation.

They serve as the foundation for all later states.

Recipe 2: Determine Dependency Order

Consider:

$$ dp[i] = dp[i-1] + dp[i-2] $$

To compute:

dp[i]

both dependencies must already exist.

Natural iteration:

for i := 2; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
}

The loop follows the recurrence dependencies.

Example: Fibonacci

Tabulation implementation:

func fib(n int) int {
    if n <= 1 {
        return n
    }

    dp := make([]int, n+1)

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

    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }

    return dp[n]
}

Complexity:

$$ O(n) $$

Memory:

$$ O(n) $$

No recursion is required.

Example: Staircase Problem

State:

$$ dp[i] $$

Meaning:

ways to reach step i

Recurrence:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Base cases:

$$ dp[0]=1 $$

$$ dp[1]=1 $$

Implementation:

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

for i := 2; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
}

The structure is identical to Fibonacci.

Example: Grid Paths

Problem:

Move only right or down.
Count paths.

State:

$$ dp[i][j] $$

Meaning:

paths to cell (i,j)

Recurrence:

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

Dependency graph:

(i-1,j)
     |
     v
(i,j)

(i,j-1) -> (i,j)

Valid iteration:

for i := 0; i < rows; i++ {
    for j := 0; j < cols; j++ {
        ...
    }
}

because:

top cell already computed
left cell already computed

before reaching the current cell.

Example: Coin Change

Problem:

minimum coins

State:

$$ dp[x] $$

Meaning:

minimum coins for amount x

Recurrence:

$$ dp[x] = 1+ \min(dp[x-c]) $$

Initialization:

$$ dp[0]=0 $$

All other states:

$$ \infty $$

Implementation:

for amount := 1; amount <= target; amount++ {
    for _, coin := range coins {
        if amount >= coin {
            dp[amount] = min(
                dp[amount],
                dp[amount-coin]+1,
            )
        }
    }
}

Amounts grow from small to large.

Dependencies are always available.

Example: Longest Common Subsequence

State:

$$ dp[i][j] $$

Meaning:

LCS length
between prefixes

Recurrence:

If characters match:

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

Otherwise:

$$ dp[i][j] = \max ( dp[i-1][j], dp[i][j-1] ) $$

Dependency directions:

up
left
upper-left

Therefore row-major iteration works naturally:

for i := 1; i <= n; i++ {
    for j := 1; j <= m; j++ {
        ...
    }
}

All required states already exist.

Building a DP Table

A useful mental model:

1. Draw the state space.

2. Mark base states.

3. Draw dependency arrows.

4. Find an ordering where every dependency appears earlier.

5. Iterate according to that ordering.

This method works for most tabulation problems.

Topological Thinking

Every dynamic programming recurrence forms a directed acyclic graph.

Example:

state A
depends on B and C

Graph:

B -> A
C -> A

Tabulation processes states in topological order.

This guarantees every dependency is available when needed.

Memoization vs Tabulation

Property	Memoization	Tabulation
Direction	Top-down	Bottom-up
Uses recursion	Yes	No
Computes needed states only	Yes	No
Stack usage	O(depth)	O(1)
Cache locality	Often poor	Usually good
Space optimization	Harder	Easier
Natural recurrence expression	Excellent	Moderate

Both approaches ultimately compute the same state graph.

The difference lies in traversal order.

Common Mistakes

Wrong Iteration Order

Suppose:

$$ dp[i] = dp[i+1] +1 $$

Then increasing iteration fails.

Dependencies are unavailable.

Always follow dependency direction.

Missing Initialization

If base states are incorrect:

all subsequent states become incorrect

Initialization errors often propagate through the entire table.

Invalid Boundaries

Grid problems commonly access:

i-1
j-1

Boundary rows and columns require special handling.

Incorrect Default Values

For minimization problems:

initialize with infinity

For maximization problems:

initialize with negative infinity

For counting problems:

initialize with zero

The wrong default value silently corrupts results.

Space Optimization Preview

Observe Fibonacci:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Only two previous states are needed.

The entire table is unnecessary.

Instead:

prev2 := 0
prev1 := 1

for i := 2; i <= n; i++ {
    current := prev1 + prev2

    prev2 = prev1
    prev1 = current
}

Memory drops from:

$$ O(n) $$

to:

$$ O(1) $$

Many dynamic programming algorithms admit similar optimizations.

When Tabulation Is Preferable

Tabulation is usually preferred when:

• all states are reachable
• recursion depth may be large
• cache locality matters
• memory optimization is important
• predictable performance is required

Competitive programming and high-performance systems often favor tabulation for these reasons.

Complexity Analysis

Let:

$$ S $$

be the number of states.

Let:

$$ K $$

be the transition cost.

Each state is processed once.

Total running time:

$$ O(S \times K) $$

Memory usage:

$$ O(S) $$

before any space optimization.

The asymptotic complexity usually matches memoization.

Practical performance is often better because recursion overhead disappears.

Takeaway

Tabulation computes dynamic programming states iteratively in dependency order. Starting from known base cases, it fills the state space until the final answer becomes available. Compared to memoization, tabulation eliminates recursion, improves memory locality, simplifies space optimization, and provides highly predictable execution behavior. For many large-scale dynamic programming problems, tabulation becomes the preferred implementation strategy once the recurrence relation is fully understood.