tabulation

Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.

In more detail

Tabulation uses loops instead of recursion, so it has no call-stack overhead or recursion limit, and it makes memory use explicit. The knapsack table has one row per item and one column per capacity. Once filled, the table can be traced back to reconstruct the chosen solution.

Related terms

Taught in

References