liveBook · Manning

Tabulation

As explained in Timeless Algorithms, The Foundational Ideas

Tabulation is a dynamic-programming implementation technique that iteratively evaluates subproblems in a predetermined dependency order and stores their results.

Tabulation is a bottom-up way to evaluate a dynamic-programming recurrence. Start with known base cases, store their values, then compute larger subproblems in an order that ensures each dependency is already available. Reuse stored results rather than recomputing them. section 6.1.4

Tabulation and memoization evaluate the same recurrence over the same states, transitions, and base cases; they differ in how and when they encounter subproblems. Tabulation suits dense state spaces with an easy-to-define dependency order. Its predictable progression avoids recursive calls and can make computation easier to understand, debug, and optimize. section 6.1.4 section 6.2.4

Table 6.1 Initializing the solution from the base cases. The known values along 𝑖 = 0 and 𝑐 = 0 provide the starting point for bottom-up computation.
Item (𝑖)
(𝑤𝑖, 𝑣𝑖)
𝑐 = 0
𝑐 = 1
𝑐 = 2
𝑐 = 3
𝑐 = 4
𝑐 = 5
𝑐 = 6
𝑐 = 7
0
Base Cases
0
0
0
0
0
0
0
0
1
(3, 4)
0
 
 
 
 
 
 
 
2
(4, 5)
0
 
 
 
 
 
 
 
3
(2, 3)
0
 
 
 
 
 
 
 
4
(1, 2)
0
 
 
 
 
 
 
 

The 0/1 knapsack table lays out states by items considered and capacity; its zero-item row and zero-capacity column provide the starting values. section 6.2.4 section 6.2.5

Worked examples show how the dependency order shapes the computation:

  • For 0/1 knapsack, fill the table row by row, comparing inclusion and exclusion for each item and capacity. With four items and capacity 7, the completed table gives a maximum value of 10. section 6.2.4 section 6.2.5
  • For coin change, process denominations first and update amounts from each denomination through the target. This counts combinations without treating different orders of the same coins as distinct; for denominations {1, 5, 10}, the count for 12 is 4. section 6.3.4 section 6.3.5

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Traces base-case initialization, dependency ordering, and table updates through worked optimization and counting problems.
Examples
Uses Fibonacci numbers, a four-item knapsack with capacity 7, and coin combinations for target 12.
What it assumes
Assumes a formulated recurrence, states, transitions, and base cases; implementation follows rather than replaces problem formulation.
What you can do after
Apply tabulation to evaluate a recurrence by initializing base cases and filling a table in dependency order.
How it connects
Compares tabulation with memoization and applies it to recurrence relations, 0/1 knapsack, and coin change.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.