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
- memoisation — Caching a function's results by its arguments so that repeated calls return the stored answer instead of recomputing it.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- traceback — Walking back through a filled dynamic-programming table from the final cell to recover the choices that produced the optimal answer.
- base case — The smallest input a recursive function answers directly, without calling itself again, which stops the recursion.
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Python Dicts And Sets Under The Hood — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers