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
